시간 계산 복잡성?

Question

거품 정렬 인이 정렬 코드는 있지만이 코드는 정확히 O (N^2)가 아닌 것 같습니다. 아래의 코드에서 Big O의 관점에서 시간 계산상의 복잡성이 무엇인지 궁금합니다. 내 추측으로 그것은 O (N.logN)입니다.

코드는 그대로 예제로 제공되며 그대로 컴파일 할 수 있다고 주장하지 않습니다. 그것을 추측 내

for(i = 0; i < n-1; i++) 
{ 
    for(j = 0; j < n-i-1; j++) 
    { 
     if (a[j+1] < a[j]) 
     { 
      temp = a[j]; 
      a[j] = a[j+1]; 
      a[j+1] = temp; 
     } 
    } 
} 

Answer 1

는 O (N.logN)입니다.

왜 그런가? 실제로 일어나는 일을보세요 ...

외부 루프를 처음 사용하면 i == 0입니다. 즉, j의 범위는 0에서 n-1입니다.

두 번째로, i == 1이므로 j의 범위는 0에서 n-2입니다.

세 번째로 i == 2이므로 j는 0에서 n-3까지입니다.

는 ...

통해 지난번 내가 == N-1, 그래서 j는 0 내지 따라서 0

범위

, 동작의 총 개수는 N-1 + N-2 + n-3 + ... + 0

Σi, i = 0..n-1은 무엇인가? 이제 큰 O 바인딩으로 변환하십시오.