嵌套循环的复杂度除以2

我试图找出使用Big O表示法的for循环的复杂性。 我之前在其他课程中已经完成了这个，但是这个比其他课程更严格，因为它是在实际的算法上。 代码如下：

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

我到了第一个循环是O（log_2（n））。 至于第二个循环，我有点迷路！ 感谢您在分析中提供的帮助。

Answer 1

要正式解决算法的时间复杂度，可以使用以下步骤使用Sigma表示法：

另外，看看Jauhar博士这篇非常有趣的文件的最后一张幻灯片。

Answer 2

内环的迭代总数是n + n / 2 + n / 4 + … + 1，约为2n。 所以复杂性是O（n）。

Answer 3

复杂性应该是O(n) 。 它形成几何系列（不完全但近似）。

该循环运行n+ n/2 + n/4 + .... +1 ，约为2n 。

并且O(2n) = O(n) 。