출처
- 해당 post는 https://www.youtube.com/watch?v=BEVnxbxBqi8 영상을 보고 정리한것 입니다.
0. 알고리즘의 속도
- 알고리즘의 속도는 느리다, 빠르다를 표현하는 방식이 Big O이다
- 다만 알고리즘의 속도는 시간으로 표현하지 않는다. 즉, 몇 초 라는 방식이 아닌것
- 같은 알고리즘이라도 컴퓨팅 파워에 따라 처리하는 시간이 다르기 때문이다.
- 알고리즘의 속도는 완료까지 걸리는 절차의 수로 결정이 된다.
- Linear Search가 Binary Search보다 스탭이 많다.(느리다)는 이러한 이유 때문이다.
1. Big O
- Big O의 그래프
- 알고리즘의 시간복잡도를 O(N)과 같은 형식으로 표현하는것을 Big O라고 한다.
- Big O를 이해한다면 알고리즘의 분석을 더 빠르게 할 수 있으며, 내 코드에 대한 평가를 할수 있다.
2. O(1) (Constant time)
1
2
def print_first(arr):
print(arr[0])
- 위 처럼 배열의 첫번째 원소를 프린트하는 함수는 배열의 크기와 상관없이 맨 첫번째의 원소를 출력함으로 동일한 숫자의 스탭이 필요하기 때문에 시간 복잡도는 constant time(상수 시간)이라고 할수 있다.
- 이는 O(1) 로 표현이 가능할것이다.
- 그래프로 표현하면 위와 같다.
1
2
3
def print_first(arr):
print(arr[0])
print(arr[0])
- 위처럼 2번 print하는 함수에 대해서는 어떨까? 2번의 스텝이 필요하니까 시간복잡도는 O(2)라고 표현할까? 아니다. 시간복잡도는 그대로 O(1)이다.
- 왜냐하면 Big O는 함수의 디테일보다는 인풋사이즈에 따른 함수의 작동방식에 주목한다.
- 따라서 위 함수가 프린트를 2번한다고 하더라도 시간 복잡도는 여전히 O(1)로 표현한다.
- 위의 함수는 인풋 사이즈가 엄청나게 커져도 미리 정해진 숫자에 따라 작동하는 것이기 때문이다.
- 즉, Big O는 상수(Constant)에 신경을 쓰지 않는다는것이다.
- 인풋 사이즈가 아무리 커져도 항상 같은 시간을 가지게 되는 O(1)은 가장 선호되는 시간 복잡도 이지만, 알고리즘으로 만들기가 어렵다.
3. O(N) (Linear time)
1
2
3
def print_all(arr):
for n in arr:
print(n)
- 위처럼 배열의 모든 원소를 프린트하는 함수는 Linear Search 처럼 배열의 모든 원소에 접근을 해야 하기 때문에 배열의 크기에 따라 step이 달라지게 된다.
- 이러한 시간 복잡도를 가지는 것을 O(N) 이라고 한다.
- O(N)을 그래프로 표현하면 다음과 같다.
1
2
3
4
5
def print_all(arr):
for n in arr: # step1
print(n)
for n in arr: # step2
print(n)
- 그렇다면 위의 함수는 O(2N)인것일까?
- Big O는 상수(Constant)에 신경을 쓰지 않는다고 한것처럼, 위의 함수도 O(N)이다.
- Big O에서는 인풋이 증가하면 step도 증가하는것을 전달하는것을 중점으로 보기 때문에 O(2N)이든 O(N)이든 상관없다. 그래서 O(2N) 처럼 상수가 증가하는것은 표현하지 않는다.
4. O(N^2) (Quadratic time)
1
2
3
4
def print_twice(arr):
for n in arr:
for x in arr:
print(x, n)
- Quadratic time은 중첩 반복(Nested Loops) 이 있을때 발생한다.
- 위처럼 2중 for문을 도는 함수는 시간복잡도는 O(n^2) 이다.
- 인풋 사이즈가 10개라면 총 100번의 step이 필요하기 때문이다.
- Linear time과 Quadratic time의 시간 복잡도는 위의 그래프와 같다.
5. O(log n) (Logarithmic time)
- Binary Search처럼 Log 시간으로 표현되는 시간복잡도 이다.
- Binary Search는 인풋사이즈가 2배로 커져도 step은 1번만 많아지는 굉장히 빠른 알고리즘이다.
- 이와 같은 알고리즘은 O(Log n) 으로 표현한다.
- 그럼 왜 Log인 것일까?
- 우선 Log와 exp는 정 반대인것을 우리는 알고 있을것이다.
- 만일 2^n = 32라면 n이 몇이여야 해당 식은 성립할까? 바로 n은 5이다.
- 2 * 2 * 2 * 2 * 2 = 32이므로 n은 2의 갯수인 5가 될것이다.
- 로그는 위의 식에서 정반대이다.
- n = log32라면 n은 몇일까? (log의 밑은 2)
- 위의 공식은 32를 2로 몇번을 나누어야 1이 될지와 같은 말이다.
32 / 2 = 16 16 / 2 = 8 8 / 2 = 4 4 / 2 = 2 2 / 2 = 1
- 위처럼 32의 밑이 2인 로그는 5라는 것을 알수 있다.
- 이것은 Binary Search와 동일하다. Binary Search도 매번 절반씩 나누면서 시작하기 떄문이다.
- 즉, Binary Search는 O(log n) 이다. 참고로 Big O에서는 log의 밑을 쓰지 않는다.
- O(lon n)의 시간복잡도는 위의 그래프와 같다.
- 당연히 O(1)보다는 느리고, O(N)보다는 빠르다.
5. Summary
- 위에서 설명한 Big O의 전체를 그래프로 그리면 이와 같다.
- 당연히 인풋사이즈가 늘어도 시간에 변함이 없는 O(1)를 선호하지만, 현실적으로 그러한 알고리즘은 만들기 어렵다.
- 앞으로 알고리즘을 구현할때 시간 복잡도를 잘 생각해서 알고리즘을 구성하면 더 효율적인 코드를 작성할수 있을것이다.