알고리즘 수행 시간 측정 방법
절대 시간 측정
프로그램을 실행하여 결과가 나올 때까지의 시간을 측정하는 방법이다. 이 방법은 프로그램을 실행하는 환경에 따라 달라질 수 있어서 코딩 테스트에서는 잘 활용하지 않는다.
시간 복잡도 측정
알고리즘이 시작한 순간부터 결괏값이 나올 때까지의 연산 횟수를 나타낸다. 그리고 시간 복잡도를 측정한 결과는 최선(best), 보통(normal), 최악(worst)의 경우로 나눈다.
배열의 길이가 8일 때 '배열의 맨 앞부터 하나씩 검사하기'라는 알고리즘을 사용한다면, 이 알고르짐의 상황에 따라 최선의 연산 횟수는 1번, 최악의 횟수는 8번이다.
시간 복잡도를 표현하는 방법
최선은 1, 최악은 8이라는 특정한 입력 크기에 따른 연산 횟수로 시간 시간 복잡도를 이야기하는 건 무의미하다. 1차원 배열 문제에서 배열 크기가 1이면 최선, 보통, 최악의 경우는 모두 연산 횟수가 1이된다. 이 결과만 보고 '이 알고리즘은 모든 경우에 연산 횟수가 1인 성능을 가지는 것이구나'라고 생각하면 안된다.
다시 말해 특정 입력 크기에 한하여 연산 횟수를 기준으로 시간 복잡도를 측정하면 안 된다. 입력 크기를 N으로 일반화하여 연산 쵯수의 추이를 나타내야 한다.
이런 방식으로 입력 크기에 따른 연산 횟수의 추이를 활용해서 시간 복잡도를 표현하는 방법을 점근적 표기법이라고 한다.
최악의 경우 시간 복잡도를 표현하는 빅오 표기법
최악의 경우에 대하여 시간 복잡도를 표현하는 방법은 상한선을 활용한 점근적 표기법인 빅오 표기법이다. 어떤 프로그램의 연산 횟수가 f(x)라고 할 때 함수의 최고차항을 남기고 차수를 지워 O(...)와 같이 표기하면 된다.
예를 들어 어떤 프로그램의 연산 횟수가 f(x) = 2x^2 + 3x + 5라면 시간 복잡도를 O(x^2)과 같이 표현하면 된다.
def solution(n):
count = 0
# 반복문 1 : n^2번 연산 수행
for i in range(n):
for j in range(n):
count += 1
# 반복문 2 : n번 연산 수행
for k in range(n):
count += 1
# 반복문 3 : 2n번 연산 수행
for i in range(2*n):
count += 1
# 반복문 4 : 5번 연산 수행
for i in range(5):
count += 1
print(count) # 59(n이 6일 때, 6^2 + 6 + 2*6 + 5 = 59)
solution(6) # 함수 호출 f(x)=x2+3x+5*
이때 다음을 만족하는 C가 있으면 f(x)의 최악의 시간 복잡도는 O(g(x))라고 쓴다.
- 특정 x 시점 이후부터 항상 f(x) ≤ C * g(x)를 만족
- C는 상수
쉽게 말해 g(x)에 상수 C를 곱했을 때 특정 시점부터 f(x)를 넘어서는지 여부를 보면 된다.
나는 왜 상수를 곱하는지... 이해를 하지 못했었는데, gpt와 검색을 통해 알게된 점이 있다.
- 빅오를 구하는 것은 함수가 성장하는 것을 따지기 위해다.
- 성장한다는 것은 입력이 커질 때, 실행 시간이 얼마나 빠르게 증가하느냐다.
- f(x)가 처음은 g(x)보다 크더라도, 성장세를 통해 두 함수를 따질 수 있는거다.
빅오 표기법을 쓸 때
최고차항만 남기는 이유
f(n) = 3n^2 + 5n + 7n이 작을 땐 5n,7도 영향이 있지만, n이 커질수록 3n^2이 다른 것보다 훨씬 빨리 커진다.
그래서 결국 전체 성능은 n^2이 지배하게 된다.
그래서 전체 성능을 지배하는 3n^2로 쓴다. 상수도 무시해버린다.
우선순위 비교
가장 느림 -> 가장 빠름(성장속도가)
1 < log(n) < n < n log n < n^2 < n^3 < ... < 2^n < n! < n^n이걸 외워둘 필요는 없다! 느낌만 가져가는 거다.
- 로그(log)는 엄청 느리게 증가
- 다항식(n, n^2, n^3)은 보통 증가
- 지수(2^n, 3^n)는 엄청 빠르게 증가
핵심 정리
입력이 커질 때 제일 큰 항이 전체 성능을 결정하니까, 나머지를 무시하는거다!
왜... 암달의 법칙의 주요 시사점이 생각나는거지...
결론
빅오(Big-O) 표기법은 입력 크기(n)가 엄청 클 때, 실행 시간이 얼마나 빨리 늘어나는지를 나타내는 방법이다.
n이 커질수록 누가 제일 빠르게 커지느냐 그거만 따지는 거다!
