시간 복잡도와 Big-O Notation

1. 시간 복잡도

알고리즘이 실행되는 데 걸리는 시간
주로 입력 크기에 따라 알고리즘 성능이 어떻게 변하는지, 얼마나 효율적인지를 평가하는 지표
입력 크기와 알고리즘이 수행하는 연산 횟수간 상관관계를 나타내는 척도값
→ 입력 크기가 증가할수록 연산 횟수가 얼마나 증가하는가
→ 시간 복잡도와 로직의 수행 시간은 비례하므로 시간 복잡도 수치가 작을수록 효율적인 알고리즘을 뜻함

시간 복잡도를 표기하는 방법으로는 세가지 점근적 표기법이 있는데, 이 중에서 우선 "Big-O Notation"을 살펴보자.

2. 빅오 표기법 (Big-O Notation)

최악의 경우를 기준으로 알고리즘이 얼마나 느려질 수 있는지를 나타냄
시간 복잡도와 공간 복잡도를 계산할 수 있는데, 시간 복잡도는 입력 크기(N)에 따라 알고리즘이 얼마나 많은 연산을 수행하는지를 나타냄 (공간 복잡도는 입력 크기(N)에 따라 얼마나 많은 메모리를 사용하는지를 나타냄)
시간 복잡도에서는 입력 크기(N)가 커질수록 알고리즘이 얼마나 빠르게 실행시간이 늘어나는지를 표현함
연산 횟수나 단계 수를 기반으로 분석하는 것이라, 실제 실행 시간과는 다를 수 잇음 (컴퓨터 성능이나 하드웨어 상태에 따라 달라짐)

✅ 빅오 표기법 종류

왼쪽이 가장 효율적이고 오른쪽으로 갈수록 더 복잡해짐

시간 복잡도	설 명	예 시
$O(1)$	입력 크기에 상관없이 항상 일정한 시간이 걸리는 경우	리스트의 첫 번째 요소에 접근하기, 변수 할당, 스택의 push, pop
$O(log N)$	입력 크기가 커질수록 실행 시간이 매우 느리게 증가하는 경우	이진 탐색, 트리 형태 자료구조 탐색
$O(N)$	입력 크기에 비례하여 실행 시간이 증가하는 경우	리스트에서 특정 값을 찾기 (모든 요소를 탐색) → 단일 for문
$O(N log N)$	대부분의 효율적인 정렬 알고리즘의 시간 복잡도	병합, 힙 정렬, 퀵 정렬(평균적인 경우)
$O(N^2)$	입력 크기에 대해 제곱에 비례하는 시간이 걸리는 경우	이중 for문, 삽입/버블/선택 정렬
$O(2^N)$	빅오 표기법 중 가장 느린 시간 복잡도로, 주로 재귀적으로 수행하는 알고리즘이 이에 해당함	피보나치 수열, 완전 탐색

입력 데이터의 범위와 실행 시간 범위를 고려하기
보통 코드 1억 번 수행시간은 1초니까, 이 기준으로 전체 수행시간 어림잡아서 문제에 적용될 수 있는 알고리즘을 고려해볼 수 있음

예) N = 100이라면 $O(N^2)$ 정도의 시간 복잡도도 가능하지만, $O(2^N)$와 같은 지수 형태의 시간 복잡도는 비효율적일 수 있음