Python_#4

hyena_lee·2025년 10월 4일

자료구조

목록 보기

7/15

🧩 점근 표기법이란?

“입력 크기(N)가 아주 커질 때, 알고리즘의 성장 속도(성능 추세) 를 수학적으로 표현한 것”
즉, 프로그램이 데이터가 많아질수록 얼마나 빠르게 느려지는가(또는 빨라지는가) 를
‘함수의 증가율’로 나타내는 표기법이에요.
점근 표기법(asymptotic notation)은 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법이다.
지금까지 이 함수는 N 정도의 시간과 공간이 걸리겠구나 하면서 분석했던 게 점근 표기법의 일종이라고 말할 수 있습니다.

💬 쉽게 말하면

상황	의미
N이 작을 때	실행 시간 차이가 별로 안 남
N이 커질 때	어떤 알고리즘이 훨씬 빠른지 / 느린지 확연히 차이남

➡ 그래서 점근 표기법은 “큰 입력일 때의 효율성”을 비교하는 도구예요.

📘 왜 “점근(asymptotic)”이라고 부를까?

“asymptotic”은 영어로 ‘점점 가까워지는’ 이라는 뜻이에요.
즉, “입력 N이 무한히 커질 때(∞로 갈수록)”
실행 시간이 어떤 식으로 ‘가까워지는지’를 보는 거예요.

👉 “N이 커질수록 실행 시간의 성장률이 어디에 수렴하느냐”
→ 이걸 보기 위해 점근 표기법을 씀.

⚙️ 대표적인 3가지 점근 표기법

이름	기호	읽는 법	뜻
Big-O (빅오)	O(f(n))	빅오	최악의 경우 상한선
Big-Theta (빅세타)	Θ(f(n))	빅 세타	평균적인 경우 정확한 성장률
Big-Omega (빅오메가)	Ω(f(n))	빅 오메가	최선의 경우 하한선

🧠 4️⃣ 그래프로 직관적으로 보기

실행시간
│
│ O(f(n)) ← 최악의 경우(가장 위)
│ Θ(f(n)) ← 평균적인 경우(중간)
│ Ω(f(n)) ← 최선의 경우(가장 아래)
│
│
└──────────────────────────▶ 입력 크기 N

이렇게 3개의 선은
입력 크기가 커질수록 실행시간이 어느 정도까지 커질 수 있는지(상한),
또는 줄어들 수 있는지(하한) 를 보여줌.

💡 각각 쉽게 예로 보기


def search(arr, target):
    for x in arr:
        if x == target:
            return True
    return False

경우	설명	표기
최선 (첫 번째에 찾음)	한 번에 찾음	Ω(1)
평균 (중간쯤 찾음)	N/2번 정도 탐색	Θ(N)
최악 (마지막 or 없음)	끝까지 탐색	O(N)

)

👉 이 함수의 점근적 시간복잡도는
보통 O(N) 으로 표현해요.
왜냐하면 “최악의 경우” 기준으로 잡는 게 일반적임.

📈 세 표기법 비교 요약

표기	의미	언제 쓰나	예시
O(f(n))	상한 (최악의 경우)	일반적으로 사용	O(N²), O(N log N)
Θ(f(n))	평균적인 경우	알고리즘 분석 시	Θ(N)
Ω(f(n))	하한 (최선의 경우)	참고용	Ω(1)

🧮 예제 비교

def double_loop(n):
    for i in range(n):
        for j in range(n):
            print(i, j)

반복 횟수는 n × n = n²

입력이 커질수록 실행 시간이 n²에 비례
➡️ 따라서 점근 표기법으로 표현하면 O(n²)

즉, “n이 아주 커지면 실행 시간은 n² 크기로 커진다”는 뜻이에요.

🧩 정리 요약표

표기	읽는 법	뜻	특징
O(f(n))	빅오	최악 시간 복잡도 (상한선)	가장 많이 사용됨
Θ(f(n))	빅세타	평균 시간 복잡도	실제 평균 성능 표현
Ω(f(n))	빅오메가	최선 시간 복잡도 (하한선)	참고용