시간 복잡도(Time Complexity)
· 알고리즘을 수행하는데 사용되는 연산들의 횟수에 대한 것을 상대적 지표로 나타낸 것
(절대적 시간 X)
· 효율적인 알고리즘 구현
→ 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘 구성
(시간 복잡도는 알고리즘 효율성을 판단하기 위한 지표)
시간 복잡도 표기법(점근적 표기법)
· Big-O(빅-오) 표기법 : 최악의 경우를 고려(상한 점근)
→ O(n) : 최악의 경우 n번까지 수행되면 프로그램이 종료
* 최악의 시간까지 고려해야 그에 맞는 대응이 가능

O(1) < O(log n) < O(n) < O(nlog n) < O(n^2) < O(2^n) < O(n!)
· O(1) : 상수 시간 알고리즘(constant time algorithm)
- 입력값이 증가하더라도 시간은 일정
→ 입력값의 크기에 상관없이 출력값을 얻어낼 수 있다.
ex) 배열에 있는 항목을 인덱스를 사용하여 접근, 집합 내 요소로의 접근 등
data = [1, 2, 3, 4]
print(data[2])
· O(log n) : 로그 시간 알고리즘(logarithmic time algorithm)
- Big-O 표기법 중 O(1) 다음으로 빠른 시간 복잡도를 가짐
- BST(Binary Search Tree)의 값 탐색 또한 O(log n)의 시간 복잡도를 가진 알고리즘
↳ 원하는 값을 탐색할 때, 노드를 이동할 때마다 경우의 수가 절반으로 줄어듬
ex) 이진 검색 등
data = [1, 2, 3, 5, 8, 22, 34, 55]
for index in range(0, len(data), 3):
print(data[index])
· O(n) : 선형 시간 알고리즘(linear time algorithm)
- 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미
- 입력값이 커지면 커질수록 계수의 의미가 점점 없어지기 때문에, 같은 비율로 증가하고 있다면 계수 상관 없이 O(n)으로 표기
ex) 중첩되지 않은 통상의 반복문, 선형 검색, 자연수의 거듭제곱 등
data = [1, 2, 3, 4, 5]
for n in data:
print(n)
· O(nlog n) : n 로그 시간 알고리즘(n logarithmic time algorithm)
ex) 퀵 정렬(Quick Sort) 등
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
lesser_arr, equal_arr, greater_arr = [], [], []
for num in arr:
if num < pivot:
lesser_arr.append(num)
elif num > pivot:
greater_arr.append(num)
else:
equal_arr.append(num)
return quick_sort(lesser_arr) + equal_arr + quick_sort(greater_arr)
· O(n^2) : 평방 시간(2차 시간) 알고리즘(quadratic time algorithm)
- 문제 해결 단계의 수가 입력값 n의 제곱으로 증가
- n이 적을 경우에만 사용해야 하는 비효율적인 알고리즘
ex) 이중 반복문, 버블정렬, 삽입정렬, 선택정렬 등
def bubble_sort(l):
swap = True
while swap:
swap = False
for i in range(len(l) - 1):
if l[i] > l[i + 1]:
l[i], l[i + 1] = l[i + 1], l[i]
swap = True
data = [41, 452, 223, 1, 23, 55, 666]
bubble_sort(data)
print(data)
· O(2^n) : 지수 시간 알고리즘(exponential time algorithm)
- n이 하나 증가할 때 마다, 걸리는 시간이 그전보다 2배로 걸리는 알고리즘
ex) 재귀로 구현하는 피보나치 수열
def recursive_fibonacchi(n):
if n <= 1:
return n
else:
return (recursive_fibonacchi(n - 1) + recursive_fibonacchi(n - 2))
steps = 10
# 양수만
if steps <= 0:
print("음수 X")
else:
print("직전 숫자와 그 전 숫자의 합이 현재 숫자 : ")
for i in range(steps):
print(recursive_fibonacchi(i))
· O(n!) : 팩토리얼 시간 알고리즘(factorial time alogrithm)
- 초 지수 시간(super-exponential)
- 시간 복잡도가 가장 큰 알고리즘
from math import factorial
print(factorial(1))
print(factorial(3))
print(factorial(5))
print(factorial(7))
- 리스트 자료형과 메서드의 시간 복잡도

- 집합(set) 자료형과 메소드의 시간 복잡도

- 딕셔너리(Dictionary) 자료형과 메소드의 시간 복잡도
