[알고리즘] | 시간 복잡도

효율성

알고리즘 문제 해결 코드가 얼마나 효율적인지 판단할때 아래 두가지가 가장 중요한 요소이다.

• 수행시간
• 사용한 메모리

수행시간

효율성을 판단하는데 제일 중요한 단 한가지 요소를 뽑자면 수행시간 이라고 할 수 있다.

• 어떤 프로그램을 작성했는데 시간이 20일이 걸리면 20일동안 실행시켜야한다.
  • 해결 불가능
• 어떤 프로그램이 메모리가 64GB가 필요한데 메모리가 부족하다면 램을 구매하면된다.
  • 해결 가능

따라서, 문제 해결시 가장 중요한 요소는 시간이라고 볼 수 있다.

문제의 크기

개발 상황에서 접하게 되는 상황은 문제를 해결하는 것이다. 문제에는 항상 크기가 존재한다.

• 예시1) 쇼핑몰 장바구니 물건의 개수 (상품의 개수, 회원의 수)
• 예시2) 게임 동시 접속자의 수

이러한 문제의 크기에 따라 걸리는 시간이 다르다. 이때 걸리는 시간을 시간복잡도로 표현할 수 있다.

시간복잡도(Time Complexity)

실행시간 관점에서 알고리즘의 효율성을 측정한다.

• 시간 복잡도를 이용하면 프로그램의 시간이 얼마나 걸릴지 대략적으로 예상이 가능하다.
• 표기법으로 대문자 O를 사용한다. (Big-O 표기법)
• 영어로는 Big O Notation이라고 한다.
• 입력의 크기에 대하여 시간이 얼마나 걸릴지 나타내는 방법
• 최악의 경우(문제의 크기가 가장 큰 경우)에 시간이 얼마나 걸릴지 알 수 있다.

[시간 복잡도 문제]

• N명의 사람이 식당에 방문
• 메뉴 M개, 메뉴판 1개
• 사람 1명이 메뉴판을 읽는데 걸리는 시간 : O(M)
• 각 사람이 메뉴판에 있는 모든 메뉴를 읽는 시간 복잡도 : O(NM)

시간 복잡도 계산 방법

• 코드를 보고 계산
• 코드 작성전 문제의 크기를 보고 구현 방법을 생각하여 계산

사실 일일히 연산을 세는것은 큰 의미가 없다. 반복문 밖에 있는 단순연산들은 결국 상수항이라 무시되고 반복문 안에있는 연산이라도 가장 큰 차수 외에는 각 항의 계수를 포함한 모든 것들이 무시되기 때문이다. 결국 반복문과 재귀로 반복되는 횟수만 확인하면 된다.

예를 들어, 반복횟수가 n인 for 반복문이 두 번 있다면 n에 대한 1차식 두개를 곱하므로 연산의 개수에 대한 식은 n²이 되는 것이고 시간복잡도는 O(n²)이다.

결국 빅오 표기법은 알고리즘 내에서 반복의 차수와 직결된다고 볼 수 있다.

1부터 N까지의 합을 구하는 코드의 시간복잡도 계산

[시간복잡도 방법1]

int sum = 0;
        
for (int i =0; i < N; i++){
    sum +=i;
}

위 코드에서 최악의 경우 i는 0부터 n-1까지 n번의 연산을 수행한다. 이를 빅오 표기법으로 표현하면 최고차항인 n만을 표기한다. 즉 위 코드의 시간복잡도는 O(n)이다.

[시간복잡도 방법2]

int sum = 0;

for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        if(i==j){
	         sum += j;
        }
    }
}

같은 방식으로 위 코드의 시간복잡도를 측정해보면 바깥쪽 for문을 n번 수행하고 안쪽 for문을 n번 수행한다. N을 N번 수행하기 때문에 시간복잡도는 O(N*N) 즉, O(n²)이다.

[시간복잡도 방법3]

int sum = 0;

sum = N * (N + 1) / 2;

위 코드는 곱셈 한번, 덧셈 한번, 나눗셈 한번 총 세번 연산한다. 이런 경우는 O(1)이라고 시간복잡도를 표현할 수 있다.

위 3가지 코드는 모두 1-N 까지의 합을 구하는 방법을 각각 다르게 하여 시간복잡도를 계산해 보았다. O(1)이 나오는 문제3방법이 가장 효율성이 좋은 방법이라고 할 수 있다.

문제 크기 N에 대하여 대략 N이 1억이라고 가정하면 실제 수행 시간은 1초정도 걸린다고 생각하면 된다. (실제로는 0.1 - 0.2초정도의 차이가 있다.)

시간 복잡도 종류

대표적인 시간 복잡도 종류와 그것들이 1초가 걸리는 입력의 크기는 아래와 같다.

• O(1)
• O(logN)
• O(N) : 1억
• O(NlogN) : 5백만
• O(n²) : 1만
• O(n^3) : 500
• O(2^N) : 20
• O(N!) : 10

시간복잡도와 상수

• 상수항 무시
  • 데이터 입력값(n)이 충분히 크다고 가정하고 있다. 따라서 알고리즘의 효율성 또한 데이터 입력값(n)의 크기에 영향을 받기 때문에 상수항같은 사소한 부분은 무시한다.
    ex) O(3n²) = O(n²), O(5) = O(1) 와 같이 상수항은 무시하고 표기한다.
• 영향력 없는 항 무시
  • 데이터 입력값(n)의 크기에 따라 영향을 받기 때문에 가장 영향력이 큰 항 이외에 영향력이 없는 항들은 무시한다.
    ex) O(n²+N) = O(n²) -> O(n²) 와 같이 영향력이 지배적인 항만을 표기한다.
• 두가지 항이 변수가 다르면 그대로 둔다.
  • 데이터 입력값(n,m)중 어느것의 크기가 더 큰 영향을 미치는지 알수 없기 때문에 두 항 모두 그대로 표기한다.
    ex) O(n²+M) 와 같이 두항 모두 그대로 표기한다.

시간복잡도 비교

O(1) < O(n) < O(logn) < O(nlogn) < O(n²) < O(N!)