時間複雜度在Python - 大O符號

我的程序的輸出如下所示：時間複雜度在Python - 大O符號

[[1000, 1500, 2000, 2500, 3000, 3500, 4000], 
[437, 680, 917, 1115, 1476, 1668, 1912]]

這是通過numpy的圖書館創建的二維數組。第一行是我傳遞給函數的N的個數，第二行是以微秒（例如N = 1000時間= 437，N = 1500時間= 680）對這個函數進行時間測量。

是否有任何簡單的方法來確定哪個是這個函數的複雜性？我知道我可以繪製一個陰謀，只是看到這個，但我的應用程序需要給我的答案（你的功能是（當然可能）O（n）或O（n日誌n）或O（n^2））。 O（n）好像很明顯 - 我只需要將N/t分爲所有數組並檢查它是否是常量，但我不知道如何檢查另外兩個數組？

來源

2017-05-05 Kornelia

如果你在https://cs.stackexchange.com/上提出這個問題，你可能會有更好的運氣，因爲它確實與編程無關，但與計算機科學。 – DyZ

一個可以做各種花哨曲線擬合和模型評估與sklearn。但是對於一個簡單的方法來說，測量預期不變的事物對數的方差就可以了。也就是說，

採取比如T/N或T /（N *日誌（N）），或T/N ** 2。我們希望這是恆定的。
取該比例的對數，以消除縮放的影響。
計算數據點間的方差，用np.var。方差最小的模型勝出。

對於示例：

import numpy as np 
n = np.array([1000, 1500, 2000, 2500, 3000, 3500, 4000]) 
t = np.array([437, 680, 917, 1115, 1476, 1668, 1912]) 
print(np.var(np.log(t/n)))    # 0.001545... 
print(np.var(np.log(t/(n*np.log(n))))) # 0.001348... 
print(np.var(np.log(t/(n**2))))   # 0.18049...

所以它絕對不是二次。 N*log(N)比線性更適合。（嘗試其他的東西，看起來N*sqrt(log(N))是最好的。）

來源

2017-05-05 22:58:06 FTP

工作輝煌，謝謝 – Kornelia

時間複雜度在Python - 大O符號

回答

相關問題