- 内のステートメントは、ループ

Question

ながら、私はこの例を持っている場合は

A = 2,1,8,4,3,6 // c1, n 
n = 6 // c2, n 
i = 1 // c3, n 
H = 2 // c4, n 
inv = 0 // c5, n 
while H <= n // c6, n(n+1)/2-1    
    if A[i] > A[H] && !H = n // c7, n(n-1)/2 
     inv = inv + 1 
     H = H + 1 
    else if A[i] > A[H] && H = n // c10, n(n-1)/2 
     inv = inv + 1 
     i = i + 1 
     H = i + 1 
    else if A[i] < A[H] && !H = n // c14, n(n-1)/2 
     H = H + 1 
    else if A[i] < A[H] && H = n // c16, n(n-1)/2 
     i = i + 1 
     H = i + 1 
print inv // c19, n 

私の質問はどのように多くのn回意志内のコードステートメントは、この例で実行する場合は？

Answer 1

このコードを理解するために、いくつかの仮定がなされなければならない、まず：

1. アレイが1インデックス基づいており、即ち、第1の要素は、A [1]としてアクセスされます。
2. の要素はです。重複する値は使用できません。
3. 表現!H = nがHが

nと等しくないことを意味するループ条件はH < = Nあるので、これが偽になることができるとき見てみましょう。我々は、その限りとしてH < N確認でき

、反復は、一つ（第ifブロック内、または第三の中のいずれか）とHをインクリメントします。 HがNに到達

、Iをインクリメント（唯一その後）、及びHは、（第二又は最後ifブロック内）I + 1なります。 iは H iはHがnよりも大きい値を得ることができる唯一の方法である、再び 1 + に設定されNなり、その後う一点で

、その時点でループが停止します。

だから、他の言葉で、このループはn個にのn + 1から私はNに1から行く、とのそれらの値のそれぞれについて、私は、H実行します。 これは本当にタプル（I、H）範囲1からすべての可能なペアをとる... NI < Hを意味します。したがって、このペア数は、n（n-1）/ 2（C（n、2）とも呼ばれます）です。例えばN = 6で

ので、ペアの数（反復）が6（6-1）/ 2 = 15あります。

次のJavaScriptの実装では、ループカウンタが実際に15のカウント数に達したことを示しています

// Must add an element at index 0, since the 
 
// original code assumes 1-based indexing 
 
A = [null,2,1,8,4,3,6] // c1, n 
 
n = 6 // c2, n 
 
i = 1 // c3, n 
 
H = 2 // c4, n 
 
inv = 0 // c5, n 
 
loopCounter = 0 
 
while (H <= n) { // c6, n(n+1)/2-1    
 
    loopCounter++; // count it!! 
 
    if (A[i] > A[H] && H != n) { // c7, n(n-1)/2 
 
     inv = inv + 1 
 
     H = H + 1 
 
    } else if (A[i] > A[H] && H == n) { // c10, n(n-1)/2 
 
     inv = inv + 1 
 
     i = i + 1 
 
     H = i + 1 
 
    } else if (A[i] < A[H] && H != n) { // c14, n(n-1)/2 
 
     H = H + 1 
 
    } else if (A[i] < A[H] && H == n) { // c16, n(n-1)/2 
 
     i = i + 1 
 
     H = i + 1 
 
    } 
 
}   
 
console.log('inv = ', inv) // c19, n 
 
console.log('iterations = ', loopCounter)