1

我正在尝试分析该算法的最坏情况增长顺序作为 N 的函数：

for (int i = N*N; i > 1; i = i/2)
     for (int j = 0; j < i; j++) {
           total++;
     }

我正在尝试total++通过查看内部和外部循环来分析线路将运行多少次。内部循环应该运行(N^2)/2时间。外环我不知道。谁能指出我正确的方向？

4

4 回答 4

2

语句总++；应运行以下次数：

= N^2 + N^2 / 2 + N^2 / 4 ... N^2 / 2^k
= N^2 * ( 1 + 1/2 + 1/4 + ... 1/2^k )

上述表达式中的项数 = log(N^2) = 2log(N)。

Hence sum of series = N^2 * (1 - 1/2^(2logN)) / (1/2)
                    = N^2 * (1 - 1/4N) / (1/2).

Hence according to me the order of complexity = O(N^2)
于 2014-09-15T12:08:11.237 回答
0

外部循环将以 log(N) 的复杂度运行，因为序列在每次迭代时减少到一半。例如二分查找。

于 2014-09-15T11:54:24.470 回答
0

对于这个问题，因为内循环取决于由外循环改变的变量的值（所以你不能简单地通过将内循环和外循环的值相乘来解决这个问题）。您将不得不开始在 a 中写入值，然后尝试找出系列，然后解决系列以获得答案..

就像你的问题一样，total++ 会运行..

n^2 + n^2/2 + n^2/2^2 + n^2/2^3 + .....

然后，取 n^2 个共同点，我们得到

n^2 [ 1 + 1/2 + 1/2^2 + 1/2^3 + ...]

解决这个系列得到答案

于 2014-09-15T11:56:01.803 回答
0

外循环运行准确2LOG (base 2) N + 1时间（浮点到整数转换并删除小数位）。如果您看到值像 N^2,N^2/2 , N^2/4 ... 1. .. 一样减小

所以总 ++ 运行的总次数是，

Summazion( x 从 0 到 int(2LOG (base 2) N + 1)) N^2/2^x

于 2014-09-15T11:58:19.590 回答