Big O (알고리즘)

빠른 알고리즘은 느린 알고리즘 보다 우수합니다.

알고리즘의 속도는 하드웨어(컴퓨터)에 따라 다를 수 있어서 빠르다 느리다 라는 시간으로 말할 수 없고 대신

'완료까지 걸리는 절차의 수'로 결정됩니다.

 

예를 들면 linear search algorithm은 size가 N개면 N번의 절차가 필요합니다.

선형검색의 시간 복잡도 = O(N)

 

Big O notation(표기법)을 이용하면 시간 복잡도를 빠르게 설명할 수 있습니다. 또한, 알고리즘 분석을 빠르게 할 수 있습니다. 그래서 언제 무엇을 쓸지 빠르게 파악이 가능하고 자신의 코드를 평가 할 수 있습니다.

-> 미래에 어떻게 작동할지 알 수 있기 때문입니다....?

 

여기까지만 보면 뭔 표기법으로 자신의 코드를 평가한다는 것이지? 라는 생각이 드네요. ㅎㅎ

 

그래서 예시를 보겠습니다.

 

예시

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

파이썬 코드인데 배열과 배열의 첫번째 값을 나타낼 것이라는 의미라네요!

input size를 크게 변경해도 1번만에 나타낼 수 있습니다.

그래서 이 예시 함수의 시간복잡도는 constant time(상수 시간) 이라고 할 수 있습니다.

O(1) -> O of one

시간복잡도 (상수)

만약 함수를 두번 불러오게 되면 

 

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

이것 또한 O(1) 이라고 합니다. Big O는 함수의 디테일엔 관심이 없어서 그렇다고 합니다. 

 

상수에 신경을 쓰지 않는다고 합니다.

 

def print_first(arr)
	for n in arr;
	print(n)

배열의 size 가 10이면  10번 반복하겠죠?

O(N)으로 표현합니다.

 

def print_first(arr)
	for n in arr;
	print(n)
    	for n in arr;
	print(n)

이것 또한 O(N)으로 표현됩니다. 상수값은 무시합니다.

O(N)

 

Quadratic Time

다음 시간복잡도로는 Quadratic Time(2차 시간) 은 Nested Loops(중첩 반복)이 있을 때 발생합니다.

 

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

이렇게 되면 arr의 size가 10일 때 10의 제곱번 반복하기 때문에

O(N^2)

O(N^2)

Logarithmic time

로그시간 -> 로그는 지수의 정반대 개념이죠.

이진검색을 예로 들면 이진 검색은 경우의 수를 절반으로 줄여주는 기능을 하게 됩니다. 이진검색에 대해서는 다음에 자세히 다루고 싶은데 그냥 가볍게 생각하면 오름차순으로 정해진 숫자배열에서 어떤 숫자를 찾는 것인데 찾는 방법이 절반에서 하나 찾고 또 다음 절반에서 한번 찾고 결국 찾게 되는 그런 .... 것인데 뭐라고 하는지 모르겠네요. 아무튼 다른 분들이 작성한 것을 확인해보면 바로~ 이해될 겁니다.

그러니 결국 시간복잡도가 log의 값으로 줄어드는 기적을 일으켜줍니다.

O(log n)

O(log n)

 

 

알고리즘이 중요하다고 합니다. 유명한 알고리즘들을 공부하면서 면접을 준비해봐야겠습니다.

---

출처 : https://www.youtube.com/watch?v=BEVnxbxBqi8