시간복잡도

빅 오 : 상한 접근

빅 오메가 : 하한 접근

빅 세타 : 평균

빅 오 표기법은 최악의 경우를 고려하기 때문에 프로그램이 실행되는 과정에서 소요되는 최악의 시간 까지 고려할 수 있다.

그렇기 때문에 빅 오 표기법을 가장 많이 사용한다.

최악의 경우가 발생하지 않길 바라며 시간을 계산하는 것 보다 ‘최악의 경도 고려하여 대비’하는 것이 바람직하다.

입력값의 변화에 따라 연산을 실행할 때, 연산횟수에 비해 시간이 얼마나 걸리는지를 표기하는 방법

O(1)

일정한 복잡도 (constant complexity)

입력값이 증가하더라도 시간이 늘지 않는다.

O(n)

선형 복잡도 (linear complexity)

입력값이 증가함에따라 시간 또한 일정 비율로 증가한다.

앞에 계수가 붙더라도 (예. O(2n) ) 입력값이 커지면 커질 수록 계수의 의미(영향력)은 퇴색되기 때문에 같은 비율로 증가하고 있다면, 2배 3배 5배 라도 O(n)이라고 표기한다.

O(log n)

로그 복잡도 (logarithmic complexity)

O(1) 다음으로 빠른 시간 복잡도

BST(Binary Search Tree) 에서는 원하는 값을 탐색할 때, 노드를 이동할 때마다 경우의 수가 절반으로 줄어든다.

up down 게임 처럼 매번 숫자를 제시할 때마다 경우의 수가 절반이 줄어들기 때문에

최악의 경우에도 금방 찾을 수 있다.

BST 값 탐색도 같은 로직으로, O(log n)의 시간 복잡도를 가진 알고리즘이다.

O(n²)

2차 복잡도(quadratic complexity) 입력값이 증가함에 따라 시간이 n의 제곱 수의 비율로 증가하는 것

O(ⅽⁿ)

기하급수적 복잡도(exponential complexity)

가장 느린 시간 복잡도

구현한 알고리즘이 해당 시간 복잡도라면 다른 접근방식을 고민해 보는 것이 좋다.

ex) 재귀로 구현하는 피보나치수열

def fibonacci(n) {
	if n <= 1 :
		return 1
	else:
		return fibonacci(n-1) + fibonacci(n-2)
}