2

std::sort は、要素 (ソース - http://www.cplusplus.com/ )のおよそ N*log2(N) (N は距離) の比較を実行するため、その複雑さは 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

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 に答える