2

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)？谢谢你。

4

4 回答 4

1

计算复杂度的正确方法是评估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]。

于 2013-06-06T12:12:15.947 回答
0

我同意N^2*log2(N)排序算法运行 N 次。在 Big-O 中，其中c是一个常数：

c*N * N*log2(N) => O(N^2*log2(N))
于 2013-06-06T12:00:49.560 回答
0

它将渐近 O((N^2)*(log2(N))

we need sum of k*log2(k) k from 1 to N
于 2013-06-06T12:14:39.907 回答
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)
于 2013-06-06T11:59:09.137 回答