시간 복잡도

과제

1부터 n까지의 숫자의 합을 구하는 알고리즘 구현

• Algorithm A : n(n+1)/2 공식을 사용하는 방법
• Algorithm B : 1+2+…+n까지 더하는 방법
• Algorithm C : 0+(1)+(1+1)+(1+1+1)+…+(1+1+…+1) 모든 숫자에 대해 1씩 하는 방법

수행

// sum = n(n+1)/2
long long algorihmA(int n) {    
    long long sum = 0;    
    // TODO: implement Algorithm A
    sum = n * (n + 1) / 2;
    return sum;
}

// sum = 1+2+…+n
long long algorihmB(int n) {
    long long sum = 0;    
    // TODO: implement Algorithm B
    for(int i = 1; i <= n; i++)
    {
        sum += i;
    }

    return sum;
}
//sum = 0+(1)+(1+1)+(1+1+1)+…+(1+1+…+1)
long long algorihmC(int n) {    
    long long sum = 0;
    // TODO: implement Algorithm C
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j < i; j++)
            sum += 1;
    }
    return sum;
}

Algorithm A

// sum = n(n+1)/2
long long algorihmA(int n) {    
    long long sum = 0;    
    // TODO: implement Algorithm A
    sum = n * (n + 1) / 2;
    return sum;
}

• 주어진 n에 대해 n * (n + 1) / 2 공식을 통해 수열의 합을 구함
• n의 할당과 연산까지 2번의 연산을 거침
• n의 크기에 관계없이 1번의 연산이 이루어지는 O(1)의 시간복잡도를 가짐

Algorithm B

// sum = 1+2+…+n
long long algorihmB(int n) {
    long long sum = 0;    
    // TODO: implement Algorithm B
    for(int i = 1; i <= n; i++)
    {
        sum += i;
    }

    return sum;
}

• 1부터 n까지의 숫자를 차례대로 더하여 수열의 합을 구함
• n의 할당과 덧셈 연산까지 2n번의 연산을 거침
• 입력받은 n의 크기만큼 연산을 반복하는 O(n)의 시간복잡도를 가짐

Algorithm C

//sum = 0+(1)+(1+1)+(1+1+1)+…+(1+1+…+1)
long long algorihmC(int n) {    
    long long sum = 0;
    // TODO: implement Algorithm C
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j < i; j++)
            sum += 1;
    }
    return sum;
}

• 1부터 n까지의 숫자를 차례대로 연산을 실시하나 그때의 i의 값 만큼 1을 더하는 것을 반복하여 수열의 합을 구함
• n의 할당과 덧셈 연산까지 2n^2번의 연산을 거침
• 이중 반복문을 사용해 n만큼의 연산을 실시하므로 O(n^2)의 시간복잡도를 가짐

결과

• 같은 기능을 수행하는 알고리즘 중에서도 여러 시간 복잡도를 가진 방법이 사용될 수 있음
  O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(n^3)
  < ... < O(n^k) < O(2^n) < ... < O(n!)
• 시간 복잡도가 클 수록 n이 커졌을 때 전체 알고리즘이 실행되는 시간이 길어지므로 효율적이지 못함
• 시간 복잡도가 n^2 + n + 1인 알고리즘이 있다고 할 때 n이 커질 수록 가장 큰 차수인 연산의 영향력이 커지므로 해당 알고리즘의 시간 복잡도를 표기할 때 가장 큰 차수인 O(n^2)으로 표기
• O(n)은 최악의 경우를 표시하며 Ω(n)은 가장 유리한 케이스를, 평균적인 경우는 θ(n)으로 나타낼 수 있음
  Ex) 정렬 알고리즘에 있어 최적의 경우 : 이미 정렬되어 있어 전체를 순회하는 것 외에 다른 조치가 필요하지 않은 경우 n회의 연산만이 필요