[Python] 알고리즘 개념2 - Big-O 표기법 심화

 

 

 

📘 1. Big-O 표기법이란?

🚀 Big-O 표기법이란?

Big-O 표기법은 **알고리즘이 실행되는 데 걸리는 시간(시간복잡도)과 사용하는 메모리 크기(공간복잡도)**를 분석하는 방법입니다.
즉, 입력 크기(nn)가 증가할 때 알고리즘이 얼마나 효율적으로 작동하는지를 나타냅니다.
💡 왜 중요할까?

• 같은 기능을 수행하는 두 개의 알고리즘이 있을 때 어떤 것이 더 빠른지 비교할 수 있음
• 입력 크기가 커질수록 비효율적인 알고리즘은 실행 속도가 급격히 느려질 수 있음
• 코딩테스트나 면접에서 효율적인 알고리즘을 선택하는 기준이 됨

---

 

 

📘 2. Big-O의 다양한 유형

Big-O 표기법에서 가장 많이 사용되는 시간복잡도 유형은 다음과 같습니다.
시간복잡도 설명 예제

O(1)O(1)	입력 크기에 상관없이 항상 일정한 시간	리스트 첫 원소 접근 arr[0]
O(logn)O(log n)	입력 크기가 절반씩 줄어드는 경우	이진 탐색 (Binary Search)
O(n)O(n)	입력 크기에 비례하는 시간	리스트 전체 탐색 for i in arr:
O(n2)O(n^2)	중첩 반복문이 있는 경우	버블 정렬 (Bubble Sort)
O(n!)O(n!)	모든 경우의 수를 다 고려하는 경우	순열 생성 (Permutations)

 

 

🚀 좋은 코드 vs 나쁜 코드 비교

 

❌ 나쁜 코드 (O(n^2))

# 리스트에서 특정 값 찾기 (비효율적인 방법)
def find_number(arr, target):
    for num in arr:
        if num == target:
            return True
    return False  # O(n)

 

✅ 좋은 코드 (O(1))

# 리스트를 집합(set)으로 변환하여 검색 속도 개선
# 딕셔너리 또는 해시맵 사용 가능

def find_number_optimized(arr, target):
    num_set = set(arr)  # O(n)
    return target in num_set  # O(1)

 
💡 차이점: 리스트를 탐색하는 대신 해시맵(set)을 활용하면 검색 속도가 빨라짐!

---

 

 

📘 3. Big-O 계산법

 

🚀 Big-O를 쉽게 계산하는 규칙

1. 상수는 무시 → O(2n)O(2n) 은 O(n)O(n) 으로 간소화
2. 가장 높은 차수만 남김 → O(n+n2)O(n + n^2) 은 O(n2)O(n^2) 으로 표현
3. 다른 연산은 더 큰 복잡도 기준 적용 → O(n)+O(logn)O(n) + O(log n) 은 O(n)O(n) 으로 정리

 

🚀 예제 분석

# O(n + n^2) → O(n^2)
for i in range(n):
    print(i)  # O(n)
for i in range(n):
    for j in range(n):
        print(i, j)  # O(n^2)

 
💡 핵심: 작은 항은 큰 항에 비해 영향이 작기 때문에 최대 복잡도만 남겨서 표현

---

 

 

📘 4. Big-O 최적화 방법

 

 

🚀 효율적인 알고리즘 설계 전략

1. 반복문 줄이기 → 중첩 루프 제거 (O(n^2) → O(n))
2. 이진 탐색 사용 → 선형 탐색 대신 O(log n) 알고리즘 활용
3. 효율적인 자료구조 활용 → 리스트보다 해시맵(딕셔너리) 사용하면 검색 속도 개선
4. 동적 프로그래밍(DP) 활용 → 중복 연산 제거하여 속도 개선

 

🚀 좋은 코드 vs 나쁜 코드 비교 (정렬 예제)

 

❌ 나쁜 코드 (O(n^2))

# 버블 정렬 (비효율적인 정렬)
def bubble_sort(arr):
    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]

 

✅ 좋은 코드 (O(n log n))

# 내장 정렬 함수 사용 (퀵 정렬 기반)
def optimized_sort(arr):
    arr.sort()  # O(n log n)

💡 정리: 같은 정렬이라도 버블 정렬보다 퀵 정렬 기반의 sort()가 훨씬 빠름!

---