내 코드의 시간 복잡도(Big O)는 얼마일까?

Author: Zzabbis // Date: 2026-02-04

📝 내 코드의 시간 복잡도(Big O)는 얼마일까?

🎯 추천 대상: 코딩 테스트 준비생, 서버 응답 속도가 걱정되는 개발자
⏱️ 소요 시간: 머리로 계산 10분 → 10초 분석
🤖 추천 모델: 모든 대화형 AI (ChatGPT, Claude, Gemini 등)

“for문이 두 개 겹쳐있는데… 이게 O(N)인가 O(N^2)인가?”

코딩 테스트를 보거나 대용량 트래픽을 처리하는 로직을 짤 때, 시간 복잡도(Time Complexity) 분석은 필수입니다. 하지만 루프 안에 재귀 호출이 있거나 조건이 복잡해지면 계산하기 머리 아프시죠? AI에게 코드를 보여주면 Big-O 표기법으로 정확하게 분석하고, 더 효율적인 알고리즘까지 제안해줍니다.

⚡️ 3줄 요약 (TL;DR)

시간 복잡도 및 공간 복잡도 정확히 계산 (Big-O)
성능 병목 구간(Bottleneck) 식별
더 낮은 복잡도를 가진 개선된 알고리즘 제안

🚀 해결책: “복잡도 분석기”

아래 PROMPT 내용을 복사해서 사용하세요.

역할 (Role): 너는 컴퓨터 과학(CS) 교수님이자 알고리즘 최적화 전문가야.

상황 (Context): 내가 작성한 알고리즘의 성능이 궁금해. 효율적인지, 아니면 개선이 필요한지 알고 싶어.

요청 (Task):

제공된 코드의 **시간 복잡도(Time Complexity)**와 **공간 복잡도(Space Complexity)**를 Big-O 표기법으로 분석해줘.

왜 그런 복잡도가 나오는지 코드 라인별로 근거를 설명해줘.

만약 더 효율적인 방법(예: O(N^2) -> O(N log N))이 있다면, 개선된 코드와 함께 설명해줘.

코드:
[여기에 분석할 코드를 붙여넣으세요]
제약사항 (Constraints):

최악의 경우(Worst Case)를 기준으로 분석해줘.

입력 데이터의 크기(N)가 매우 클 때 발생할 수 있는 문제점을 언급해줘.

🧬 프롬프트 해부 (Why it works?)

이 프롬프트가 강력한 이유는 3가지 논리적 장치 때문입니다.

근거 요구: 단순히 “O(N)입니다”라고 답만 주는 게 아니라, “이 반복문 때문에 N이고, 저기서 정렬을 해서 log N입니다”라고 이유를 설명하게 하여 학습을 돕습니다.
최악의 경우 가정: 알고리즘 성능은 평균보다 최악(Worst Case)일 때가 중요하므로 이를 기준으로 잡도록 명시했습니다.
개선안 제시: 분석에서 그치지 않고, 더 나은 알고리즘(예: 이중 루프를 해시맵으로 변경)을 제안받아 실질적인 코드 품질을 높입니다.

📊 증명: Before & After

❌ Before (입력 코드)

def find_duplicate(nums):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] == nums[j]:
                return nums[i]
    return None

✅ After (결과)

분석:

시간 복잡도: O(N^2). 이중 for 루프를 사용하고 있습니다. N이 10,000만 넘어도 매우 느려집니다.
공간 복잡도: O(1). 추가적인 메모리를 거의 사용하지 않습니다.

개선된 코드 (Hash Set 사용):

def find_duplicate_optimized(nums):
    seen = set()
    for num in nums:
        if num in seen:
            return num
        seen.add(num)
    return None

개선 결과:

시간 복잡도: O(N). 루프를 한 번만 돕니다.
공간 복잡도: O(N). seen 집합에 데이터를 저장해야 합니다. (Time-Space Tradeoff)

🚨 트러블 슈팅 (안 될 땐 이렇게!)

Q. 재귀 함수 분석을 잘 못해요. A. “재귀 호출의 깊이(Depth)와 각 호출당 연산량을 고려해서 점화식을 세워보고 분석해줘” 라고 구체적으로 요청하세요.

Q. 특정 라이브러리 함수(Sort 등)의 복잡도를 무시해요. A. “내장 함수(sort, map 등)의 내부 복잡도까지 포함해서 계산해줘” 라고 명시하세요.

🎯 결론

“돌아가니까 됐어”라는 생각은 이제 그만. 보이지 않는 성능까지 챙기는 개발자가 진짜 고수입니다. AI 교수님의 피드백으로 알고리즘 근육을 키워보세요! 🍷