なぜwhileループは時間の複雑さ全体にO（n）を寄与しないのですか？

Question

私はInterview Bit

問題からこの問題を得た

int j = 0; 
for(i = 0; i < n; ++i) { 
    while(j < n && arr[i] < arr[j]) { 
     j++; 
    } 
} 

whileループがないことを、比較の合計数は、おそらくn以下のn（約ある質問arrによる）。ループはn回実行されます。時間の複雑さはO（n^2）でなければならないのですか？

Answer 1

whileループの条件の1つはwhile j < nです。意味が最悪の場合、ループはループが何回ループするかにかかわらず（jはゼロから始まり、増加するだけでゼロにリセットされないか、または減少する）、whileループn回でループします。私達はちょうどランタイムは、最悪の場合にはどうなるか検討しているので、あなたが安全に、他の条件arr[i] < arr[j]を無視することができます：forループもn回ループするので、あなたのbig-OはO(n+n) => O(n)

NOTEです。

Answer 2

このコードは意図的に誤解を招くように設計されているようです。 whileループは、0からnに1回だけ実行され、外側のループの繰り返しごとにリセットされません。

Answer 3

あなたは最も内側のループ内の文を実行します合計回数をカウントする必要があります。

それは、これらの値からステップは、外側のループの異なる反復の間に分散することができるにもかかわらず、一度だけn-1に0の間の値を通過するためのネストされたwhileループが複雑に寄与しません。

ループの最も内側の「ペイロード」、すなわちarr[i] < arr[j]とj++、jをインクリメントすると、「一方通行」であるので、最大でn回実行されます。その値がゼロにリセットされることはありません、j達するとそうn、ループの本体がもう実行されません。

Answer 4

実際、内側のループは 'i'に依存しないので、 'i'が0からn-1になると最大n回実行されます。

前回のループでは 'j'は0で初期化され、次に最悪の場合は 'i'ループでは1 + 2 + 3 + .....が実行されます。 ..n-2 + n-1回= O（n^2）です。