시간 복잡도(Big-O)¶

왜?¶

입력 크기(N)에 따라 허용 복잡도가 달라진다. - N ≤ 10^3: O(N^2) 가능 - N ≤ 10^5: O(N log N) 권장 - N ≤ 10^6: O(N) ~ O(N log N) - 10^9급 범위: O(log N) 이하

비유(도서관)¶

• O(1): 내 책상 위
• O(log N): 정렬된 책장, 절반씩(이분 탐색)
• O(N): 전부 훑기
• O(N^2): 모든 책끼리 비교
• O(2^N): 가능한 모든 조합

예시¶

• 선형 탐색: O(N)
• 이분 탐색: O(log N) (정렬 전제)