[CS 기초 #11] 복잡도 분석: Big-O 표기법 완벽 마스터

알고리즘의 성능을 예측하는 방법! Big-O 표기법을 알면 코드가 느려지기 전에 미리 알 수 있습니다. 최적화와 면접의 필수 지식입니다.

🎯 이 글을 읽고 나면

• Big-O 표기법이 무엇인지 정확히 설명할 수 있습니다
• O(1), O(n), O(log n), O(n²) 등의 차이를 이해합니다
• 코드를 보고 시간 복잡도를 계산할 수 있습니다
• 공간 복잡도와 시간 복잡도를 구분할 수 있습니다
• 상황에 맞는 최적의 알고리즘을 선택할 수 있습니다

📚 사전 지식

• 기본 프로그래밍: 반복문, 재귀 개념 이해
• 자료구조 기초: 스택과 큐, 배열 개념
• 수학 기초: 로그, 지수 개념 (모르셔도 예제로 이해 가능합니다!)

💡 핵심 개념 미리보기

Big-O 표기법은 알고리즘이 데이터가 많아질 때 얼마나 느려지는지를 나타냅니다. O(1)은 데이터가 아무리 많아도 속도가 똑같고, O(n)은 데이터가 2배면 2배 느려지며, O(n²)은 데이터가 2배면 4배 느려집니다. 이를 알면 100만 개 데이터에서도 빠른 코드를 작성할 수 있습니다!

---

📈 들어가며: 왜 복잡도 분석이 중요한가?

“이 코드가 더 빠를까, 저 코드가 더 빠를까?” 개발자라면 누구나 하는 고민입니다. 하지만 실행 시간을 측정하는 것만으로는 충분하지 않습니다!

오늘은 알고리즘의 효율성을 객관적으로 평가하는 복잡도 분석과 Big-O 표기법을 완벽하게 마스터해보겠습니다. 이 지식은 코드 최적화와 기술 면접의 필수 요소입니다!

🎯 복잡도 분석이란?

복잡도 분석은 알고리즘의 성능을 예측하는 방법입니다. 입력 크기가 커질수록 실행 시간이나 메모리 사용량이 어떻게 변하는지 분석합니다.

graph LR
    subgraph "복잡도 종류"
        TC[시간 복잡도<br/>Time Complexity]
        SC[공간 복잡도<br/>Space Complexity]
    end
    
    subgraph "분석 케이스"
        BC[최선 Best Case]
        AC[평균 Average Case]
        WC[최악 Worst Case]
    end
    
    TC --> BC
    TC --> AC
    TC --> WC
    SC --> BC
    SC --> AC
    SC --> WC

왜 실행 시간 측정만으로는 부족한가?

import time
import random

def why_big_o_matters():
    """실행 시간의 한계 시연"""
    
    # 두 가지 검색 알고리즘
    def linear_search(arr, target):
        for i in range(len(arr)):
            if arr[i] == target:
                return i
        return -1
    
    def binary_search(arr, target):
        left, right = 0, len(arr) - 1
        while left <= right:
            mid = (left + right) // 2
            if arr[mid] == target:
                return mid
            elif arr[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return -1
    
    # 작은 입력에서 테스트
    small_arr = sorted([random.randint(1, 100) for _ in range(10)])
    target = small_arr[5]
    
    # 선형 검색
    start = time.perf_counter()
    linear_search(small_arr, target)
    linear_time = time.perf_counter() - start
    
    # 이진 검색
    start = time.perf_counter()
    binary_search(small_arr, target)
    binary_time = time.perf_counter() - start
    
    print(f"n=10일 때:")
    print(f"선형 검색: {linear_time*1000000:.2f} μs")
    print(f"이진 검색: {binary_time*1000000:.2f} μs")
    
    # 큰 입력에서 테스트
    large_arr = sorted(range(1000000))
    target = 999999
    
    start = time.perf_counter()
    linear_search(large_arr, target)
    linear_time = time.perf_counter() - start
    
    start = time.perf_counter()
    binary_search(large_arr, target)
    binary_time = time.perf_counter() - start
    
    print(f"\nn=1,000,000일 때:")
    print(f"선형 검색: {linear_time*1000:.2f} ms")
    print(f"이진 검색: {binary_time*1000:.2f} ms")
    print(f"속도 차이: {linear_time/binary_time:.0f}배")

why_big_o_matters()

📊 Big-O 표기법

Big-O는 알고리즘의 최악의 경우 성능을 나타냅니다. 입력 크기 n이 무한대로 갈 때의 성장률을 표현합니다.

주요 복잡도 클래스

import numpy as np
import matplotlib.pyplot as plt

def visualize_complexities():
    """복잡도 시각화"""
    n = np.linspace(1, 100, 100)
    
    complexities = {
        'O(1)': np.ones_like(n),
        'O(log n)': np.log2(n),
        'O(n)': n,
        'O(n log n)': n * np.log2(n),
        'O(n²)': n ** 2,
        'O(2ⁿ)': 2 ** np.minimum(n, 20)  # 20 이상은 너무 커서 제한
    }
    
    # 복잡도별 성장률 출력
    print("입력 크기에 따른 연산 횟수:")
    print("-" * 60)
    print(f"{'n':<10} {'O(1)':<10} {'O(log n)':<10} {'O(n)':<10} {'O(n log n)':<12} {'O(n²)':<10}")
    print("-" * 60)
    
    for size in [1, 10, 100, 1000, 10000]:
        o1 = 1
        ologn = int(np.log2(size)) if size > 0 else 0
        on = size
        onlogn = int(size * np.log2(size)) if size > 0 else 0
        on2 = size ** 2
        
        print(f"{size:<10} {o1:<10} {ologn:<10} {on:<10} {onlogn:<12} {on2:<10}")

visualize_complexities()

복잡도 순서

graph TB
    O1[O<sub>1</sub> - 상수]
    Ologn[O<sub>log n</sub> - 로그]
    On[O<sub>n</sub> - 선형]
    Onlogn[O<sub>n log n</sub> - 선형로그]
    On2[O<sub>n²</sub> - 이차]
    On3[O<sub>n³</sub> - 삼차]
    O2n[O<sub>2ⁿ</sub> - 지수]
    Onfact[O<sub>n!</sub> - 팩토리얼]
    
    O1 --> Ologn
    Ologn --> On
    On --> Onlogn
    Onlogn --> On2
    On2 --> On3
    On3 --> O2n
    O2n --> Onfact
    
    style O1 fill:#90EE90
    style Ologn fill:#90EE90
    style On fill:#90EE90
    style Onlogn fill:#FFD700
    style On2 fill:#FFD700
    style On3 fill:#FFA500
    style O2n fill:#FF6347
    style Onfact fill:#FF0000

🔍 시간 복잡도 분석

기본 규칙

class ComplexityRules:
    """Big-O 계산 규칙"""
    
    @staticmethod
    def rule1_drop_constants():
        """규칙 1: 상수 무시"""
        # O(2n) → O(n)
        # O(n/2) → O(n)
        # O(1000) → O(1)
        
        def example(n):
            # O(3n) = O(n)
            for i in range(n):
                print(i)
            for i in range(n):
                print(i)
            for i in range(n):
                print(i)
    
    @staticmethod
    def rule2_drop_lower_terms():
        """규칙 2: 낮은 차수 항 무시"""
        # O(n² + n) → O(n²)
        # O(n³ + n² + n + 1) → O(n³)
        
        def example(n):
            # O(n² + n) = O(n²)
            for i in range(n):
                for j in range(n):
                    print(i, j)  # n²
            
            for i in range(n):
                print(i)  # n
    
    @staticmethod
    def rule3_different_inputs():
        """규칙 3: 다른 입력은 다른 변수"""
        # 두 배열을 처리하면 O(a + b) 또는 O(a * b)
        
        def example(arr1, arr2):
            # O(a + b)
            for item in arr1:
                print(item)
            for item in arr2:
                print(item)
        
        def example2(arr1, arr2):
            # O(a * b)
            for item1 in arr1:
                for item2 in arr2:
                    print(item1, item2)
    
    @staticmethod
    def rule4_worst_case():
        """규칙 4: 최악의 경우 고려"""
        def linear_search(arr, target):
            # 최선: O(1) - 첫 번째 원소
            # 평균: O(n/2) = O(n)
            # 최악: O(n) - 마지막 원소 또는 없음
            for i in range(len(arr)):
                if arr[i] == target:
                    return i
            return -1

복잡도 분석 예제

def analyze_complexity():
    """다양한 코드의 복잡도 분석"""
    
    # O(1) - 상수 시간
    def constant_time(arr):
        """배열의 첫 번째 원소 반환"""
        if len(arr) > 0:
            return arr[0]
        return None
    
    # O(log n) - 로그 시간
    def logarithmic_time(n):
        """n을 반으로 줄여가며 처리"""
        count = 0
        while n > 1:
            n = n // 2
            count += 1
        return count
    
    # O(n) - 선형 시간
    def linear_time(arr):
        """배열의 합 계산"""
        total = 0
        for num in arr:
            total += num
        return total
    
    # O(n log n) - 선형로그 시간
    def linearithmic_time(arr):
        """병합 정렬"""
        if len(arr) <= 1:
            return arr
        
        mid = len(arr) // 2
        left = linearithmic_time(arr[:mid])
        right = linearithmic_time(arr[mid:])
        
        # 병합 O(n)
        result = []
        i = j = 0
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                result.append(left[i])
                i += 1
            else:
                result.append(right[j])
                j += 1
        
        result.extend(left[i:])
        result.extend(right[j:])
        return result
    
    # O(n²) - 이차 시간
    def quadratic_time(arr):
        """모든 쌍의 합"""
        result = []
        for i in range(len(arr)):
            for j in range(len(arr)):
                result.append(arr[i] + arr[j])
        return result
    
    # O(2ⁿ) - 지수 시간
    def exponential_time(n):
        """피보나치 (재귀)"""
        if n <= 1:
            return n
        return exponential_time(n-1) + exponential_time(n-2)
    
    # 복잡도 정리
    complexities = {
        "constant_time": "O(1)",
        "logarithmic_time": "O(log n)",
        "linear_time": "O(n)",
        "linearithmic_time": "O(n log n)",
        "quadratic_time": "O(n²)",
        "exponential_time": "O(2ⁿ)"
    }
    
    print("함수별 시간 복잡도:")
    for func, complexity in complexities.items():
        print(f"  {func:20}: {complexity}")

analyze_complexity()

💾 공간 복잡도 분석

공간 복잡도는 알고리즘이 사용하는 메모리의 양을 나타냅니다.

class SpaceComplexity:
    """공간 복잡도 예제"""
    
    @staticmethod
    def constant_space(arr):
        """O(1) 공간 - 상수 공간"""
        # 입력 크기와 관계없이 고정된 변수만 사용
        total = 0
        max_val = float('-inf')
        
        for num in arr:
            total += num
            max_val = max(max_val, num)
        
        return total, max_val
    
    @staticmethod
    def linear_space(n):
        """O(n) 공간 - 선형 공간"""
        # 입력 크기에 비례하는 공간 사용
        arr = []
        for i in range(n):
            arr.append(i * 2)
        return arr
    
    @staticmethod
    def quadratic_space(n):
        """O(n²) 공간 - 이차 공간"""
        # n x n 행렬 생성
        matrix = []
        for i in range(n):
            row = []
            for j in range(n):
                row.append(i * j)
            matrix.append(row)
        return matrix
    
    @staticmethod
    def recursive_space(n):
        """O(n) 공간 - 재귀 호출 스택"""
        # 재귀 깊이가 n이므로 O(n) 공간
        if n <= 0:
            return 0
        return n + SpaceComplexity.recursive_space(n - 1)
    
    @staticmethod
    def analyze_space_usage():
        """공간 사용량 분석"""
        import sys
        
        # 다양한 자료구조의 메모리 사용량
        n = 1000
        
        # 리스트
        list_1d = [i for i in range(n)]
        list_2d = [[i*j for j in range(n)] for i in range(n)]
        
        # 딕셔너리
        dict_small = {i: i*2 for i in range(n)}
        
        # 집합
        set_data = set(range(n))
        
        print("메모리 사용량 (bytes):")
        print(f"1D 리스트 (n={n}): {sys.getsizeof(list_1d):,}")
        print(f"2D 리스트 (n²={n*n}): {sys.getsizeof(list_2d):,}")
        print(f"딕셔너리 (n={n}): {sys.getsizeof(dict_small):,}")
        print(f"집합 (n={n}): {sys.getsizeof(set_data):,}")

SpaceComplexity.analyze_space_usage()

🎯 복잡도 분석 실전

1. 반복문 분석

def loop_complexity_analysis():
    """반복문 복잡도 분석"""
    
    def single_loop(n):
        """단일 반복문 - O(n)"""
        count = 0
        for i in range(n):
            count += 1
        return count
    
    def nested_loops(n):
        """중첩 반복문 - O(n²)"""
        count = 0
        for i in range(n):
            for j in range(n):
                count += 1
        return count
    
    def triple_nested(n):
        """3중 중첩 - O(n³)"""
        count = 0
        for i in range(n):
            for j in range(n):
                for k in range(n):
                    count += 1
        return count
    
    def dependent_loops(n):
        """종속적 반복문 - O(n²)"""
        count = 0
        for i in range(n):
            for j in range(i):  # j는 i에 종속
                count += 1
        # 실제 연산 횟수: 1+2+3+...+(n-1) = n(n-1)/2 = O(n²)
        return count
    
    def logarithmic_loop(n):
        """로그 반복문 - O(log n)"""
        count = 0
        i = 1
        while i < n:
            count += 1
            i *= 2  # 매번 2배씩 증가
        return count
    
    def nested_different(n, m):
        """다른 크기 중첩 - O(n*m)"""
        count = 0
        for i in range(n):
            for j in range(m):
                count += 1
        return count
    
    # 테스트
    n = 100
    print("반복문 실행 횟수:")
    print(f"단일 반복문 O(n): {single_loop(n)}")
    print(f"중첩 반복문 O(n²): {nested_loops(n)}")
    print(f"종속 반복문 O(n²): {dependent_loops(n)}")
    print(f"로그 반복문 O(log n): {logarithmic_loop(n)}")

loop_complexity_analysis()

2. 재귀 복잡도 분석

def recursive_complexity():
    """재귀 함수 복잡도 분석"""
    
    # O(n) - 선형 재귀
    def factorial(n):
        """팩토리얼 - T(n) = T(n-1) + O(1) = O(n)"""
        if n <= 1:
            return 1
        return n * factorial(n - 1)
    
    # O(2ⁿ) - 지수 재귀
    def fibonacci_naive(n):
        """피보나치 (비효율) - T(n) = T(n-1) + T(n-2) + O(1) = O(2ⁿ)"""
        if n <= 1:
            return n
        return fibonacci_naive(n-1) + fibonacci_naive(n-2)
    
    # O(n) - 최적화된 피보나치
    def fibonacci_optimized(n, memo={}):
        """피보나치 (메모이제이션) - O(n)"""
        if n in memo:
            return memo[n]
        if n <= 1:
            return n
        
        memo[n] = fibonacci_optimized(n-1, memo) + fibonacci_optimized(n-2, memo)
        return memo[n]
    
    # O(log n) - 이진 탐색
    def binary_search_recursive(arr, target, left, right):
        """이진 탐색 - T(n) = T(n/2) + O(1) = O(log n)"""
        if left > right:
            return -1
        
        mid = (left + right) // 2
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            return binary_search_recursive(arr, target, mid + 1, right)
        else:
            return binary_search_recursive(arr, target, left, mid - 1)
    
    # 마스터 정리 (Master Theorem)
    print("재귀 복잡도 (마스터 정리):")
    print("T(n) = aT(n/b) + f(n)")
    print("• T(n) = T(n-1) + O(1) → O(n)")
    print("• T(n) = 2T(n/2) + O(n) → O(n log n)")
    print("• T(n) = 2T(n/2) + O(1) → O(n)")
    print("• T(n) = T(n/2) + O(1) → O(log n)")
    print("• T(n) = 2T(n-1) + O(1) → O(2ⁿ)")

recursive_complexity()

3. 분할 상환 분석 (Amortized Analysis)

class AmortizedAnalysis:
    """분할 상환 분석"""
    
    @staticmethod
    def dynamic_array():
        """동적 배열의 분할 상환 분석"""
        class DynamicArray:
            def __init__(self):
                self.capacity = 1
                self.size = 0
                self.array = [None] * self.capacity
                self.resize_count = 0
                self.total_operations = 0
            
            def append(self, value):
                if self.size == self.capacity:
                    # 크기 2배로 확장
                    self.resize()
                
                self.array[self.size] = value
                self.size += 1
                self.total_operations += 1
            
            def resize(self):
                self.capacity *= 2
                new_array = [None] * self.capacity
                
                # 기존 원소 복사 - O(n)
                for i in range(self.size):
                    new_array[i] = self.array[i]
                    self.total_operations += 1
                
                self.array = new_array
                self.resize_count += 1
        
        # 분석
        arr = DynamicArray()
        n = 1000
        
        for i in range(n):
            arr.append(i)
        
        print(f"동적 배열 분할 상환 분석 (n={n}):")
        print(f"  총 삽입: {n}")
        print(f"  리사이즈 횟수: {arr.resize_count}")
        print(f"  총 연산: {arr.total_operations}")
        print(f"  평균 연산/삽입: {arr.total_operations/n:.2f}")
        print(f"  분할 상환 복잡도: O(1)")
    
    @staticmethod
    def stack_with_min():
        """최소값을 O(1)에 반환하는 스택"""
        class MinStack:
            def __init__(self):
                self.stack = []
                self.min_stack = []
            
            def push(self, val):
                self.stack.append(val)
                if not self.min_stack or val <= self.min_stack[-1]:
                    self.min_stack.append(val)
            
            def pop(self):
                if self.stack:
                    val = self.stack.pop()
                    if val == self.min_stack[-1]:
                        self.min_stack.pop()
                    return val
            
            def get_min(self):
                # O(1) - 분할 상환
                return self.min_stack[-1] if self.min_stack else None
        
        print("\n최소값 스택:")
        print("  push: O(1)")
        print("  pop: O(1)")
        print("  get_min: O(1)")
        print("  공간: O(n)")

AmortizedAnalysis.dynamic_array()
AmortizedAnalysis.stack_with_min()

📊 복잡도 비교와 선택

알고리즘 선택 가이드

def algorithm_selection_guide():
    """상황별 알고리즘 선택 가이드"""
    
    scenarios = {
        "작은 데이터 (n < 100)": {
            "추천": "간단한 알고리즘 (버블 정렬, 선형 검색)",
            "이유": "오버헤드가 적고 구현이 간단",
            "복잡도": "O(n²)도 충분히 빠름"
        },
        "중간 데이터 (100 ≤ n < 10,000)": {
            "추천": "효율적인 알고리즘 (퀵 정렬, 이진 검색)",
            "이유": "성능과 구현 복잡도의 균형",
            "복잡도": "O(n log n) 선호"
        },
        "큰 데이터 (n ≥ 10,000)": {
            "추천": "최적화된 알고리즘 (기수 정렬, 해시 테이블)",
            "이유": "성능이 최우선",
            "복잡도": "O(n) 또는 O(n log n) 필수"
        },
        "실시간 시스템": {
            "추천": "예측 가능한 알고리즘 (힙 정렬)",
            "이유": "최악의 경우도 보장",
            "복잡도": "최악 복잡도 중요"
        },
        "메모리 제한": {
            "추천": "제자리 알고리즘 (퀵 정렬, 힙 정렬)",
            "이유": "추가 공간 최소화",
            "복잡도": "공간 O(1) 또는 O(log n)"
        }
    }
    
    print("알고리즘 선택 가이드:")
    print("=" * 60)
    for scenario, info in scenarios.items():
        print(f"\n{scenario}:")
        for key, value in info.items():
            print(f"  {key}: {value}")
    
    # 실제 비교 예제
    import time
    import random
    
    def bubble_sort(arr):
        """O(n²) - 간단하지만 느림"""
        n = len(arr)
        for i in range(n):
            for j in range(0, n-i-1):
                if arr[j] > arr[j+1]:
                    arr[j], arr[j+1] = arr[j+1], arr[j]
    
    def quick_sort(arr):
        """O(n log n) 평균 - 빠름"""
        if len(arr) <= 1:
            return arr
        pivot = arr[len(arr) // 2]
        left = [x for x in arr if x < pivot]
        middle = [x for x in arr if x == pivot]
        right = [x for x in arr if x > pivot]
        return quick_sort(left) + middle + quick_sort(right)
    
    # 성능 비교
    sizes = [100, 1000, 5000]
    print("\n\n정렬 알고리즘 실제 성능 비교:")
    print("-" * 60)
    print(f"{'크기':<10} {'버블 정렬 O(n²)':<20} {'퀵 정렬 O(n log n)':<20}")
    print("-" * 60)
    
    for size in sizes:
        arr1 = [random.randint(1, 1000) for _ in range(size)]
        arr2 = arr1.copy()
        
        # 버블 정렬
        start = time.perf_counter()
        bubble_sort(arr1)
        bubble_time = time.perf_counter() - start
        
        # 퀵 정렬
        start = time.perf_counter()
        quick_sort(arr2)
        quick_time = time.perf_counter() - start
        
        print(f"{size:<10} {bubble_time*1000:<20.2f}ms {quick_time*1000:<20.2f}ms")

algorithm_selection_guide()

💡 실전 문제와 복잡도 최적화

문제 1: Two Sum 최적화

def two_sum_optimization():
    """Two Sum 문제의 복잡도 최적화"""
    
    # O(n²) 해법 - 브루트 포스
    def two_sum_naive(nums, target):
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] + nums[j] == target:
                    return [i, j]
        return []
    
    # O(n) 해법 - 해시 테이블
    def two_sum_optimized(nums, target):
        seen = {}
        for i, num in enumerate(nums):
            complement = target - num
            if complement in seen:
                return [seen[complement], i]
            seen[num] = i
        return []
    
    # 비교
    nums = [2, 7, 11, 15]
    target = 9
    
    print("Two Sum 최적화:")
    print(f"입력: {nums}, target = {target}")
    print(f"O(n²) 해법: {two_sum_naive(nums, target)}")
    print(f"O(n) 해법: {two_sum_optimized(nums, target)}")
    print("\n복잡도 비교:")
    print("  Naive: 시간 O(n²), 공간 O(1)")
    print("  Optimized: 시간 O(n), 공간 O(n)")

two_sum_optimization()

문제 2: 최대 부분 배열 합

def max_subarray_sum():
    """최대 부분 배열 합 - 복잡도 개선"""
    
    # O(n³) - 브루트 포스
    def max_subarray_n3(arr):
        n = len(arr)
        max_sum = float('-inf')
        
        for i in range(n):
            for j in range(i, n):
                current_sum = 0
                for k in range(i, j + 1):
                    current_sum += arr[k]
                max_sum = max(max_sum, current_sum)
        
        return max_sum
    
    # O(n²) - 개선된 브루트 포스
    def max_subarray_n2(arr):
        n = len(arr)
        max_sum = float('-inf')
        
        for i in range(n):
            current_sum = 0
            for j in range(i, n):
                current_sum += arr[j]
                max_sum = max(max_sum, current_sum)
        
        return max_sum
    
    # O(n) - 카데인 알고리즘
    def max_subarray_kadane(arr):
        max_sum = current_sum = arr[0]
        
        for num in arr[1:]:
            current_sum = max(num, current_sum + num)
            max_sum = max(max_sum, current_sum)
        
        return max_sum
    
    # 테스트
    arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
    
    print("최대 부분 배열 합:")
    print(f"입력: {arr}")
    print(f"O(n³) 결과: {max_subarray_n3(arr)}")
    print(f"O(n²) 결과: {max_subarray_n2(arr)}")
    print(f"O(n) 결과: {max_subarray_kadane(arr)}")

max_subarray_sum()

🎯 핵심 정리

꼭 기억해야 할 5가지

1. Big-O는 최악의 경우를 나타냄
2. 상수와 낮은 차수 항은 무시
3. 입력이 다르면 변수도 다르게 (O(a+b))
4. 재귀는 마스터 정리로 분석
5. 공간 복잡도도 중요함

복잡도 선택 가이드

• n < 100: 어떤 알고리즘도 OK
• n < 10,000: O(n²)까지 가능
• n < 1,000,000: O(n log n) 필요
• n > 1,000,000: O(n) 또는 O(log n) 필수

📚 추가 학습 자료

추천 자료

• “Introduction to Algorithms” - CLRS
• “Algorithm Design Manual” - Skiena
• Big-O Cheat Sheet (bigocheatsheet.com)

연습 문제

• 주어진 코드의 시간/공간 복잡도 분석
• 복잡도 개선 문제
• 최적 알고리즘 선택 문제

🚀 다음 시간 예고

다음 포스트에서는 정렬 알고리즘을 다룹니다. 버블 정렬부터 퀵 정렬, 기수 정렬까지 모든 정렬 알고리즘을 마스터해보겠습니다!

---

📌 시리즈 네비게이션

순서	제목	링크
10	해시 테이블: O(1) 검색의 비밀	← 이전 글
11	복잡도 분석: Big-O 표기법 완벽 이해 ✅	현재 글
12	정렬 알고리즘: 버블 정렬부터 퀵 정렬까지	다음 글 →

📋 전체 시리즈 목차 보기

기초 이론편

1. CS 입문 ✅
2. 컴퓨터 구조 ✅
3. 이진수와 논리 게이트 ✅
4. 운영체제 기초 ✅
5. 네트워크 기초 ✅

자료구조편

1. 배열과 연결 리스트 ✅
2. 스택과 큐 ✅
3. 트리 구조 ✅
4. 그래프 ✅
5. 해시 테이블 ✅

알고리즘편

1. 복잡도 분석 ✅
2. 정렬 알고리즘
3. 탐색 알고리즘
4. 동적 계획법
5. 그리디와 분할정복

실무 응용편

1. 데이터베이스 이론
2. 소프트웨어 공학
3. 보안 기초
4. 분산 시스템
5. CS 종합과 면접 준비