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

Question

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

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

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

#c #embedded #programming #russian

0

09.11.2021

18 ответов

16 просмотров

Ilya Zviagin

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

0

09.11.2021

Ilya Zviagin

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

0

09.11.2021

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, и тут возник вопрос, это влияет в общем случае но сложность или нет?

0

09.11.2021

Constantine Drozdov

MrAndreson
ну допустим есть такая функция // v содержит отсо...

странный вопрос... суммировать цикл?

0

09.11.2021

MrAndreson Автор вопроса

Constantine Drozdov
странный вопрос... суммировать цикл?

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

0

09.11.2021

Constantine Drozdov

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

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

0

09.11.2021

MrAndreson Автор вопроса

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

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

0

09.11.2021

Constantine Drozdov

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

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

0

09.11.2021

MrAndreson Автор вопроса

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

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

0

09.11.2021

Constantine Drozdov

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

и что из этого следует?

0

09.11.2021

Constantine Drozdov

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

0

09.11.2021

Andrey M

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

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

0

09.11.2021

MrAndreson Автор вопроса

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

благодарю добрый человек

0

09.11.2021

MrAndreson Автор вопроса

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

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

0

09.11.2021