对于复杂的嵌套循环除以2 [英] Complexity for nested loops dividing by 2

问题描述

我试图找出的复杂性，使用大O符号循环。我以前在我的其他类做到了这一点，但是这一次是比别人更严格，因为它是在实际的算法。在code是如下：

I am trying to figure out the complexity of a for loop using Big O notation. I have done this before in my other classes, but this one is more rigorous than the others because it is on the actual algorithm. The code is as follows:

for(i=n ; i>1 ; i/=2) //for any size n
{
    for(j = 1; j < i; j++)
    {
      x+=a
    }
}

我已到达该第一循环是O（log_2（正））。至于第二个循环，我有点失落！感谢您的分析帮助。

I have arrived that the first loop is of O(log_2(n)). As for the second loop I am a little lost! Thank you for the help in the analysis.

推荐答案

要正式解决了你的算法的时间复杂度，可以使用适马符号以下步骤：

To formally solve the your algorithm's time complexity, you may used the following steps with Sigma notation:

此外，看一看这个非常有趣的文档的最后一张幻灯片通过Jauhar博士。

Also, take a look a the last slide of this very interesting document by Dr. Jauhar.

这篇关于对于复杂的嵌套循环除以2的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！