algorithm - 条件语句的时间复杂度

假设第二个while循环应该读取while j<=n，时间复杂度为：

在）

决定因素正是k上的那个循环。

我们有：

i=1
while i<=n
    j=1
    while j<=n
        if i==j
            k=1
            while k<=j
                k+=1
                print("hello")
        else
            print("world")
        j*=2
    i*=2

这种情况i==j在外循环的每次迭代中只发生一次（其中i发生变化），并且可以独立于 j 的值，并在j上从循环中取出：

i=1
while i<=n
    j=1
    while j<=n
        if i!=j
            print("world")
        j*=2
    k=1
    while k<=i
        k+=1
        print("hello")
    i*=2

这会改变print输出的顺序，但这与确定时间复杂度无关。我们甚至可以进一步拆分：

i=1
while i<=n
    j=1
    while j<=n
        if i!=j
            print("world")
        j*=2
    i*=2

i=1
while i<=n
    k=1
    while k<=i
        print("hello")
        k+=1
    i*=2

所以现在对于第一个外部循环的一次迭代，它的内部 while 循环迭代logn次。该内部循环的每次迭代都需要恒定的时间。在一种情况下（当i等于j时），工作时间是恒定的，所以这个循环的时间复杂度为O(logn)-O(1) = O(logn) 。while

这使第一个外循环的时间复杂度为：

O(logn) * O(logn) = O((logn)²)

对于第二个外部循环的一次迭代，其内部 while 循环迭代i次，因此我们得到1 + 2 + 4 + 8 + ... + n的总迭代次数（当 n 是 2 的幂时），这是一个二进制扩展- 等于2(2 ^logn )-1 = 2n-1，时间复杂度为：

O(2n-1) = O(n)

对于整体时间复杂度，我们取总和，即

O((logn)²) + O(n) = O(n)。

插图

为了说明这种时间复杂度，请看一下这个实现，其中n在每次执行中都会增加，并且计算并返回工作单元。n与工作量之间的比率接近一个常数：

function work(n)  {
    var units = 0;
    var i=1
    while (i<=n) {
        var j=1
        while (j<=n) {
            if (i==j) {
                var k=1
                while (k<=j) {
                    k+=1
                    //print("hello")
                    units++;
                }
            } else {
                //print("world")
                units++;
            }
            j*=2
        }
        i*=2
    }
    return units;
}

// Demo
setTimeout(function loop(n=1) {
    var units = work(n);
    console.log(`n=${n}, work=${units}, ratio=${units/n}`);
    if (n < 100000000) setTimeout(loop.bind(null, n*2));
});

这只是一个例子，不能作为证明。

algorithm - 条件语句的时间复杂度

问题描述

解决方案

插图

推荐阅读