알고리즘 실행 시간에 대하여

개관

어떠한 한 문제를 풀기 위한 알고리즘은 여러가지입니다. 특정 문제를 풀때 여러가지 알고리즘중 어떤 알고리즘을 선택할지에 대한 기준은, '시간과 공간'에 있습니다. 시간은 그 소스코드가 동작하는 시간을 말합니다. 시간이 적을수록 무언가 다른 동작을 할 시간이 많아집니다. 또, 공간은 알고리즘을 실행 하는 데에 필요한 공간, 즉 컴퓨터 메모리를 말합니다. 이제 저희는 문제에 대한 알고리즘 선택에 최소 시간, 최소 공간이 필요한 알고리즘을 선택해야 한다는 것을 알 것입니다. 하지만 보통 시간이 빠르면 메모리 공간을 많이 차지하고, 메모리 공간을 별로 차지하지 않으면 시간이 느립니다. 보통 프록래밍 대회에서 중요시 여기는 알고리즘의 기준은 공간보다 시간에 초점을 두고있습니다. 따라서 저희도 시간에 초점을 둘 것입니다.

 

시간 복잡도

시간이 빠른 알고리즘을 추구하기 위해 저희는 알고리즘의 시간 복잡도를 분석하는 능력의 필요성을 느껴야합니다. 알고리즘을 실행했을 때, 실행시간에 영향을 주는 요인들은 많습니다. 실행하는 운영체제, 프로그래밍 언어, 컴파일러 등등 이 실행시간에 영향을 줍니다. 알고리즘의 수행시간을 어떤 기준으로 측정해야할까요? 

종만북에서 나온 예시를 들겠습니다.

 

항목	자동차 A	자동차 B
시동 거는 데 걸리는 시간	4분	3초
문 열었다 닫는 데 걸리는 시간	2분	0초
운전석 등받이 조절에 걸리는 시간	6분	0초
앞 유리 닦는 데 걸리는 시간	7분	0초
최대 시속	100km/h	20km/h

위 표를 보고, 자동차 A, 자동차 B 중 하나를 서울에서 부산 가는 길에 타고 가야한다고 생각해봅시다. 

당연히 운동하는 것을 매우 심각하게 좋아하는 사람이 아닌이상 자동차 A를 타고 갈 것입니다(참고로 자동차 B는 자전거였습니다 ㄴㅇㄱ). 자동차를 타고 서울에서 부산이면 시간단위로 가야하는데, 문열었다 닫거나, 유리를 닦는 등의 몇분 소요로는 어느 자동차가 더 빠른지에 영향을 주기 힘듭니다.

알고리즘도 마찬가지입니다 어떠한 요인들이 영향을 미친다 한들 가장 큰 영향을 주는 요인에 의해서 알고리즘의 빠른 순위가 결정됩니다. 알고리즘의 수행시간을 지배하는 것을 반복문입니다.

 

다음 예시 코드를 보고 생각을 해보겠습니다.

정말 유명한 별찍기 문제에 대해서 for문을 이용하여 시간복잡도를 분석해 보겠습니다.

#include <iostream>
using namespace std;
int main(){
    int a;
    cin>>a;
    int count = 0;
    for(int i= 0; i<a; i++){
        for(int j = 0; j<=i; j++){
            cout<<"*";
            count ++;
        }
        cout<<endl;
    }
    cout<<count;
    return 0;
}

여기서 count 변수는 총 for문이 몇번 돌았는지 세 주는 변수입니다. a값이 들어오면 count는 항상

a(a+1)/2 입니다. 즉 a(a+1)/2번 만큼 for문이 실행된다는 뜻입니다. 시간복잡도는 계수를 생각하지 않고 차수는 항상 높은 것을 선택하기 때문에 이 코드의 시간 복잡도는 O(N^2)라고 할 수 있습니다.