170 похожих чатов

Может кто-нибудь подскажет, как подсчитывается временная сложность алгоритма, если

у меня размер контейнера будет увеличивается на каждой итерации.

Допустим есть n входных массивов и один выходной, при этом в цикле происходит операция над каждым массивом, сложность которой зависит от длины выходного массива, как это учесть?

18 ответов

18 просмотров

поясни как сложность может зависеть от выходных данных?

Временная сложность не зависит от этого в общем случае

Как это учесть - тоже не понятно не зная алгоритма и его сути

MrAndreson- Автор вопроса
Ilya Zviagin
Как это учесть - тоже не понятно не зная алгоритма...

ну допустим есть такая функция // v содержит отсортированные списки list<int> foo(vector<list<int>> &v) { list<int> res; for(list<int> &li : v) { res.merge(li); return res; } тут у merge, как говорит стандарт, сложность O(n+k), где n и k объединяемые списки, но n на каждой итерации увеличивается на k, и тут возник вопрос, это влияет в общем случае но сложность или нет?

MrAndreson- Автор вопроса
MrAndreson
в смысле суммировать цикл?

а относительно каких параметров вы хотите считать временную сложность алгоритма?

MrAndreson- Автор вопроса
Constantine Drozdov
а относительно каких параметров вы хотите считать ...

понял, только вопрос то в чем, понятно, что сложность будет m * (n + k), где m размер входного вектора, n - размер res, k - размер li, только n меняется на каждой итерации на k, разве это не влияет на сложность??

MrAndreson
понял, только вопрос то в чем, понятно, что сложно...

странно оценивать временную сложность относительно внутреннего параметра алгоритма, так что непонятно, при чем тут res

MrAndreson- Автор вопроса
Constantine Drozdov
странно оценивать временную сложность относительно...

так размер res же напрямую влияет на время работы ф-ции merge

MrAndreson
так размер res же напрямую влияет на время работы ...

вот смотрите for (int i = 0; i < n; ++i) for (int j = 0; j < i; ++j) if (a[i] < a[j]) swap(a[i], a[j]); вы задаёте вопрос: как оценивать сложность этого алгоритма, ведь внутренний цикл зависит от параметра i

MrAndreson
так размер res же напрямую влияет на время работы ...

сложность квадратичная. если n- число списков, то каждый n-й список добавит обработку не только своих элементов, но и дополнительный перебор всех накопленных элементов предыдущих n-1 списков,

MrAndreson- Автор вопроса
MrAndreson- Автор вопроса
Andrey M
сложность квадратичная. если n- число списков, то ...

стоп, а не m*n, где m общее к-во элементов?

MrAndreson
стоп, а не m*n, где m общее к-во элементов?

мы ничего не знаем про элементы списка. усредненно считаем, что все списки равноценны на бесконечности.

Andrey M
сложность квадратичная. если n- число списков, то ...

для \sum_{i=1..n} (n-i)*s_i такая оценка бывает грубоватой. Скажем, \sum_{i=1..n} (n-i)*2^i = O(2^n) = O(\sum_{i=1..n} 2^i)

Похожие вопросы

Обсуждают сегодня

Господа, а что сейчас вообще с рынком труда на делфи происходит? Какова ситуация?
Rꙮman Yankꙮvsky
29
А вообще, что может смущать в самой Julia - бы сказал, что нет единого стандартного подхода по многим моментам, поэтому многое выглядит как "хаки" и произвол. Короче говоря, с...
Viktor G.
2
30500 за редактор? )
Владимир
47
а через ESC-код ?
Alexey Kulakov
29
Гайс, вопрос для разносторонее развитых: читаю стрим с юарта, нада выделять с него фреймы с определенной структурой, если ли чо готовое, или долбаться с ринг буффером? нада у...
Vitaly
9
Чёт не понял, я ж правильной функцией воспользовался чтобы вывести отладочную информацию? но что-то она не ловится
notme
18
У меня есть функция где происходит это: write_bit(buffer, 1); write_bit(buffer, 0); write_bit(buffer, 1); write_bit(buffer, 1); write_bit(buffer, 1); w...
~
14
Добрый день! Скажите пожалуйста, а какие программы вы бы рекомендовали написать для того, чтобы научиться управлять памятью? Можно написать динамический массив, можно связный ...
Филипп
7
Недавно Google Project Zero нашёл багу в SQLite с помощью LLM, о чём достаточно было шумно в определённых интернетах, которые сопровождались рассказами, что скоро всех "ибешни...
Alex Sherbakov
5
длина пакета фиксированная, или меняется?
Okhsunrog
7
Карта сайта