Python源代碼如下:
import time
import matplotlib.pyplot as plt # 制圖的類別庫,匯入模塊pyplot,并指定其別名為plt
import numpy as np
n = [0]
time_run = [0]
def boem(a):
n = len(a)
k = 2
while k <= n:
b = 0
while b < n:
d = k >> 1
while d > 0:
# for j in range(0 if d == k >> 1 else d, k-d, d << 1):
# j = 0 if d == (k >> 1) else j = d
if d == k >> 1:
j = 0
else:
j = d
while (j + d) < k:
i = 0
while i < d:
u = b + j + i
v = u + d
if ((u < n) and (v < n)):
if a[v] < a[u]:
# a[u],a[v] = a[v],a[u]
a[u] = a[v] + a[u]
a[v] = a[u] - a[v]
a[u] = a[u] - a[v]
i += 1
#d >>= 1
j += d << 1
d >>= 1
b += k
k <<= 1
for len_n in range(0, 1000):
a = list(range(0, len_n))
start = time.clock()
boem(a)
end = time.clock()
n.append(len(a))
time_run.append(end - start)
plt.plot(n, time_run, 'g-h') # x、y軸與曲線顏色
plt.legend() # 給圖加上圖例
plt.title(r"running time varies with n")
# plt.show()
x = np.arange(0, 1000, 1)
y = np.log2(x) ** 2 * x * x
plt.plot(x, y, 'r')
plt.show()
這個代碼是我根據下圖所示代碼所轉換的:
我手動計算出來的時間復雜度是O(logn*logn*n*n)
但我的時間復雜度函式與原始碼的運行時間不吻合，運行的圖片類似下面的曲線圖
請問是哪里出了問題，該怎么處理?
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/142267.html
上一篇：LAMP平臺部署及論壇搭建