如何處理找到任何算法

Question

所有，

的大O /時間複雜度我一直覺得自己是值得懷疑的，當談到找到一個給定的代碼/算法的複雜性。防爆。

FOR I=1 TO N 
do J=1 
WHILE J*J < I 
do J=J+1 

上面的代碼具有時間的Big Theta (N^(3/2))複雜性。但是，我不明白答案是如何得出的。

任何人都可以請指導我找到複雜的步驟或任何可以幫助我的具體資源嗎？大部分的時間，我只能找到代碼的複雜性N, lg N , N lg N和N^2

Answer 1

的方法始終是相同的：工作有多少業務正在爲ñ的函數執行，然後扔掉低階項和常量。

在你上面的例子

因此，內循環迭代大約SQRT（I）倍，所以我們有（約）SQRT（1） + SQRT（2） + SQRT（3） + ...結果是一個函數，其最高階項是N ^（3/2）。