시간 복잡도와 Big-O(빅-오) 표기법을 알아보자

Time Complexity

효율적인 알고리즘이란, 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘.
시간 복잡도는 주로 Big-O 표기법으로 나타낸다.

Big-O Notation

"입력값의 변화에 따라 연산을 실행할 때,
연산 횟수에 비해 시간이 얼마만큼 걸리는가?"를 표기하는 방법이다.

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

O(1)

constant complexity라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않는다.
다시 말해 입력값의 크기와 관계없이, 즉시 출력값을 얻어낼 수 있다.

O(log n)

logarithmic complexity라고 하며, O(1) 다음으로 빠른 시간 복잡도를 가진다.
up & down 게임을 예로 들 수 있다.
BST(Binary Search Tree) 자료구조의 값 탐색도 같은 로직이다.

O(n)

linear complexity라고 하며, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가한다.
*반복문

O(n2)

quadratic complexity라고 하며,
입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가한다.
*이중 이상의 반복문

O(2n)

exponential complexity라고 하며 Big-O 표기법 중 가장 느린 시간 복잡도다.구현한 알고리즘의 시간 복잡도가 O(2n)이라면 다른 접근 방식을 고민해 보아야 한다.
재귀로 구현한 피보나치 수열은 O(2n)의 시간 복잡도를 가진 대표적인 알고리즘이다.

입력 데이터가 크다면 O(n) 혹은 O(log n)의 시간 복잡도를 만족할 수 있도록 문제를 풀어야 하지만, 주어진 데이터가 작다면, 신경쓰지 말고 문제를 푸는 것에 집중하자.