分析最坏情况的增长顺序 [英] Analyzing worst case order-of-growth

问题描述

对于这种算法，我正在尝试分析最坏的情况下作为N的函数的增长顺序：

I'm trying to analyze the worst case order of growth as a function of N for this algorithm:

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

我要分析的是<< c $ c> total ++ 将通过查看内部和外部循环来运行。内部循环应运行（N ^ 2）/ 2 次。我不知道外部循环。谁能指出我的正确方向？

What I'm trying is to analyze how many times the line total++ will run by looking at the inner and outer loops. The inner loop should run (N^2)/2 times. The outer loop I don't know. Could anyone point me in the right direction?

推荐答案

语句total ++;应该运行以下次数：

The statement total++; shall run following number of times:

= 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）。

The number of terms in the above expression = 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)

这篇关于分析最坏情况的增长顺序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！