數據結構算法的時間復雜度

按照分析慣例，假設所有單壹運算的時間復雜度均為1

x=n; ......1

while(x>=(y+1)*(y+1)) ......4(兩次加法、1次乘法、1次比較)

y=y+1 ......1

時間復雜度 = 1 + (4 + 1) x 循環次數

循環次數是由n和y的初始值決定的，假設循環次數為N，y的初始值為y0，y的結束狀態為yn，有

x < (yn + 1)*(yn + 1) ......假設y的初始值為整數，則yn為滿足該式的最小整數

N = (yn - y0) / 1 ......因為每次循環y的遞增量為1

1式簡化為 x = (yn + 1)*(yn + 1)，可得：yn = n^(1/2) - 1

所以N = n^(1/2) - 1 - y0

采用大O表示法，僅考慮最高次項，則求N的復雜度為O(n^(1/2))

進而求得妳這3行代碼的

總體復雜度 = 1 + (4 + 1) x O(n^(1/2))

由於已知的常數項及非最高次項通常會被忽略（大O精神），所以總時間復雜度為O(n^(1/2))

上一篇:波音公司的主流三維軟件是什麽?

下一篇:大家的實驗室買的球磨機是什麽牌子