시간복잡도.. Big O 신경 써서 코테 문제 풀어야한다며...
뭔지는 알았다. 최적의 알고리즘을 만들어내고, 문제를 해결하기 위해서 고려해야 하는 사항이라는 것
그리고 O(1)이 가장 빠르고 O(n!)이 가장 느리단 것도... 전공 수업에서 배웠기 때문이다.
이론은 알고있었는데,, 막상 코테 문제를 풀 때 고려해서 풀려니 뭔가 어색하고 코드를 다 짜고나서 빅오를 측정하려니까 당연히 이해를 못하고 암기식으로 알고 있으니까 뭘 몰랐던 것,,
코테를 처음 접하게 될 때 항상 걸리는 부분이 시간 제한, 시간 초과다 (열받음;;) 이런 실수는 나면 안 된다.
시간복잡도를 알고 있는 사람이라면,,
여러 책과 영상 찾아보면서 좀 디테일하게 공부해 보았다.
알고리즘 분석에서는 2가지의 측면을 고려할 수 있다.
즉 알고리즘의수행시간과 알고리즘이 필요로 하는기억공간의 양이 그것이다.
시간복잡도함수
절대적인 수행시간을 나타내는 것이 아니라
알고리즘을 이루고 있는 연산들이 몇번이나 수행되는지를 숫자로 표시한다.
연산들의 수행횟수는 보통 프로그램에 주어지는 입력의 개수 n에 따라 변하게 된다.
따라서 연산의 수행횟수는 고정된 숫자가 아니라 n에 대한 함수가 된다. 이렇게 입력의 개수 n의 함수로 나타낸 것을
시간복잡도 함수라고 하고 T(n)이라고 표시한다.
예제
| 알고리즘 A | 알고리즘 B | 알고리즘 C |
| sum ← n*n | for i ← 1 to n do sum ← sum+n |
for i←1 to n do for j←1 to n do sum ← sum+1 |
여기서 문제의 크기는 n이다. 연산의 횟수를 세어보자 (루프제어는 고려하지 않는다.)
- 알고리즘의 비교
| 알고리즘 A | 알고리즘 B | 알고리즘 C | |
| 대입연산 | 1 | n | n*n |
| 덧셈연산 | n | n*n | |
| 곱셈연산 | 1 | ||
| 나눗셈연산 | |||
| 전체연산수 | 2 | 2n | 2n^2 |
하나의 연산이 t만큼의 시간이 걸린다고 하면 알고리즘A는 2t에 비례하는 시간이 필요할거고..
알고리즘B는 2nt의 시간이, 알고리즘C는 2nt^2 만큼의 시간이 걸린다.
그래서 문제의 크기인 n이 커질수록 알고리즘간의 차이는 더욱더 커지게 될 것이다.
자, 여기서 당연하게도 알고리즘A 가 최적의 알고리즘임을 알 수 있겠다.
이런 시간복잡도를 표현할 때는 빅오 표기법을 사용한다.
빅오 표기법
쉽게 설명하자면, 가장 빠르게 증가하는 항만을 고려하는 표기법이다.
이게 무슨 말이냐면,,
일반적으로 자료의 개수가 많은 경우에는 차수가 가장 큰 항이 가장 영향을 크게 미친다. 무슨말인가 하면,
$$ T(n) = n^2 + n+ 1 $$
이런 수식이 있다고 치자. n=1000일 때, T(n)값은 1,001,001이고 이중에서 첫 번째 항인 $ n^2 $의 값이 전체의 약 99.9%인 1,000,000이고 두번째 항의 값이 1000으로 전체의 약 0.1%를 차지한다.
이렇게 입력 자료의 개수가 큰 경우에는 차수가 가장 큰 항이 전체의 값을 주도함을 알 수 있다.
따라서 보통 시간 복잡도 함수에서 차수가 가장 큰 항만을 고려하면 충분한데 이 때 가장 빠르게 증가하는, 가장 크게 영향을 끼치는 항만을 고려하는 표기법인
빅오표기법을 사용한다.
빅오 표기법은 시간복잡도 함수에서 불필요한 정보를 제거하여 알고리즘 분석을 쉽게할 목적으로 시간 복잡도를 표시하는 방법이다.
따라서 위에 알고리즘A는 O(n)이라 하고 "빅오 of n"이라고 읽는다.
▶ 추가로.. 수학적 정의로는...
" 두 개의 함수 f(n)과 g(n)이 주어졌을 때 모든 $ n>n_0 $에 대해 $|f(n)| <= c|g(n)| $을 만족하는 2개의 상수 c와 $n_0$가 존재하면 f(n)=O(g(n))이다. "
예제
- $f(n)=5$ 이면 O(1) 이다. 왜냐하면 $n_0=1$, c=10 일 때, n>1에 대해 $5<=10*1$이 되기 때문이다.
- $f(n)=2n+1$이면 O(N)이다. 왜냐하면 $n_0=2$, c=3일 때, n>2에 대해 $2n+1<=3n$이 되기 때문이다.
- $f(n)=3n^2+100$이면 $O(n^2)$이다. 왜냐하면 $n_0=100$, c=5일 때, n>100에 대해 $3n^2+100<=5^n^2$이 되기 때문이다.
- $f(n)=5*2^n+10n^2+100이면 $O(2^n)$이다. 왜냐하면 $n_0=1000$, c=10일 때, n>1000에 대해 $5*2^n+10n^2+100<=10*2^n$이 되기 때문이다.
예제를 보면 알겠지만 그저 최고차항의 차수만을 활용한다는 것을 볼 수 있는데
주의 할 점이 있다. 바로 logn인데 logn은 차수를 가지고 있기 때문이다.
예를 들어 $ 8n^2logn+5n^2+n=O(n^2logn) $ 을 볼 수 있다.
빅오 표기법에 의한 알고리즘의 수행시간 비교
- $ O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) <O(n!) $
주의 할 점은 또 있다.
상수항이나 계수가 굉장히 큰 경우에는 수행시간에 영향을 끼친다는 것이다. 예를 들어 두 개의 알고리즘,A와 B가 있다고 해보자.
이때 이들의 시간 복잡도 함수가 각각 $T_A(n)=100n+100$ 이고 $T_B(n)=n^2 $ 라고 하자.
알고리즘 A를 빅오 표기법으로 표기를 하면 $O(n)$이 될 것이고, 알고리즘 B는 $O(n^2)$이 되지만 실제로 비교해보면 알고리즘 A가 더 효율적이게 되는 것은 N>100인 경우다. 따라서 n이 작을 때는 상수항이나 각 항의 계수도 영향을 끼친다.
빅오 표기법 이회의 표기법
빅오 표기법은 편리하지만, $f(n)=2n+1$인 경우 $f(n)=O(n)$이라 하지만 사실은 $f(n)=O(n^2)$이라고도 할 수 있다.
왜냐면 $n_0=1$, c=2로 잡으면 n>1에 대해서 $2n+1<=2n^2$이기 때문이다.
이로써, 빅오 표기법은 상한을 표기한 것이므로 상한은 여러개가 존재할 수 있다.
이와 같은 문제점을 보완하기 위해 나타난 것이
빅오메가와 빅쎄타 표기법이다.
- 빅오메가는 어떤 함수의 하한을 표시하는 방법이다. 예를 들어 $f(n)=2n+1$인 경우에는 n>1에 대해 2n+1>=n이므로 $f(n)= \Omega(n)$ 이다.
- 빅쎄타는 동일한 삼수로 상한과 하한을 만들 수 있는 경우, 즉 $f(n)=O(g(n))$이고 $f(n)=\Omega(g(n))$인 경우를 $\Theta(g(n))$이라 한다.
사실 이게 무슨 소린가 싶다. 수능 때 지겹게 보던 증명문제 푸는 느낌임. 그거다! 별로 알 필요 없다. 다만, 당연하게도 정의도 알고 있어야하고 이해도 하고 있어야 한다. 따라서 나는 빅오메가와 빅쎄타 표기법을 구해볼 수 있는 문제를 구글링해서 이해를 도왔다.
(근데 솔직히 뭔가 시간낭비 같긴 했음)
나왔다 나왔어 "최선, 평균, 최악의 경우"...
크게 예시를 들어서 정렬 알고리즘에 거의 정렬이 되어 있는 자료 집합을 주면, 난수값으로 주어지는 자료집합보다 훨씬 빨리 정렬 될 수도 있다. 그러면 알고리즘의 수행시간을 이야기할 때 어떤 자료 집합을 기준으로 해야할까?
즉, 최악의 경우, 최선의 경우는 수행시간이 가장 오래걸리고 적게 걸리고를 말하고 평균은 모든 입력을 고려하고 각 입력이 발생하는 확률을 고려해서 평균적인 수행시간을 의미한다.
사실. 평균 수행시간은 상당히 구하기 힘들 수 있다. 그래서 최악의 경우의 수해이간이 알고리즘의 시간 복잡도 척도로 많이 쓰인다.
예제
정렬되지 않은 배열을 순차적으로 탐색해서 특정한 값을 찾는 알고리즘에서 최악, 최상, 평균적인 경우의 시간복잡도 함수를 계산해보자. (순차탐색)
순차 탐색의 코드를 한번 작성해보겠다.
def seq_search(list, key):
for i in n:
if list[i]==key:
return i
return -1
- 최선의 경우는 찾고자 하는 숫자가 배열의 맨 처음에 있는 경우이다. 빅오 표기법에 따르면 O(1)이다.
- 최악의 경우는 찾고자 하는 숫자가 맨 마지막에 있는 경우가 될 것이다. 따라서 빅오로 표기하면 O(n)이다.
- 평균은 모든 숫자들이 탐색될 가능성이 1/n일 것이다. 따라서 모든 숫자들이 탐색 되었을 경우의 비교 연산 수행 횟수를 더하고, 전체 숫자 개수로 나누어 주면 평균적인 경우의 비교의 연산 수행 횟수를 알 수 있다.
$(1+2+...+n)/n=(n+1)/2$ 즉, 빅오로는 O(n)이 나온다.
일반적으로 코테 환경에서는 $O(n^3)$을 넘어가면 문제 풀이에서 사용하기 어렵다고 한다. 기본적으로 연산 횟수사 10억을 넘어가면 C언어를 기준으로 통상 1초 이상의 시간이 소요되는데 N의 크기가 5,000이 넘는다면 10초 이상의 시간이 걸릴 수 있기 때문이다. (C언어인데도!!)
시간 복잡도 분석은 문제 풀이의 핵심이다. 문제를 해석하기 전에 조건을 먼저 보기도 하는데,
이는 얼마나 효율적인 알고리즘을 작성해야하는지 눈치 챌 수 있기 때문이다.
(난 아직 거기까진 안되지만 최근에 본능적으로 그렇게 보기 시작했다.)
예를 들어 시간 제한이 1초라면, 대략 최악의 경우 O(N)의 시간 복잡도로 동작하는 알고리즘을 작성해야 할 것이라고 예상할 수 있고 데이터의 크기나 탐색 범위가 100억이나 1,000억을 넘어간느 경우 O(logN)의 시간 복잡도를 갖는 알고리즘을 작성해야 할 것이다.
아래는 몇 가지 예시인데 모두 시간제한이 1초인 문제에 대한 예시이다.
- N의 범위가 500인 경우: 시간복잡도가 $O(N^3)$인 알고리즘
- N의 범위가 2,000인 경우 : 시간복잡도가 $O(N^2)$인 알고리즘
- N의 범위가 100,000인 경우 : 시간복잡도가 O(NlogN)인 알고리즘
- N의 범위가 10,000,000인 경우 : 시간복잡도가 O(N)인 알고리즘
파이썬의 시간과 메모리 측정
실질적으로 알고리즘의 소요시간을 확인해야 자신이 제대로 알고리즘을 작성하고 있는지 체크할 수 있다.
import time
start_time=time.time() # 측정 시작
#프로그램 소스코드
end_time=time.time() # 측정 종료
print("time :", end_time-start_time) # 수행 시간 출력참고로 컴퓨터의 성능에 따라 IDE 상에서의 결과가 다를 수 있다! (코테 IDE 로는 시간 초과나는데 내 로컬 IDE에서는 잘 돌아가는 경험을 해 본 적이 있을 것이다. 이게 그 이유)