算法时间复杂度分析？

Question

我正在尝试分析这个算法的时间复杂性，但我很难分解和计算最终循环将被执行多少次。虽然我知道第一个循环是 log(N)，但我似乎无法得出一个正确的总和。算法如下：

for(int i = 1; i <= n; i = 2*i){
    for(int j = 1; j <= i; j = 2*j){
        for(int k = 0; k <= j; k++){
            // Some elementary operation here.
        }
    }
}

最好直接给出答案，然后解释下思路

Answer 1

我个人理解总体是O(4n)，更准确一些来说应该是O(4n+lg2(n)*lg2(n)/2-lg2(n)/2)以下是具体论述。

单纯考虑

    for(int j = 1; j <= i; j = 2*j){
        for(int k = 0; k <= j; k++){
            // Some elementary operation here.
        }
    }

当给定i=x时，考虑其复杂度，假设为f(x)，由该程序段可以看出
\( f(x) = \sum_{tmp=0}^{m}(2^{tmp}+1) = 2^{m+1}+m-1 , 且 x = 2^{m}\)
所以有最终f(x)表达式为
\( f(x) = 2^{m+1} + m -1 = 2x + lg2(x) - 1 \)

再考虑整体

for(int i = 1; i <= n; i = 2*i){
    for(int j = 1; j <= i; j = 2*j){
        for(int k = 0; k <= j; k++){
            // Some elementary operation here.
        }
    }
}

假设\( N = 2^{k} \)
\( F(N) = \sum_{x=1}^{k}f(2^{x}) = \sum_{x=1}^{k}2^{x+1}+\sum_{x=1}^{k}lg2(2^{x})-k\)
最终有
\( F(N) = 2^{k+1} + lg2(2^{k*(k+1)/2}) -k \)
即

F(N) = 4N + lg2(N)(lg2(N)+1)/2 - lg2(N)

当然这里只是比较粗略的证明，因\( x=2^{m}和N=2^{x} \) 都只是特殊情况

用代码遍历从8到10000

import matplotlib.pyplot as plt
import math

def estimateComplexByN(n):

    lgval = math.log2(n)
    
    return 4*n + lgval*lgval/2 - lgval/2

def estimateComplexByNSimplified(n):
    return 4*n

actual = []
estimateAll = []
estimateSimplified = []

n_range = list(range(8,10001))

for n in n_range:
    val1 = 0
    
    i = 1
    while i<=n:
        j = 1
        while j<=i:
            k = 0
            while k<=j:
                k += 1
                val1 += 1
            j *= 2
        i*=2
    val2 = estimateComplexByN(n)
    val3 = estimateComplexByNSimplified(n)

    actual.append(val1)
    estimateAll.append(val2)
    estimateSimplified.append(val3)

plt.plot(n_range,actual, label='Actual')
plt.plot(n_range,estimateAll,label='4*n + lg2(n)*lg2(n)/2 -lg2(n)/2')
plt.plot(n_range,estimateSimplified,label='4*n')

plt.show()

只是比较粗略的想法，不一定对，欢迎沟通和交流