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

개발 공부/컴퓨터 과학

도이(doi) 2021. 6. 28. 10:31

728x90

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)

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

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

정리

728x90