[자료구조와 알고리즘] 알고리즘 스피드의 표현법 Big O

상수 시간

O(1)

N이 얼마나 큰 지에 상관없이 끝내는데 동일한 숫자의 스텝이 필요.

인풋 사이즈와 관계없이. 스텝이 정해진 알고리즘. 

대표적으로는 배열에서 값을 index으로 읽어올 때 해당 됨. 

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

 

선형 시간

O(N)

선형 검색과 유사함. 배열이 커질 때 필요한 스텝도 커짐. 

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

빅 오에서 상수는 필요없다.

예를들어서 위의 함수로 예시를 들어보겠다.

만약, 위의 식이 아래과 같이 표기 되면 두 번 작업하기 때문에 O(2N)이 될 것 같지만. 

빅 오에서는 상수를 무시하기 때문에 O(N)으로 표기한다. 

-> 인풋이 증가하면 스텝도 증가한다는 선형적 사실만 전달하면 되기 때문에. 

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

지수 시간 

O(n^2)

Quadratic Time (2차 시간)

Nested Loops(중첩 반복)이 있을 때 발생.

시간 복잡도는 input의 n^2

예를들어, input이 10개라면 100번의 스텝 필요.

-> 루프 안에서 루프를 실행하기 때문. 

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

로그 시간

O(log n)

이진검색 알고리즘을 설명할 때 사용. 

*이진 검색은 정렬되지 않은 배열에는 사용할 수 없음. 

정리

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