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)?
Спасибо.
Правильный способ вычислить сложность состоит в том, чтобы оценить сложность повторного 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]
,
Я бы согласился с N^2*log2(N)
так как алгоритм сортировки выполняется N раз. В Биг-О, где c
является константой:
c*N * N*log2(N) => O(N^2*log2(N))
Это будет асимптотически O ((N ^ 2) * (log2 (N))
we need sum of k*log2(k) k from 1 to N
Вы суммируете логарифмические функции:
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)