알고리즘 실행 시간 (시간 복잡도)에 대해 알아보자

위에서 아래로 빠른 순

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)

표기	이름	의미	예시
O(1)	상수 시간	입력 크기와 관계없이 항상 같은 시간 (한 번의 연산)	배열에서 인덱스로 원소 접근
O(log n)	로그 시간	입력을 매번 절반씩 줄여가며 처리함. 입력이 커질수록 실행 시간이 느리게 증가	이진 탐색(Binary Search)
O(n)	선형 시간	모든 데이터를 한 번씩 확인해야 함. 입력 크기에 비례해서 실행 시간 증가	배열 전체 순회
O(n log n)	로그 선형 시간	n 개의 데이터 각각이 log n의 깊이에서 비교됨 효율적인 정렬 알고리즘들이 이에 속함	병합 정렬, 퀵 정렬 평균
O(n²)	제곱 시간	모든 원소 쌍을 비교하는 경우 n이 2배 되면 실행 시간은 4배	버블 정렬, 삽입 정렬
O(n³)	세제곱 시간	모든 조합을 탐색함. n이 2배 되면 실행 시간은 8배	3중 for문 알고리즘
O(2ⁿ)	지수 시간	가능한 모든 경우(부분집합 등)를 시도함. 입력 크기 조금만 커져도 급격히 증가	부분집합 탐색, 재귀적 조합
O(n!)	팩토리얼 시간	순열처럼 가능한 모든 순서를 전부 시도함. 매우 느림 (n이 10만 되어도 거의 불가능)	외판원 순회 문제(Brute force)