姬長信(Redy)

算法-查找以下重复发生的复杂度:T(n)= T(n…


如何估算两个循环的运行时间,每个循环以对数时间运行,如下所示:

for(int i=n; i>=0; i /= 2)
{
    for( int j=i; j>=0; j /= 2)
    {
        count++;
    }
}

我的分析:

i = n  , 1  => j = lg n  | 1+lg (n) 
i = n/2, 1  => j = lg n/2 | 1+lg (n/2)
i = 1  , 1  => j = 0      | 1

在这种情况下,如何总结对数项?