시간 복잡도 & 빅오표기법

친구를 만나기 위해 약속 장소를 찾아가는 상황을 생각해보자.  나머지 비용은 같다는 가정하에 목적지까지 1시간이 걸리는 경로와 30분이 걸리는 경로가 있다면 30분이 걸리는 경로를 선택할 것이다. 우리에게 시간은 소중하기에 효율적으로 사용하기 위한 노력을 의식적으로 하고 있는 것이다.컴퓨터 프로그래밍도 마찬가지다. 어떤 경로를 통해 약속장소로 가는 과정을 컴퓨터 프로그래밍에선 알고리즘이라고 말한다. 이때 도출할수 있는 여러 과정 중에 가장 빠르게 수행할 수 있는 알고리즘을 선택한다면 더 좋은 프로그램을 만들 수 있을 것이다.

알고리즘(Algorithm)

• 어떠한 문제를 해결하기 위한 여러 동작들의 모임
• [알고리즘에 관한 더 자세한 설명[위키피디아\]]: https://ko.wikipedia.org/wiki/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

알고리즘 - 위키백과, 우리 모두의 백과사전

좋은 알고리즘의 분석기준 중에서는 복잡도가 있다. 우리는 복잡도가 낮은 알고리즘을 우선적으로 사용하게 된다.

복잡도에는 시간 복잡도와 공간 복잡도가 있는데 공간복잡도는 간단히 말하면 알고리즘이 실행될 때 사용되는 메모리의 양을 의미한다. 요즘에는 데이터를 저장할 수 있는 메모리의 발전으로 중요도가 낮아졌다.

이번에는 시간복잡도를 자세히 다루고 공간 복잡도는 다음에 필요하면 다시 다루겠다.

시간 복잡도란?

• 알고리즘의 성능을 설명하는 중요한 지표
• 알고리즘을 수행하기 위해 프로세스가 수행되어야 하는 연산을 수치화한 것
• 실행시간이 아니라 연산수 치로 복잡도를 판별하는 이유는 명령어의 실행시간은 컴퓨터의 하드웨어 또는 프로그래밍 언어에 따라 편차가 크게 달라지기 때문에 명령어의 실행 횟수만을 고려하는 것이다.

왜 필요할까?

어떠한 문제를 해결하기 위해 자신이 세운 알고리즘의 시간이 얼마나 걸리는지를 알 수 있어야 한다.

시간 복잡도의 표기법

1. 빅오 표기법 O(BigO) : 시간의 상한 값 t <=∞ (최악의 값)
2. 세타 표기법 θ(Theta) : 시간의 상한 값과 하한 값의 사이 t (평균값)
3. 오메 가표 기법 Ω(Omega) : 시간의 하한 값 t>=1 (최상의 값)

어떤 표기법을 사용해야 할까?

빅오 표기법(Big-O) 표기법

 

평균을 나타내는 세타 표기법이 가장 이상적이고 정확하지만, 도출하기가 상대적으로 어렵다. ​ 빅오 표기법을 통해 알고리즘의 최악의 경우를 판단하면 평균과 가까운 성능의 예측이 가능하다. ​ 그리고 최악의 값(제일 오래 걸리는 시간)이 최상의 값(젤 빨리 실행되는 시간)을 판단하는 것보다 안전하기 때문이다.

시간 복잡도 계산법

가장 큰 영향을 끼치는 n의 단위를 구해야 한다(n의 크기가 증가할수록 작은 차수는 영향이 약해진다).

1                  O(1)    -> 상수

2n + 4             O(n)    -> n이 가장 큰 영향을 끼침

2n^2 + 4n          O(n^2)  -> n^2가 가장 큰 영향을 끼침

흔한 빅 오식

O(1) < O(1og n) < O(n) < O(n log n) < O(n^2) < O(C^n) [성능(수행 시간, 연산 횟수)]

O(1) //상수형, 데이터 수에 상관없이 '연산횟수가 고정'인 유형의 알고리즘을 뜻한다 

O(1og n) //로그형, '데이터수의 증가율'에 비하여 '연산횟수의 증가율'이 훨씬 낮은 알고리즘 ex)이진탐색, 정렬알고리즘

O(n) //선형, 데이터 수와 연산횟수가 비례하는 알고리즘

O(n log n) //선형로그형, 데이터의 수가 2배로 늘 때, 연산횟수는 2배 조금 넘게 증가하는 알고리즘

O(n^2) //지수형, '지수적 증가'는 무서운 연산횟수의 증가를 보이므로 다른 방안을 찾아야 함

O(C^n) // 문제를 해결하기위한 단계의 수는 상수값 C의 입력값 제곱

예시

//덧셈 연산이 하나뿐이므로 상수시간인 O(1)
//단순한 변수 선언이나 함수 진입과 끝은 알고리즘 성능에 영향을 주지 않는다.
int sum1(int a, int b){
    return a + b;
}
//덧셈, 대입연산이 cnt만큼 실행된다. O(cnt) = O(n)
//입력이 증가하면 처리시간이 선형적으로 증가한다.
int sum2(int cnt){
    sum=0;
    for(int i=0; i<cnt; i++){
        sum+=i;
    }
    return sum;
}
//위의 덧셈,대입연산이 d만큼 실행된것을 또 C만큼 실행한다. O(c*d) = O(n^2)
//반복문의수 : 2
int sum3(int c, int d){
    sum=0;
    for(int i=0; i<c; i++){
        for(int j=0; j<d; j++){
            sum +=1;
        }
    }
    return sum;
}

정렬 알고리즘 시간 복잡도 비교

이름	최상	평균	최악
삽입정렬	n	n^2	n^2
선택정렬	n^2	n^2	n^2
버블정렬	n^2	n^2	n^2
셸정렬	n	n^1.5	n^2
퀵정렬	nlogn	nlogn	n^2
힙정렬	nlogn	nlogn	nlogn
병합정렬	nlogn	nlogn	nlogn

정리

• 알고리즘 문제를 해결할 때 보통 1억 번(연산 횟수)을 1초로 잡는다.
• 알고리즘의 수행 시간을 빠르게 확인하는 법은 반복문(차수)을 확인하는 것이다.
• 연산의 입력이 커서 시간 초과가 날 경우 차수를 줄이는 게 가장 중요하다. - O(logn), O(n)으로 짜는 버릇을 들이자.