アルゴリズムのBig O/Timeの複雑さを見つける方法

Question

すべて、

与えられたコード/アルゴリズムの複雑さを見つけることは常に疑問に思っています。 Ex。

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

上記のコードの時間複雑度はBig Theta (N^(3/2))です。しかし、私は答えがどのように導き出されたのか理解していません。

誰でも私を助けることができる複雑さや特定のリソースを見つけるための手順に私を導くことができますか？ Nの関数として実行されているどのように多くの操作をうまくして、離れた低次項を投げると：時間のほとんどは、私は複雑N, lg N , N lg NとN^2

Answer 1

アプローチは常に同じであるとのコードを見つけます定数。上記のあなたの例ではそう

、内側のループが繰り返さ約SQRT（I）回、私たちは（1） + はsqrt（約）SQRT（2） + はsqrt（3） +を持っています...結果は、最高次項がN ^（3/2）である関数です。