파이썬으로 시간복잡도를 알아보자

 

 

 

 

 

정보처리기사를 준비하면서 시간복잡도를 계산하는 방법에 대해 다시 정리하게 되었습니다.

시간복잡도를 계산하는 법은 코드의 실행 시간이 입력 크기 nn에 따라 어떻게 변하는지 파악하는 과정입니다.

간단한 문제로 계산하는 방법을 단계별로 설명하겠습니다.

---

목차

• 1. 시간 복잡도 계산의 기본 원칙
• 2. 예제 문제
• 3. 계산 요약

---

1. 시간 복잡도 계산의 기본 원칙

1. 기본 연산: 덧셈, 곱셈, 비교, 할당 등 한 번의 실행에 O(1)O(1)이 걸린다고 간주합니다.
2. 반복문: 반복 횟수에 따라 시간 복잡도가 결정됩니다.
   • 단일 루프: O(n)O(n)
   • 중첩 루프: 반복 횟수의 곱으로 계산 (O(n2),O(n3)O(n^2), O(n^3) 등).
3. 조건문: 조건의 실행 시간이 큰 영향을 미치지 않는다면 가장 긴 조건을 포함한 부분을 기준으로 계산합니다.
4. 함수 호출: 호출되는 함수의 시간 복잡도를 포함해야 합니다.
5. 상수 제거: 상수는 시간 복잡도에서 제외됩니다. 예를 들어, O(2n)O(2n)은 O(n)O(n)으로 단순화됩니다.
6. 최고차항 유지: 가장 빠르게 증가하는 항만 남깁니다. 예: O(n2+n)O(n^2 + n) → O(n2)O(n^2).

 

 

 

 

 

2. 예제 문제

문제 1: 단일 루프

for i in range(n):
    print(i)

• 분석:
  • 반복문은 nn번 실행됩니다.
  • 각 반복에서 print(i)print(i)가 한 번 실행되므로 한 번에 O(1)O(1) 시간이 걸립니다.
• 시간 복잡도: O(n)O(n).

문제 2: 중첩 루프

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

• 분석:
  • 외부 루프는 nn번 반복.
  • 내부 루프도 nn번 반복.
  • 따라서 n×n=n2n \times n = n^2번 실행됩니다.
• 시간 복잡도: O(n2)O(n^2).

문제 3: 로그 반복

i = 1
while i < n:
    print(i)
    i *= 2

• 분석:
  • ii는 1,2,4,8,…,n1, 2, 4, 8, \ldots, n처럼 2배씩 증가합니다.
  • 반복 횟수는 i=2ki = 2^k가 nn보다 작을 때까지. 즉, k≤log⁡2(n)k \leq \log_2(n).
• 시간 복잡도: O(log⁡n)O(\log n).

 

문제 4: 조건문

if n % 2 == 0:
    for i in range(n):
        print(i)
else:
    print("Odd number")

• 분석:
  • 조건문 자체는 O(1)O(1).
  • nn이 짝수인 경우 O(n)O(n), 홀수인 경우 O(1)O(1).
  • 최악의 경우(짝수 조건 기준)를 기준으로 계산.
• 시간 복잡도: O(n)O(n).

문제 5: 재귀 함수

def recursive(n):
    if n == 0:
        return
    print(n)
    recursive(n - 1)

• 분석:
  • 함수는 nn번 호출됩니다.
  • 각 호출에서 O(1)O(1) 작업 수행.
• 시간 복잡도: O(n)O(n).

문제 6: 이진 분할 재귀

def binary_recursion(n):
    if n == 1:
        return
    binary_recursion(n // 2)
    binary_recursion(n // 2)

• 분석:
  • 두 번의 재귀 호출 T(n)=2T(n/2)T(n) = 2T(n/2).
  • 이를 풀면 T(n)=O(n)T(n) = O(n) (재귀 트리의 깊이는 log⁡n\log n, 노드 개수는 O(n)O(n)).
• 시간 복잡도: O(n)O(n).

 

3. 계산 요약

1. 단일 루프: 반복 횟수에 비례 → O(n)O(n).
2. 중첩 루프: 루프의 반복 횟수 곱 → O(n2)O(n^2), O(n3)O(n^3).
3. 로그 반복: 값이 지수적으로 증가/감소 → O(log⁡n)O(\log n).
4. 재귀 함수: 재귀 호출의 깊이와 호출 횟수로 계산.
5. 최악의 경우 고려: 항상 최악의 입력에 대해 계산.

코드를 직접 분석하고 반복 구조와 조건을 이해하면 시간 복잡도를 쉽게 계산할 수 있습니다.