嵌套循环的复杂度除以 2

Question

我正在尝试使用大 O 表示法计算出 for 循环的复杂性。我以前在其他类(class)中也这样做过，但是这门类(class)比其他类(class)更严格，因为它是基于实际算法的。代码如下:

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 符号的步骤:

此外，请看一下这个非常有趣的最后一张幻灯片 document作者:Jauhar 博士。