我正在嘗試分析演算法的時間復雜度。
下面的演算法僅用于檢查陣列的一部分，因此如果它沒有多大意義，請不要擔心。
我對計算回圈的時間復雜度感到非??常困惑，請查看我的評論。
def search(key,arr)
N = arr.length C1
for 0 <= i < ceiling(N/2) C2*N C3 - ceiling can be considered a constant.
if(arr[i] == key): C4*N -- Assuming this because its inside the loop?
return 2*i C5*N -- N because of the loop?
return "Not found" C6
這是否意味著我們有：
T(N) = (C2 C4 C5)N (C1 C3 C6)
T(N) = C7*N (C8)
T(N) = N??
回圈中的所有內容總是 *N？
提前致謝！
uj5u.com熱心網友回復：
你的計算是正確的。這是一個O(n)演算法。
但是你不能說回圈中的所有東西都是 times N。考慮以下示例：
for i == N; i >= 0; i /= 2:
... do some constant stuff
這顯然是 中的對數N，因為我們i在每次迭代中減半。
關鍵是您的變數如何接近回圈邊界。如果它以恒定的步長遞增/遞減。然后是線性的。但如果涉及其他一些操作，則需要考慮到這一點。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/387607.html
上一篇：Java中的回圈佇列實作