[C] Running time and Asymptotic complexity ::: 시간복잡도(정확한 수행시간 및 점근적 표기)

 

---

까다로운 부분 알아가기

---

[1] C코드는 Pseudocode에 주어진 그대로 수행을 하면 되기 때문에 설명할 것이 없다.

 

[2] 문제에서 Exact running time T(n)을 구하라고 하면 cost와 수행횟수를 나타내는 표를 그린다. 각 코드 한줄마다 cost는 c1,c2,c3...식으로 달아주고, 수행횟수를 계산해서 넣어준다. 그 후 cost와 수행횟수를 코드 한줄마다 곱해서 전부 더해준다.

 

[3] Asymptotic complexity는 점근복잡도이기 때문에 최고차항을 나타내면 된다.

---

답안 및 출력결과

---

a) 내림차순으로 정렬하면서 가장 큰 원소부터 k번째 가장 큰 원소까지의 합계를 반환한다.

 

b)

#include <stdio.h>

int whatIDo(int A[],int n, int k){
    int sum=0;
    int i,j,maxi,swp;
    for(i=0;i<k;i++){
        maxi=i;
        for(j=i+1;j<n;j++){
            if(A[j]>A[maxi]){
                maxi=j;
            }
        }
        sum=sum+A[maxi];
        swp=A[i];
        A[i]=A[maxi];
        A[maxi]=swp;
    }
    return sum;
}
int main(){
    int n;
    printf("How many integers? ");
    scanf("%d",&n);
    int A[n],i;
    printf("Input integers: ");
    for(i=0;i<n;i++){
        scanf("%d",&A[i]);
    }
    int k;
    printf("Sum up to: ");
    scanf("%d",&k);
    printf("%d",whatIDo(A,n,k));
    return 0;
}

c)

d)

Best case : 전부 이미 내림차순 정렬되어 있어서 if 조건문이 한번도 수행이 되지 않으며 1번째 원소까지만 합계를 구하는 경우이다. 즉, 위의 하늘색 동그라미 α(알파)=0, k=1인 경우이다. 이를 T(n)에 대입해보면,

따라서, Best case의 Asymptotic complexity는

Worst case : 전부 오름차순 정렬되어 있어서 if 조건문이 최대로 수행이 되어야 하며 마지막 원소까지의 합계를 구하는 경우이다. 즉, α(알파)=1, k=n인 경우이다. 이를 T(n)에 대입해보면,

따라서, Worst case의 Asymptotic complexity는

e) 위의 Best case처럼 k=1이면, linear complexity를 가진다. 하지만 k가 n에 가까워질수록 k~n quadratic complexity를 가지게 된다. 즉, k값이 클수록 cost가 커진다.

 

f) 

1. Empty array인 경우, 즉, n=0, A=[ ].

2. k=0인 경우, for loop자체를 들어가지 못하고 끝난다.

3. k>n인 경우, 수행은 되지만 이상한 결과값을 반환한다.