개요

우리가 약속을 잡고 나갈 때 출발 시간을 정하는 기준은 여러가지가 있다.
이론적으로 언제까지 어디에 도착해야하고 어떤 이동수단을 타면 딱 맞게 도착하겠다.
여기엔 버스가 늦게올 확률, 무언가를 빼먹어서 다시 집으로 돌아갈 확률 등이 빠져있어서 지각할 때가 많았다…
내가 늦어서 짜증났던 사람들에게 이 자리를 빌려 심심한 사과의 말씀을 드린다.

그래서 그 뒤로는 항상 버스 배차 시간의 최대를 기다리는 시간으로, 목적지까지 가는데 걸리는 시간의 최대를 예상 시간으로 잡고 나간다. 그래야 지각을 안한다.

컴퓨터의 문제 해결 과정도 마찬가지다.

시간복잡도

세상에는 여러가지 알고리즘이 있다. 그러니 같은 목적의 알고리즘이지만 방식이 다른 알고리즘이 있다. 이런 경우 어떻게 알고리즘을 선택해야할까?
시간적인 제약이 가장 먼저 떠오른다. 일반적으로 여러 가지의 알고리즘이 사용된 서로 다른 코드가 있을 때 수행 시간을 예측하여 수행 시간은 최대 ~이하의 시간이 걸려야한다 등의 요구사항이 존재하기 때문이다. 그렇지 않다면 많은 처리를 해야하는 경우 시스템 장애 등으로 이어질 수 있다.
따라서 이를 예측하고 예방할 수 있어야한다.
직접 측정해보자.
아래는 반복문을 돌며 1부터 5까지의 수를 순차적으로 출력하는 코드다.

import time

start = time.time()
for i in range(1, 6):
    print(i)
end = time.time()

print(end - start)

실행 시간은 1.3828277587890625e-05
다시 한 번 실행시켜보면 1.2159347534179688e-05이 나온다.
이렇게 달라진다.
이건 컴퓨터가 사용할 수 있는 자원이 매번 다르고 이 자원이 프로그램에 영향을 미치므로
소요 시간도 매번 달라지는 것이다.
즉, 언어에 따라 달라지고 실행 환경에 따라 달라진다.

이런 상황이니 서로 다른 두 알고리즘을 비교해야한다면 좀 더 일반적인 비교가 필요하다.
위의 코드는 5번의 반복을 하니 f(n) = 5로 표현할 수 있다.
만약 n이 달라지면 f(n)의 값도 커진다.
따라서 알고리즘의 단계는 n값에 영향을 받는다.
수학적으로는 f(n) = n으로 나타낼 수 있다.
실제 로직은 좀 더 여러 로직이 엉겨붙어있다. 예를 들어 반복문 안에 코드 한 줄만 추가되어도 f(n) = 2n이 된다.

그러나 이처럼 필요한 단계를 매번 새롭게 샐 수는 없다. 그래서 점근법(대략적으로 나타내는 방법)을 사용하여 데이터가 증가할 때 연산 횟수의 변화를 나타낸다.(상수는 무시한다.) image 만약 f(n) = n^2이고 n이 1이라면 n과 n^2의 차이가 없다. 따라서 데이터를 무한히 증가시켜 평가한다. 이를 공식으로 나타낸 것이 Big O 표기법이라고 한다. 여기서 O는 On the order of의 약자로 ~만큼의 정도로 커지는 이라는 의미로 해석할 수 있다.

다음과 같은 배열이 있다고 하자.

int[] a = {1,3,4,5,10,9,8};

이 배열에서 특정 숫자를 찾는다면 몇번의 연산을 수행해야 할까?

찾으려는 숫자가 1일 경우 한번만에 찾을 수 있다. -> 최선
8을 찾으려면 7번의 연산을 통해 찾을 수 있다. -> 최악
5를 찾으려면 4번의 연산을 통해 찾을 수 있다. -> 평균

이들을 각각 O(1), O(n), O(n)으로 나타낼 수 있다.
위에서 살펴본 빅 오 표기법 말고도 빅 오메가 빅 세타 등이 있다.
일반적으로는 최선일 경우 빅 오메가, 평균일 경우 빅 세타를 말하는데 이는 오개념으로
위에서 살펴본대로 n에 영향을 받곤 하는데 이 상한선을 의미하는 것이 빅 오 표기법이다.
그러니 항상 최악의 경우만 의미하는 것은 아니다. 하나의 알고리즘에서도 최선과 최악이 존재할 수 있다. 일반적으로 빅 오 시간 복잡도를 최악의 경우라고 알고있는 이유는 상한의 의미를 가지기 때문인데 n이 커질 때 알고리즘의 실행 단계가 절대로 O(f(n))을 넘지 않는다는 의미가 된다.
빅 오메가는 알고리즘의 최선의 경우 즉, 실행 시간이 최소 얼마나 걸리는지를 나타낸다.
선형 탐색의 경우 최선의 경우 시간 복잡도는 O(1)이자 Ω(1)이다.
이러한 표기 법은 범위를 표현하는 것이 본질이기 때문이다.

이중에 코딩테스트에서 참고하는 시간복잡도는 빅 오다.
그 이유는 다양한 테스트케이스를 돌려 모두 통과해야만 하는데 그렇다면 최악의 상황이었을 때의 빅 오 시간복잡도를 고려해야 모든 테스트 케이스가 정해진 제약조건 안에서 통과할 수 있기 때문이다. 마치 약속을 잡고 집에서 출발할 때 버스 대기시간의 최대 시간, 버스 예상 이동 시간의 최대 시간으로 잡아야 확실히 약속 시간에 늦지 않고 도착할 수 있는 것과 같다.

추가 자료

이진 탐색의 경우 시간 복잡도를 계산해보면 log2(n)이지만 상수는 무시하기 때문에 log(n)이라고 표기한다.

말이 나온 김에 이진 탐색의 시간복잡도를 계산해보자. 데이터를 반으로 나누어 검색한다.

n / 2
n / 2 / 2
n / 2 / 2 / 2
...
n * (1/2) ^ k = 1(k번 반복 끝에 결국 탐색범위가 1이 되므로)
2 ^ k = n
k = log2(n)

아래의 그래프는 시간 복잡도의 종류에 따른 데이터 양과 연산 횟수를 의미한다. image

O(1)은 상수로 주로 해시 자료구조에서 값을 찾거나 배열의 가장 첫 번째 요소를 찾는 작업의 시간 복잡도에 해당한다. 또는 코딩 문제를 풀면서 데이터를 단순히 사칙연산하여 답을 구할 수 있는 경우도 시간복잡도는 상수이다.

O(n)은 비례관계로 선형이라고 한다. 데이터 양이 증가함에 따라 메모리 사용, 연산 횟수가 선형적으로 증가한다.

O(n^2)은 반복문이 중첩되어 2개가 있는 경우로 수학에서의 y = x^2과 같다. 데이터 양이 증가함에 따라 처리 시간은 그의 제곱배로 증가한다.
만약 반복문이 4개가 중첨되어있는 경우 시간 복잡도는 n^4가 된다.

O(log(n))은 데이터 양이 많아짐에 따라 연산 횟수가 서서히 느리게 증가한다.

내용 출처: https://www.hanbit.co.kr/channel/category/category_view.html?cms_code=CMS4190304964
https://www.boostcourse.org/cs112/lecture/119020?isDesc=false
https://www.acmicpc.net/blog/view/136