비 - 큰 O 복잡도

나는 알고리즘의 복잡도 계산에 매우 혼란 스럽다. 한 과제에 대해 우리는 다음과 같은 기능을 부여 받고 그 복잡성을 발견하도록 요청 받았다.비 - 큰 O 복잡도

int selectkth(int a[], int k, int n) { 
    int i, j, mini, tmp; 
    for (i = 0; i < k; i++) { 
     mini = i; 
     for (j = i+1; j < n; j++) 
     if (a[j]<a[mini]) 
      mini = j; 
     tmp = a[i]; 
     a[i] = a[mini]; 
     a[mini] = tmp; 
    } 
    return a[k-1]; 
}

할당 자체는 "정수의 순서화 된 배열의 K 번째 최소의 정수를 찾기 위해 사용되는 기능의 복잡성을 찾는다."하라는

또한 f 함수와 g 함수를 작성해야합니다.

내가 이해 한대로 f 함수의 경우 모든 할당과 함수를 함수에 추가합니다. 이 f 함수에 k 또는 n 변수를 포함합니까?

가장 좋은 추측으로, 첫 번째 for 루프에서 반복되는 6 개의 연산이 있으므로 중첩 된 for 루프에서 4 번의 연산이 수행되므로 f (n) = 6n + 4 (n^2)라고 말하고 싶습니다. .

이 함수의 Big O 복잡도는 O (n^2)가 될까요? 중첩 된 for 루프가 있고 매번 모든 항목을 통과하는 최악의 시나리오를 의미하기 때문에 그렇게 말합니다.

나는 명확하지 않다면 사과드립니다. 나는 이것이 어떻게 작동하는지 매우 혼란 스럽다.

출처

2014-10-09 wpaverd

을 당신이 올바른지 두 개의 중첩 루프'의미 O 것을 (N^2)', IMO의 정확한 수를 표시하는 방정식을 마련하려고 명령어는 하나 이상의 CPU 명령어가 될 것이고 일부는 컴파일러에 의해 최적화 될 것이기 때문에 어리석은 짓이다. – IllusiveBrian

두 개의 중첩 루프가 반드시 'O (n^2)'를 의미하지는 않습니다. 여기서 외부 루프는 0에서 k-1로 이동하며, 이는 O (n^2) 대신에 'O (kn)'로 이어질 가능성이 높습니다. (나는 공식적인 증명없이 추측하기 때문에 "가능하다"라고 말합니다.) 변수에 대해 정확해야하고 생각 프로세스를 항상 "2 루프 = 2 차 = O (n^2)"로 단순화하는 것이 중요합니다. –

내부 루프는'(n-1) + (n-2) + ... + (n-k)'번 실행되며, 분명히'O (kn)'입니다. –

여기 간단한 분석을 진행한다 :

외부 루프는 k 반복하고있다.

인터 루프는 n-1 반복을 수행하지만 그 값은 k 회입니다.

그래서 우리 (우리는 어레이 내에 n 번째 가장 작은 정수를 요청할 수 있음) 식을 O(n*n-n) = O(n^2-n) = O(n^2) becames O(k*(n-1)) = O(kn-k) k 때문에 n가 동일 할 수있다.

큰 O 표기법 표기에 대한 자세한 도움말을 보려면 체크 아웃 : http://web.mit.edu/16.070/www/lecture/big_o.pdf

출처

2014-11-24 04:17:00

비 - 큰 O 복잡도

답변

관련 문제