Python_#2

hyena_lee·2025년 10월 4일

시간복잡도 챌린지

자료구조

목록 보기

5/15

🧩 시간 복잡도란?

입력값에 비해 얼마나 일을 수행해야 하는가? 가 시간 복잡도임.
입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계가 있음.

⏱️ 2. 왜 중요할까?

같은 코드라도 실행 속도가 완전히 달라짐.
시간복잡도를 알면 효율적인 알고리즘을 고를 수 있음.

📊 시간복잡도의 대표 표기법 (Big-O 표기법)

표기	이름	예시	설명
O(1)	상수 시간	딱 한 번만 실행	입력 크기와 관계없이 빠름
O(log N)	로그 시간	이진탐색	입력이 커져도 느려지지 않음
O(N)	선형 시간	단순 반복문	데이터가 늘면 실행시간도 비례
O(N log N)	로그선형	병합정렬, 퀵정렬	중간 정도 효율
O(N²)	제곱 시간	이중 for문	데이터가 많아지면 급격히 느려짐

🧮 4. 예제 코드로 비교해보기

🔹 예제 1) O(1) — 상수 시간

def print_first_element(arr):
    print(arr[0])

➡ 리스트 길이가 10이든 10,000이든, 항상 한 번만 실행됨.

🔹 예제 2) O(N) — 선형 시간

def print_all_elements(arr):
    for x in arr:
        print(x)

➡ 배열의 길이가 100이면 100번, 1000이면 1000번 반복함.
👉 실행 시간이 입력 크기 N에 비례함.

🔹 예제 3) O(N²) — 제곱 시간

def print_pairs(arr):
    for i in arr:
        for j in arr:
            print(i, j)

➡ for문이 2개 겹침
만약 배열 길이가 100이라면 → 100 × 100 = 10,000번 실행
👉 데이터가 조금만 많아져도 폭발적으로 느려짐.

🔹 예제 4) 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

➡ 탐색할 때마다 데이터 절반씩 줄이기 때문에
1000개의 데이터도 약 10번 정도만 비교해요.
(2¹⁰ = 1024 → 로그 성질)

📘 5. 시간복잡도 비교 예시

입력 개수 (N)	O(1)	O(log N)	O(N)	O(N²)
10	1	3	10	100
100	1	7	100	10,000
1,000	1	10	1,000	1,000,000

➡ N이 커질수록 O(N²)은 엄청나게 느려진다는 것,
이 표로 한눈에 볼 수 있음 👀

🔹 예

내가 반에 있는 사람들 중에서 가장 이성에게 호감이 높은 사람을 뽑는다고 하자.
반에 있는 사람들이 N명이라면 하면,
A방식은 N번 만큼의 연산이 필요하고
B방식은 N^2만큼의 연산이 필요하다고 한다.
N이 예를 들어 30이라면 A방식은 30번, B방식은 900번의 연산이 필요함.

🧩 최댓값 찾기 알고리즘의 시간 복잡도

def find_max_num(array):
    for number in array:
        is_max_num = True
        for compare_number in array:
            if number < compare_number:
                is_max_num = False
        if is_max_num:
            return number

print("정답 = 6 / 현재 풀이 값 = ", find_max_num([3, 5, 6, 1, 2, 4]))
print("정답 = 6 / 현재 풀이 값 = ", find_max_num([6, 6, 6]))
print("정답 = 1888 / 현재 풀이 값 = ", find_max_num([6, 9, 2, 7, 1888]))

이 해결 방법은 각 숫자마다 모든 다른 숫자와 비교해서 최대값인지 확인한다. 만약 다른 모든 값보다 크다면 반복문을 중단한다.
이 함수가 시간이 얼마나 걸리는지 어떻게 분석할 수 있을까?
바로, 각 줄이 실행되는 걸 1번의 연산이 된다고 생각하고 계산하시면 됨.
아래와 같이 계산할 수 있다.

    for number in array:                 # array 의 길이만큼 아래 연산이 실행
        is_max_num = True                # 대입 연산 1번 실행
        for compare_number in array:     # array 의 길이만큼 아래 연산이 실행
            if number < compare_number:  # 비교 연산 1번 실행
                is_max_num = False       # 대입 연산 1번 실행
        if is_max_num:                   # 비교 연산 1번 실행
            return number

위에서 연산된 것들을 더해보면,
1. array의 길이 X array의 길이 X (비교 연산 1번 + 대입 연산 1번)
  
  만큼의 시간이 필요함. 여기서 array(입력값)의 길이는 보통 N이라고 표현함.
  그러면 위의 시간을 다음과 같이 표현할 수 있다.
  $N \times N \times 2$
2. array의 길이 X 비교 연산 1번
  
  만큼의 시간이 필요함.
  $N$
  그러면 우리는 이제 이 함수는 $2* N^2 + N$ 만큼의 시간이 걸렸겠구나! 라고 말할 수 있다.

🧠 주의해야 할 점

for문이 몇 겹인지 확인.
➡ 한 겹이면 O(N), 두 겹이면 O(N²)
리스트 길이가 바뀔 때 실행 횟수가 얼마나 변하는지 확인!
“시간복잡도 = 실행시간”은 아님!!
➡ 실제 시간은 컴퓨터 성능, 언어, 환경에 따라 다르지만
복잡도는 성장 속도(비율) 만 봄

🌱 정리

구분	설명	예시
O(1)	입력 크기와 상관없이 일정	딕셔너리 접근
O(N)	입력 크기만큼 반복	for문 한 번
O(N²)	이중 반복문	버블정렬
O(log N)	절반씩 줄이기	이진탐색
O(N log N)	효율적인 정렬	병합정렬, 퀵정렬