문제를 해결하기 위한 일련의 절차
알고리즘이 문제를 해결하는 데 필요한 계산 자원(시간, 메모리 등)의 양을 나타내는 개념입니다.
계산 복잡도를 측정하는 데에는 주로 시간 복잡도(Time complexity)와 공간 복잡도(Space complexity)가 사용됩니다.
시간 복잡도는 알고리즘이 문제를 해결하는 데 걸리는 시간의 양을 나타냅니다. 입력 크기에 따라 시간이 어떻게 증가하는지를 나타내는데, 이를 Big-O 표기법으로 나타내는 경우가 많습니다.
O(1)
입력값(N)이 증가해도 실행시간은 동일한 알고리즘, index로 접근하여 바로 처리할 수 있는 연산 과정의 시간 복잡도 → 기본 연산 수라고 생각하면 편함
ex) stack의 push, pop
O(log N)
연산이 한 번 실행될 때 마다 데이터의 크기가 절반 감소하는 알고리즘 (log의 지수는 항상 2)
ex) binary search 알고리즘, tree 형태 자료구조 탐색
O(N)
입력값(N)이 증가함에 따라 실행시간도 선형적으로 증가하는 알고리즘
ex) 1중 for문
O(N log N)
O(N)의 알고리즘과 O(log N)의 알고리즘이 중첩된 형태
ex) 퀵 / 병합 / 힙 정렬
O(N^2)
O(N)의 알고리즘과 O(log N)의 알고리즘이 중첩된 형태
ex) 2중 For 문, 삽입/거품/선택 정렬
O(2^N)
빅오 표기법 중 가장 느린 시간 복잡도로 주로 재귀적으로 수행하는 알고리즘이 이에 해당
ex) fibonacci 수열
Big-O(빅 오) 표기법: 알고리즘 최악의 실행 시간을 표기한다. 가장 많이 사용하는 표기법이다. 최소한 보장되는 성능을 표기하기 때문에 가장 일반적으로 사용한다.
Big-Ω(빅 오메가) 표기법: 알고리즘 최상의 실행 시간을 표기한다.
Big-θ(빅 세타) 표기법: 알고리즘 평균 실행 시간을 표기한다.