Big O Notation: 알고리즘 효율성 : 개념, 예제, 설명, 개요

프로그래밍을 하다 보면 가끔 코드가 점점 느려지는 걸 경험한 적이 있죠? 처음엔 별 문제없다가 데이터가 많아지면서 실행 속도가 확 줄어드는 경우 말이에요. 이럴 때 알아두면 좋은 게 바로 **빅오 표기법(Big O Notation)**입니다! 쉽게 말해서, 이 개념은 알고리즘이 입력 크기에 따라 얼마나 효율적으로 실행되는지를 분석하는 도구예요. 개발자나 데이터 과학자는 물론, 코딩 공부하는 누구에게나 필수적인 개념이죠!

이번 글에서는 빅오 표기법이 정확히 무엇인지, 어떻게 활용하는지, 그리고 현실 속에서는 어떻게 적용되는지를 하나씩 짚어볼 거예요. 어렵다고 겁먹을 필요 없어요! 친근한 예시와 함께 쉽게 설명해 드릴 테니까 편하게 읽어보세요.

 

---

 

빅오 표기법이란?

한마디로 입력 크기가 커질 때 알고리즘 성능이 어떻게 변하는지를 나타내는 방법이에요. 어떤 알고리즘은 데이터가 커져도 속도가 거의 변하지 않지만, 어떤 건 입력이 조금만 많아져도 실행 시간이 폭발적으로 늘어나죠.

왜 알아야 할까요?

• 성능 예측이 가능해요! 데이터가 커질수록 실행 속도가 어떻게 변할지 미리 짐작할 수 있죠.
• 효율적인 알고리즘을 고를 수 있어요! 여러 가지 방법이 있다면, 더 빠르고 가벼운 걸 선택하는 데 도움이 돼요.
• 최적화할 때 필수예요! 프로그램이 느려진다면, 어떤 부분을 개선해야 할지 찾는 데 유용하죠.

그럼 이제 다양한 빅오 표기법을 하나씩 살펴볼까요?

 

---

 

Big O Notation: 알고리즘 효율성 : 개념, 예제, 설명, 개요

 

대표적인 빅오 표기법들: 효율적인 순서대로 정리!

1. O(1) - 상수 시간 (언제나 빠름!)

입력 크기에 상관없이 실행 시간이 변하지 않는 알고리즘이에요. 데이터가 얼마나 많든 속도는 그대로죠!

예제:

# 배열에서 특정 요소 가져오기 (O(1))
def get_element(arr, index):
    return arr[index]

 

사용되는 곳:

• 배열에서 특정 위치의 값 조회
• 해시 테이블(딕셔너리)에서 데이터 찾기

 

---

 

2. O(log n) - 로그 시간 (효율 최고!)

입력이 많아져도 실행 시간이 그렇게 빨리 증가하지 않는 경우예요. 대표적인 예가 **이진 탐색(Binary Search)**이죠.

예제:

# 이진 탐색 (O(log n))
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

 

사용되는 곳:

• 정렬된 데이터에서 특정 값 찾기 (예: 전화번호부에서 이름 검색)
• 데이터베이스 인덱스 검색

 

---

 

3. O(n) - 선형 시간 (입력 크기만큼 증가!)

데이터가 많아질수록 실행 시간이 비례해서 증가하는 알고리즘이에요.

예제:

# 최대값 찾기 (O(n))
def find_max(arr):
    max_value = arr[0]
    for num in arr:
        if num > max_value:
            max_value = num
    return max_value

 

사용되는 곳:

• 리스트에서 최댓값 찾기
• 문서에서 특정 단어 검색하기

---

 

4. O(n log n) - 선형 로그 시간 (정렬할 때 자주 등장!)

대표적인 정렬 알고리즘들이 여기에 속해요. 예를 들어 **병합 정렬(Merge Sort)**이죠.

예제:

# 병합 정렬 (O(n log n))
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

 

사용되는 곳:

• 대량의 데이터를 정렬할 때 (예: 대형 데이터베이스 정렬)

 

---

5. O(n²) - 이차 시간 (반복문 많으면 주의!)

반복문이 중첩된 경우에 자주 등장하는 복잡도예요. 데이터가 많아질수록 실행 시간이 기하급수적으로 늘어나죠.

예제:

# 버블 정렬 (O(n²))
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]

 

사용되는 곳:

• 간단한 정렬 알고리즘 (작은 데이터에서는 괜찮지만, 큰 데이터에서는 비효율적!)

 

---

 

예제 1: 배열 순회

 

현실적인 이야기: 알고리즘은 이론과 다를 수도 있어요!

이론적으로 효율적이라도 실제 환경에서는 다른 요소들도 영향을 줄 수 있어요.

• 캐시 활용: 데이터가 메모리에 어떻게 저장되느냐에 따라 속도가 달라질 수 있어요.
• 병렬 처리: 요즘 컴퓨터는 여러 작업을 동시에 할 수 있어서, 이론적인 복잡도와 실제 성능이 다를 수 있어요.
• 하드웨어 성능: CPU, RAM 속도, 디스크 읽기/쓰기 속도도 알고리즘 실행 속도에 영향을 줍니다.

 

---

 

예제 2: Linked List와 Array

 

결론: 알고리즘 선택, 신중하게 하자!

빅오 표기법을 알면, 어떤 알고리즘이 더 효율적인지 쉽게 판단할 수 있어요. 하지만 이론만으로 결정하지 말고, 직접 실행해 보고 테스트하는 것도 중요합니다.

앞으로 코드 짤 때, 실행 속도가 영 느리다면 "어? 이거 혹시 O(n²) 아닌가?" 하고 의심해 볼 수도 있겠죠? 알고리즘을 설계할 때, 좀 더 효율적인 방법을 고민해 보세요!