알고리즘의 속도

속도는 컴퓨터라는 하드웨어가 결정하기 때문에 알고리즘은 '빠르다', '느리다'처럼 시간으로 결정되지 않고 "완료까지 걸리는 절차의 수"로 결정된다.

이렇게 표현되는 알고리즘의 속도를 BigO라고 하는데, BigO를 사용하면 시간복잡도를 빠르게 설명할 수 있다.
BigO를 이해함으로써 알고리즘 분석을 빠르게 할 수 있고, 언제 무엇을 쓸지 빠르게 파악이 가능하다.

BigO

O(1) (constans time (상수시간))

def print_first(arr):
	print(arr[0])

배열의 첫 번째를 프린트하는 python 함수가 있다. 배열 사이즈와 상관없이 이 함수는 동일한 수의 스텝이 필요하다.

이 함수의 시간복잡도는 N의 사이즈와 상관없이 끝내는데 동일한 숫자의 스텝이 필요하므로 constant time (상수시간)이라고 할 수 있다.
BigO에서는 O(1)이라고 읽는다.

def print_first(arr):
	print(arr[0])
    print(arr[0])

이번엔 배열의 첫 번째를 두 번 프린트한다. 이 함수를 끝내기 위해 2개의 스텝이 필요하다.
2개의 스텝이 필요함에도 이런 경우 O(2)라고 하지 않고 똑같이 O(1)이라고 한다. BigO는 함수의 디테일과 상관없이 input되는 아이템의 사이즈에 따라 결과값이 어떻게 바뀌는지를 따지기 때문에 여전히 O(1)로 표현한다.

O(N) (선형 시간복잡도)

def print_all(arr):
	for n in arr:
    	print(n)

배열의 각 아이템을 다 프린트하는 python 함수가 있다. 배열 사이즈가 10이라면 10번, 배열 사이즈가 100이라면 100번 프린트하게 된다.
input되는 아이템 사이즈에 따라 스텝도 증가하므로 이런 경우 O(N)이라고 한다.

def print_all(arr):
	for n in arr:
    	print(n)
    for n in arr:
    	print(n)

위에서 언급한 바와 같이, for문을 두 번 돌려서 두 번 프린트한다고 해서 O(2N)이 되는 것이 아닌 여전히 O(N)이 된다.

O($n^2$) (Quadratic Time(2차 시간))

2차 시간은 Nested Loops(중첩 반복)이 있을 때 발생한다.

def print_twice(arr):
	for n in arr:
    	for x in arr:
        	print(x, n)

이 함수는 배열의 각 아이템에 대해 루프를 반복하여 실행하므로 시간 복잡도가 input의 $n^2$가 된다. 즉, input이 10개라면 완성하는데 100번의 스텝이 필요하다.

따라서 선형 시간복잡도가 더 효율적인 것이다.

O(log N) (Logarithmic Time(로그 시간))

이진검색 알고리즘을 설명할 때 사용하는 것이다.
엄밀히 말하면 $\log_2 32$이지만 BigO의 특성상 밑 숫자 (base)는 사라진다.

이전 포스트에서 이야기한 것처럼 선형 시간복잡도보단 효율적이지만, 정렬되지 않은 배열에는 사용할 수 없다.