알고리즘의 기본 - 시간복잡도

2022.03.11 - [개발/알고리즘] - 알고리즘을 공부하기 위한 기초지식 (자료구조)

알고리즘을 공부하기 위한 기초지식 (자료구조)

이어지는 포스팅입니다.

 

목표

• 알고리즘의 정의를 이해한다.
• 알고리즘 설계기법의 종류를 나열한다.
• 알고리즘 시간 복잡도의 의미와 계산법을 알아본다.
• 점근 성능의 표기법의 종류와 개념을 이해하고 적용할 수 있다.

목차

• 알고리즘의 정의와 설계
• 알고리즘 분석 (시간 복잡도, 빅오 표현법)
• 순환 알고리즘의 성능
• 참고

---

알고리즘의 정의와 설계

 알고리즘이란 문제를 풀기 위한 1개 이상의 명령어의 나열이며, 다음 특성을 가집니다.

 

• 입출력 : 0개 이상의 외부 입력, 1개 이상의 출력
• 명확성 : 명령은 모호하지 않고, 명확하게
• 유한성 : 명령이 끝난 후 종료
• 유효성 : 컴퓨터에서 명령이 수행 가능해야 함
• 효율성 

 

설계기법

 위 특성들로 알고리즘을 설계하나 이 설계에 영향을 주는 환경은 너무나도 다양합니다. 따라서 범용적으로 가장 효율적인 설계기법은 존재하지 않습니다. 그러나 대표적인 알고리즘 설계기법들은 있습니다.

 

• 분할 정복 방법
• 동적 프로그래밍 방법
• 욕심쟁이 방법

---

알고리즘 분석 (시간 복잡도, 빅오 표현법)

 분석 시에는 크게 정확성과 효율성을 분석합니다. 정확성은 입력에 대하여 정확한 결과를 생성하는지를 분석하는데 이때는 수학적 기법들을 이용하여 이론적인 증명이 필요합니다.

 효율성을 분석할 때는 알고리즘 수행 시 필요한 자원 (메모리, 수행 시간)의 양을 분석합니다. 메모리의 양은 공간 복잡도를 나타내고,  수행 시간은 시간 복잡도를 나타냅니다.

 

시간 복잡도

 시간 복잡도란 알고리즘을 수행하기 위해 프로세스가 수행하는 연산을 함수로 나타내는 것입니다.  시간 복잡도를 계산하는 첫 번째 단계는 알고리즘의 단위 연산 수행 회수를 합하여 간단한 방정식으로 나타내는 겁니다.

 

 아래와 같이 배열의 전체 요소를 출력하는 메서드가 있다고 가정합니다.

public static void printArray1(int[] arr) {
    int n = arr.length; // 1번

    for (int i = 0; i < n; i++) { // n 번
        System.out.println("i : " + arr[i]); // n 번
    }// n 번

}

각 명령들이 몇 번 시행되는지 옆에 주석으로 표기했습니다. 각 명령 하나하나가 단위 연산들입니다. 이 단위 연산들의 시행 회수를 모두 합하면 3n+1이 됩니다.

 

N X N 2차원 배열을 출력하는 메서드를 보겠습니다.

public static void printArray2(int[][] arr) {
    int n = arr.length; // 1번

    for (int i = 0; i < n; i++) { // n번
        int[] inArr = arr[i]; // n번

        for (int j = 0; j < n; j++) { //n*n번
            System.out.println(inArr[j] + " "); //n*n번
        } //n*n번

    } //n번

}

 

3n^ + 3n + 1입니다.

 이렇게 구한 수식을 점근 성능을 이용한 점근적 표기법으로 표현합니다. 점근 성능이란 입력 데이터의 크기 n이 무한히 커짐에 따라 결정되는 성능입니다.  왜 점근 성능을 이용할까요? 아래 표를 보면 쉽게 알 수 있습니다.

 

복잡도	1	10	100
1	1	1	1
log N	0	2	5
N	1	10	100
N log N	0	20	461
N^2	1	100	10000
2^N	1	1024	1267650600228229401496703205376
N!	1	3628800	표기 불가

 표를 보면 데이터가 무한히 커짐에 따라 복잡도에 따라서 그 결과 값은 엄청난 차이를 보이게 됩니다. 따라서 복잡도를 표현할 때에는 점근 성능을 이용하여 다음과 같이 세 가지로 표현 가능합니다.

 

• 최상의 경우 : 오메가 표기법 (Big-Ω Notation)
• 평균의 경우 : 세타 표기법 (Big-θ Notation)
• 최악의 경우 : 빅오 표기법 (Big-O Notation)

 

 또한 점근 표기에는 계수를 제거한 최고차항만을 이용합니다. 마찬가지로 데이터의 개수(n)가 계속하여 증가하면 최고차항을 제외한 부분이 결과값에 영향을 거의 끼치지 못하기 때문입니다. (위 표 참고)

 계수를 제거한 최고차항만을 이용하여 표기하는 점근 표기가 왜 의미가 있을까요? 이유는 알고리즘의 추세를 파악하기가 용이하기 때문이고, 그에 따라서 알고리즘 간의 우열을 판가름할 수가 있습니다. 이제 점근적 표기법을 이용하여 시간 복잡도를 표현해보겠습니다.  

 

오메가 표기법 (Big-Ω Notation) : 점근적 하한 (최상의 경우)

 알고리즘 성능이 같거나 더 나쁜 함수들의 집합입니다. 알고리즘 성능의 최상의 경우를 기준으로 나타내는 표기법입니다. 풀어서 "나의 알고리즘이 제일 좋아봤자 이보다 좋을 수는 없다"는 뜻입니다.  그래프로 나타내면 아래와 같습니다.

 

 

빅오 표기법 (Big-O Notation) : 점근적 상한 (최악의 경우)

 알고리즘 성능이 같거나 더 좋은 함수들의 집합입니다. 알고리즘 성능의 최악의 경우를 기준으로 나타내는 기법입니다. 풀어서 "나의 알고리즘이 아무리 나빠져봤자 이보다 나빠질 순 없다"는 뜻입니다. 그래프로 나타내면 아래와 같습니다.

 

 세타 표기법 (Big-θ Notation) : 점근적 상하한(평균의 경우)

 알고리즘의 평균적인 성능을 나타내는 표기법입니다.

 

점근 성능 표기 예시

 

n0=2, c=11 이면 n>=2 일 때 3n+5 <= 11 * n 이므로 f(n) = O(g(n)) = O(n)

n0=1, c=3 이면 n>>=1일 때 3n+5 >= 3 * n 이므로 f(n) = O(g(n)) = Ω(n)

f(n)=O(n), f(n)=Ω(n) 이므로 f(n)=θ(n)

 

 시간 복잡도 간의 크기 비교는 빅오 표기법에 의해 다음과 같은 대소 관계를 가집니다.

출처 : https://www.bigocheatsheet.com

 

알고리즘 시간 복잡도 구하기 (빅오 표현법)

1. 알고리즘의 수행 시간 판단 f(n)
2. f(n) = O(g(n))을 만족하는 함수 g(n)  판별 (계수를 제거한 최고차항)

---

순환 알고리즘 

 재귀 알고리즘이라고도 합니다. 알고리즘 도중에 본인 알고리즘을 다시 수행하는 알고리즘입니다. 간단한 예시입니다.

public static void main(String[] args) throws Exception {

    printHelloJava(5);

}

private static void printHelloJava(int printTime) {

    if(printTime == 0){
        return;
    }

    System.out.println("HELLO JAVA");
    printHelloJava(--printTime);
}

 

---

참고

 

https://ko.wikipedia.org/wiki/%EC%B5%9C%EC%84%A0,_%EC%B5%9C%EC%95%85,_%EA%B7%B8%EB%A6%AC%EA%B3%A0_%ED%8F%89%EA%B7%A0%EC%9D%98_%EA%B2%BD%EC%9A%B0

 

최선, 최악, 그리고 평균의 경우 - 위키백과, 우리 모두의 백과사전

 

https://www.bigocheatsheet.com/

Big-O Algorithm Complexity Cheat Sheet (Know Thy Complexities!) @ericdrowell