расчет сложности сортировки

std :: sort выполняет приблизительно N * log2 (N) (где N — расстояние) сравнения элементов (источник — http://www.cplusplus.com/), поэтому его сложность составляет N * log2 (N).
Пожалуйста, помогите мне рассчитать сложность для следующего кода:

void func(std::vector<float> & Storage)
{
for(int i = 0; i < Storage.size() - 1; ++i)
{
std::sort(Storage.begin()+i, Storage.end());
Storage[i+1] += Storage[i];
}
}

сложность = N ^ 2 * log2 (N) или 2log2 (2) + 3log2 (3) + … + (N) log2 (N)?
Спасибо.

2

Решение

Правильный способ вычислить сложность состоит в том, чтобы оценить сложность повторного O(K Log K) проблемы линейно увеличивающихся размеров K = 1 ... N, Это можно сделать либо путем вычисления суммы, либо просто путем вычисления интеграла

Integrate[K Log[K], {K, 0, N}]

например, с Mathematica, и вы получите

1/4 N^2 (-1 + 2 Log[N])

который из O(N^2 Log N),

Хотя для полиномиальных и логарифмических функций это справедливо, в целом неверно, что интеграл K = 1 ... N подзадачи сложности f(K) равно N f(N), Например. сумма K = 1 ... N подзадачи сложности Exp[K] это просто Exp[N]не N Exp[N],

1

Другие решения

Я бы согласился с N^2*log2(N) так как алгоритм сортировки выполняется N раз. В Биг-О, где c является константой:

c*N * N*log2(N) => O(N^2*log2(N))
0

Это будет асимптотически O ((N ^ 2) * (log2 (N))

we need sum of k*log2(k) k from 1 to N
0

Вы суммируете логарифмические функции:

complexity <- 0

for i = 1..N
complexity += i Log(i)

В результате чего происходит суммирование:

Log(1) + 2 Log(2) + ... + N Log(N)

от http://en.wikipedia.org/wiki/Logarithm:

Логарифм произведения представляет собой сумму логарифмов факторов:

таким образом:

суммирование становится:

Log(1) + Log(2^2) + .. + Log(N^N)

дальнейшее упрощение:

Log(1*2^2*3^3*...*N^N)
0
По вопросам рекламы ammmcru@yandex.ru
Adblock
detector