2017-06-14 5 views
0

コードフラグメントの時間の複雑さに関するステップ数のカウントには助けが必要です。コードのステップ数をカウントする(時間の複雑さ)

total = 0 
    i = 0 
while i<3: 
    j=0 
    while j<3: 
     total = total + 1 
     j = j+1 
    i = i+1 
return total 

Iが述べ溶液有する:2 + 3 *(* 3 2 + 3 + 2)+2 = 43

= 0合計= 0とI上から最初の2行を、はい、私はそれらのそれぞれがそれぞれ1つのタイムステップであることを知っています。したがって、2を与えます。whileステートメントのために、私はそれがどのように取得されたかわからないので、< 3、その3タイムステップ? j = 0は1タイムステップです。

ここで私はそれを得ていません。ネストされたiループとjループがある場合、どのように時間の複雑さを判断するのですか?解決策では、*(複数)があることに気が付いています。誰かが私にとってより簡単な言葉でそれを打ち破ることができたら、私は感謝します。

答えて

1

時間の複雑さには議論が必要です。たとえば、O(n^2)です。

書かれているように、あなたの関数のどの部分が変更されるのか分かりませんので、定数O(1)です。

iと比較すると、この場合3が変わる可能性があるとします。あなたの機能と同じように、「私はそれぞれ3回jをする」その場合、変数を大きくするとループにさらに3つのステップが追加されます。つまり、複雑さはO(3n)のようになります。定数倍を取り除くことができるので、それはちょうどO(n)です。

私が書いたのは仮説です。それはあなたの機能に何が変わるかによって異なります。