Сложность алгоритма

@A66a · Регистрация: 29.03.2024

Студворк — интернет-сервис помощи студентам

Добрый вечер всем форумчанам! Вот такой код:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <set>
#include <map>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
int main() {
    int cnt, n;
    cin >> cnt >> n;
    vector<pair<int, string>> l;
    string words = "";
    map<int, int> score;
    for(int i = 0; i < n; ++i) {
        pair<int, string> p;
        cin >> p.first >> p.second;
        l.push_back(p);
    }
    reverse(l.begin(), l.end());
    for(int i = 0; i < n; ++i) {
        if((int)words.find(l[i].second) == -1) {
            ++score[l[i].first];
        }
        words += l[i].second;
    }
    for(int i = 1; i <= cnt; ++i) {
        cout << score[i] << " ";
    }
}

Я думал, что сложность алгоритма О(n), но работает долго. Подскажите, пожалуйста, какая сложность.

@Royal_X · 29.03.2024, 18:29

Сообщение от A66a

Я думал, что сложность алгоритма О(n), но работает долго

Логики здесь не вижу.
O(n) ничего не говорит о том, будет ли алгоритм работать долго или нет.

Недавно, видел нечто похожий бред. Но там была сложность O(1) и чел удивлялся, почему работает долго, ведь это мол "самая низкая из всех сложностей". Но O(1) это говорит, что выполняется за константное время, а это константное время может быть 100 или 1000 лет)))

@SmallEvil · 29.03.2024, 19:57

Если разбить на мелкие подзадачи, с "малым" временем выполнения :
1. Добавление в std::vector - O(1) плюс (log n) реалокаций с копированием.
2. std::reverse

Exactly std::distance(first, last) / 2 swaps.

3. std::string::find() O(words.size()) на каждой итерации.
4. вставка/доступ элемента score O(log score.size()) при каждом доступе.
5. конкатенация строк оператором+=

Complexity
There are no standard complexity guarantees, typical implementations behave similar to std::vector::insert().

Для вставки вектора в вектор.

4) Linear in std::distance(first, last) plus linear in the distance between pos and end of the container.

То есть заметно сколько везде нужно проработать.
При этом итоговая сложность зависит от входных данных.
Как от n так и от остальных.

@TheCalligrapher · 29.03.2024, 21:12

Сообщение от A66a

Я думал, что сложность алгоритма О(n), но работает долго.

Какого именно алгоритма?

Сообщение от A66a

C++
1
2
3
    for(int i = 0; i < n; ++i) {
        if((int)words.find(l[i].second) == -1) {
            ++score[l[i].first];

Здесь у вас n итераций с вызовом O(n) метода std::string::find и O(log n) метода std::map::operator []. То есть это уже квадратичная сложность. Никакого O(n) тут не получится.

@A66a · 29.03.2024, 21:47 **[ТС]**

[QUOTE=TheCalligrapher;17261889]Какого именно алгоритма?
Того, который в вопросе, вы правильно поняли

Сообщение от TheCalligrapher

Здесь у вас n итераций с вызовом O(n) метода std::string::find и O(log n) метода std::map::operator []. То есть это уже квадратичная сложность. Никакого O(n) тут не получится.

Понял, спасибо

@Royal_X · 29.03.2024, 22:31

A66a, если не хочешь разбираться в сложностях алгоритмов стандартной библиотеки или если код очень сложный, то можно сделать проще

Берешь разные входные данные и смотришь на время. Составляешь потом график. По нему будем видно, что за сложность

@SmallEvil · 29.03.2024, 22:45

Сообщение от Royal_X

Берешь разные входные данные и смотришь на время. Составляешь потом график. По нему будем видно, что за сложность

Хм, сомнительно.
Есть же функции со множеством минимумов/максимумов на разных отрезках.
Вида типа : http://cos-cos.ru/math/327/
Не уверен что методом тыка данных можно выяснить адекватную ассимптотику.

Добавлено через 2 минуты
Чисто по представленному коду не составит труда создать мин. и макс. ассимптотики.

@Royal_X · 29.03.2024, 23:02

SmallEvil, если код большой, ты устанешь все считать, а иногда это практически невозможно. Более того, если используются какие-то библиотеки, то придется еще копаться в их алгоритмах. Поэтому метод тыка недооценивать нельзя. Кроме того, сложность разная бывает. Как раз методом тыка можно найти среднюю сложность алгоритма, а не только наихудший случай. Никто ж не говорит, что нужно вручную вводить входные данные. Все можно автоматизировать.
Конечно, код ТС простой, здесь метод тыка особо и не нужен. Но может ТС будет интересно о нем узнать.

@SmallEvil · 29.03.2024, 23:52

Сообщение от Royal_X

если код большой, ты устанешь все считать

В таком случае этого просто не делают.

Сообщение от Royal_X

Все можно автоматизировать.

Есть много случаев когда вариации данных невозможно перебрать.
В таких случаях средний подсчет работы алгоритма будет не более чем гадание на кофейной гуще.
Наверное

Нет, я не говорю что стоит от него отказаться полностью.
Чем однообразнее данные, тем лучше будет такой метод оценки работать.

Сообщение от Royal_X

Но может ТС будет интересно о нем узнать.

Даже мне интересно его будет где то применить.
Вообще не делать оценку (из-за сложности алгоритма, набора алгоритмов) VS сделать оценку на наиболее возможных входных данных.
Я думаю тут выбор очевиден. Даже для той же презентации. Сделал, сдал, забыл.

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

Сложность алгоритма

Решение

Решение

@Royal_X 6118 / 2813 / 1038 Регистрация: 01.06.2021 Сообщений: 10,254
	29.03.2024, 22:31
	A66a, если не хочешь разбираться в сложностях алгоритмов стандартной библиотеки или если код очень сложный, то можно сделать проще Берешь разные входные данные и смотришь на время. Составляешь потом график. По нему будем видно, что за сложность 1

@Royal_X 6118 / 2813 / 1038 Регистрация: 01.06.2021 Сообщений: 10,254
	29.03.2024, 23:02
	SmallEvil, если код большой, ты устанешь все считать, а иногда это практически невозможно. Более того, если используются какие-то библиотеки, то придется еще копаться в их алгоритмах. Поэтому метод тыка недооценивать нельзя. Кроме того, сложность разная бывает. Как раз методом тыка можно найти среднюю сложность алгоритма, а не только наихудший случай. Никто ж не говорит, что нужно вручную вводить входные данные. Все можно автоматизировать. Конечно, код ТС простой, здесь метод тыка особо и не нужен. Но может ТС будет интересно о нем узнать. 0