# 算法时间复杂度分析

• 8

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.
}
}
}

1 个回答
young
• 77
✓ 已被采纳

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

$$f(x) = \sum_{tmp=0}^{m}(2^{tmp}+1) = 2^{m+1}+m-1 , 且 x = 2^{m}$$

$$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.
}
}
}

$$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)

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()


###### 你尚未登录，登录后可以
• 和开发者交流问题的细节
• 关注并接收问题和回答的更新提醒
• 参与内容的编辑和改进，让解决方法与时俱进