[Python] 빅오표기법

빅오

알고리즘의 효율성을 수학적으로 표기해주는 표기법이다. 보통 알고리즘의 시간 복잡도와 공간 복잡도를 나타내는데 사용한다.

• 시간 복잡도 : 연산 횟수
• 공간 복잡도 : 사용하는 메모리 양

O(1)

일정한 복잡도(constant complexity)
입력 데이터의 크기에 상관없이 항상 같은 시간이 걸리는 알고리즘

n = input()

print(n)

O(n)

선형 복잡도(linear complexity)
입력 데이터의 크기에 비례해서 y=x 그래프 형태로 처리 시간이 증가하는 알고리즘

n = int(input())

for i in range(n):
	print(i)

O(n**2)

2차 복잡도(quadratic complexity)
입력 데이터 n 만큼 반복하고 그 안에서 n만큼 반복하는 알고리즘

• 크기가 1인 데이터들이 들어있는 가로,세로 길이가 n인 정사각형틀이다.

n = int(input())

for i in range(n):
	for j in range(n):
    	print(i, j)

O(2**n)

기하급수적 복잡도(exponential complexity)
빅오표기법 중 가장 느린 시간 복잡도를 가진다.
대표적인 예로 피보나치 수열이 있다.

n = int(input())

def fibo(n):
	if (n<=1):
    	return 1
    else:
    	return fibo(n-1) + fibo(n-2)
    
print(fibo(n))

O(log n)

로그 복잡도(logarithmic complexity)
빅오표기법 중 O(1) 다음으로 가장 빠른 시간 복잡도를 가진다.
대표적인 예로 이진 탐색(binary search)이 있다.
-> 중간값이 찾고자 하는 값일 때 종료

def binary(arr, target, start, end):
	# 범위 내에서 찾지 못했을 때
	if (start > end):
    	return -1
    # 중간값의 위치
    mid = (start + end) // 2
    
    # target이 중간값의 data와 같을 때
    if arr[mid] == target:
    	return mid
    # target이 중간값의 data보다 작을 때
    elif arr[mid] > target:
    	# 왼쪽 구간 탐색
    	end = mid - 1
    # 중간값의 data가 target보다 작을 때
    elif arr[mid] < target:
    	# 오른쪽 구간 탐색
    	start = mid + 1
    # 작아진 구간을 탐색
    return binary(arr, target, start, end)