시간 복잡도(Time complexity)

입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼만큼 걸리는가?

효율적인 알고리즘이란, 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘 을 구성했다는 것입니다.

시간 복잡도는 주로 빅-오 표기법을 사용해 나타냅니다.

시간복잡도를 표기하는 방법

• Big-O(빅-오)
• Big-Ω(빅-오메가)
• Bid-θ(빅-세타)

세 가지 표기법은 시간 복잡도를 각각 최악, 최선, 중간(평균)의 경우에 대해 나타내는 방법입니다.

빅오 표기법은 최악의 경우를 고려하므로, 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있습니다.

한 마디로, "이 정도 시간까지 걸릴 수 있다." 로 표현할 수 있습니다.

최선의 경우 또는 평균값을 기대하는 시간 복잡도로 알고리즘을 구현한다면, 최악의 경우 어디에서 문제가 발생했는지 알아내기 위해 로직의 많은 부분을 파악해야 하므로 문제를 파악하는 데 많은 시간이 필요합니다.

그래서, 최악의 경우도 고려하여 대비 하는 것이 바람직하기 때문에, 다른 표기법보다 빅오 표기법을 많이 사용합니다.

O(1)

O(1)은 constant complexity라고 하여, 입력값이 증가하더라도 시간이 늘어나지 않습니다. 상수의 시간 복잡도라는 의미이기 때문에, 입력값의 크기와 관계없이, 즉시 출력값을 얻어낼 수 있습니다.

위 예시의 경우, arr 의 길이가 십만, 백만 단위로 늘어나더라도, 즉시 해당 index 에 접근해 값을 반환할 수 있습니다.

O(n)

O(n)은 Linear complexity라 하며, 입력값이 증가함에 따라 시간 또한 선형적으로 같은 비율로 증가하는 것을 의미합니다.

입력값이 1일 때 1초의 시간이 걸리고, 입력값을 100배로 증가시킬 때 1초의 100배인 100초가 걸리는 알고리즘의 경우, O(n)의 시간복잡도를 가집니다.

O_n_algorithm 함수에선 n이 1씩 증가할 때마다 실행 시간이 1초씩 증가합니다. 입력값이 증가함에 따라 같은 비율로 걸리는 시간이 늘어납니다.

another_O_n_algorithm은 n이 1씩 증가할 때마다 실행 시간이 2초씩 증가합니다.

여기서, another_O_n_algorithm의 시간 복잡도는 O(2n)이 되지 않고, O(n) 으로 표기합니다.

입력값이 커지면 커질수록 계수의 영향력이 퇴색되기 때문에, 같은 비율로 증가하고 있다면 모두 O(n) 으로 표기합니다.

O(log n)

O(log n)은 Logarithmic complexity라고 부르며 빅오 표기법 중 O(1) 다음으로 빠른 시간 복잡도를 가집니다.

BST(Binary Search Tree) 의 경우, 원하는 값을 탐색할 때, 노드를 이동할 때마다 경우의 수가 절반으로 줄어듭니다. 이 경우 O(log n)의 시간 복잡도를 가진 알고리즘입니다.

O($n^2$)

O($n^2$) 은 quadratic complexity라고 부르며, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미합니다.

예를 들어 입력값이 1일 경우 1초가 걸리던 알고리즘에 5라는 값을 주었더니 25초가 걸리게 된다면, 이 알고리즘의 시간 복잡도는 O($n^2$)라고 표현합니다.

위 예시의 경우로 보면, 입력값으로 5를 주게 되면, 내부 반복분에서 5초의 시간이 걸리고, 그 반복문을 나와 외부 반복문을 수행하게 됩니다. 즉, 내부 반복문이 5번 실행되는 것으로, 25초가 걸리게 됩니다.

반복문이 세 번 중첩된 경우, $5^3$ 초가 걸리게 됩니다.
이 경우들이 모두 O($n^2$)의 시간 복잡도를 가집니다.

O($2^n$)

O($2^n$)은 Exponential complexity라고 부르며 빅오 표기법중 가장 느린 시간 복잡도를 가집니다.

종이를 42번 접으면 그 두께가 지구에서 달까지의 거리보다 커진다는 이야기를 들어보신 적 있으신가요?
고작 42번 만에 얇은 종이가 그만한 두께를 가질 수 있는 것은, 매번 접힐 때마다 두께가 2배로 늘어나기 때문입니다.

구현한 알고리즘의 시간 복잡도가 O(2n)이라면 다른 접근 방식을 고민해 보는 것이 좋습니다.

재귀로 구현한 피보나치 수열의 경우, 대표적인 O($2^n$)알고리즘 입니다. 관련하여 이전에 포스팅한 글을 첨부하겠습니다.

시간 복잡도를 개선한 피보나치 수열

---

일반적으로 코딩 테스트에서는 정확한 값을 제한된 시간 내에 반환하는 프로그램을 작성해야 합니다.

시간제한과 주어진 데이터 크기 제한에 따른 시간 복잡도를 어림잡아 예측할 수 있습니다.

예를 들어 입력으로 주어지는 데이터에는 n만큼의 크기를 가지는 데이터가 있고, n이 1,000,000보다 작은 수일 때 O(n) 혹은 O(nlog n)의 시간 복잡도를 가지도록 예측하여 프로그램을 작성할 수 있습니다.

데이터 크기 제한	예상 시간 복잡도
n ≤ 1,000,000	O(n) or O (log n)
n ≤ 10,000	O($n^2$)
n ≤ 500	O($n^3$)

대략적인 데이터 크기에 따른 시간 복잡도는 다음과 같습니다.

---

예시

위 예시의 경우, 나올 수 있는 시간 복잡도는

• 스택에 새로운 요소를 넣거나 뺄 때 발생하는 O(1)이 있습니다. (가장 마지막 요소를 넣거나 빼기 때문에)

• 스택의 요소들을 탐색하는 O(n)이 있습니다.

위 예시의 경우에서 나올 수 있는 시간 복잡도는 O(n)입니다.

첫 번째 반복분은 n번 실행하고, 두 번째 반복문은 n-1번 실행합니다. 둘 다 모두 O(n)으로 표현합니다.

위 예시는 n이 주어졌을 때 절반씩 줄어들고 있기 때문에, 연산 횟수는 $log_2(n)$이며, 빅오 표기법으론 O(log n)입니다.

위 예시의 경우

n이 64이고, k가 2일 때 출력되는 i를 순서대로 나타내보면 다음과 같습니다.

i = [0, 2, 6, 14, 30, 62];

수학적으로 i는 k 배수만큼 커지며 n에 도달하고 있습니다. 로그식으로 표현하면 $log_kn$ 이며, 위 예시라면 $log_264$가 되기 때문에, 6번 ($2^6=64$) 실행됐다는 것을 알 수 있습니다.

빅오 표기법은 log의 base(밑)은 고려하지 않기 때문에, O(log n)이 되겠습니다.