- 내부 문 루프

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 인덱스, 즉 첫 번째 요소는 A와 액세스 기반 [1]한다.
2. 의 요소는이며 중복 값은 허용되지 않습니다.
3. 발현 !H = n는 H 루프 조건 < H = N 인 N

동일 아니므이 거짓이 될 수있을 때 보자 의미한다.

우리만큼 H < N와 같은 반복 H를 증가 것이라고 볼 수 하나 (하나 제 if 블록 또는 세 번째).

H N 는 난이 (그래야만 등) 증가 도달하고, H은 (두 번째 또는 마지막 if 블록) I + 1된다.

한순간 에서 나는N 다음 H가 설정 될 될 것이다 내가보다 N 인 값을 얻을 수있는 유일한 방법 H이다 다시 + 1,, 그 시점에서 루프가 중지됩니다.

그래서, 즉,이 루프 내가 N 1 내지 가서 N-N + 1에서 I 들 값 H 실행마다 한다. 이 정말 튜플 (I, H)는 범위(1)로부터 모든 가능한 쌍을 얻어 ... N I < H를 의미한다. 따라서이 쌍의 수는 n (n-1)/2 (C (n, 2)이라고도 함)입니다. 예 N = 6이므로 쌍의 수 (반복)에서

는 6 (6-1)/2 = 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)