Note 1. 시간 복잡도

안녕하시렵니까!
드디어 미루고 미루던 코테 준비를...해볼까 합니다...!!!
앞으로 차근차근 정리하는 개념들은 'Do it! 알고리즘 코딩 테스트 파이썬' 교재를 기반으로 작성할 예정입니다.
후! 시작이 반이다...

---

❓시간 복잡도 정의

알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말합니다. 시간 복잡도를 정의하는 유형에는 3가지가 있습니다.

1. 빅-오메가 : 최선일 때의 연산 횟수를 나타낸 표기법
2. 빅-세타 : 보통일 때의 연산 횟수를 나타낸 표기법
3. 빅-오(O(n)) : 최악일 때의 연산 횟수를 나타낸 표기법

 

코딩 테스트에서는 빅-오(O(n))를 기준으로 수행시간을 계산하는 것이 좋습니다. 그 이유는 코테는 다양한 테스트 케이스를 통과해야만 합격하기 때문에 시간 복잡도를 최악일 때를 염두해 작성해야 합니다. 

1️⃣ 빅-오(O(n)) 표기법별 대표 알고리즘

1. O(1): Stack push/pop, array indexing
2. O(log n): Binary Search, Balanced BST operations
3. O(n): Linear scan, simple for-loop
4. O(n log n): Merge Sort, Heap Sort, Quick Sort (average)
5. O(n²): Double loop, Bubble Sort, Selection Sort, Insertion Sort
6. O(2ⁿ): Recursive Fibonacci, Power set generation

2️⃣ 시간복잡도 효율 비교 (낮을수록 좋음)
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)

---

❓시간 복잡도를 바탕으로 코드 로직 개선하기

코드에서 시간 복잡도를 도출하려면 2가지 기준을 고려해야 합니다.

1. 상수는 시간 복잡도 계산에서 제외한다.
2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.

 

코드 예를 살펴보겠습니다.

# 예제 1) 연산 횟수 = N

N = 100
cnt = 0

for i in range(N):
    cnt += 1   # 한 번의 연산

print("총 연산 횟수:", cnt)

# 예제 2) 연산 횟수 = 3N

N = 100
cnt = 0

for _ in range(N):
    cnt += 1  # 1번째 반복

for _ in range(N):
    cnt += 1  # 2번째 반복

for _ in range(N):
    cnt += 1  # 3번째 반복

print("총 연산 횟수:", cnt)

 

두 예제의 연산 횟수를 비교해보면 3배의 차이가 납니다. 그러나 앞서 말씀드린 2가지 기준 중에서 첫 번째를 다시 생각해 보면 '상수는 시간 복잡도 계산에서 제외'합니다. 그래서 두 코드 모두 시간 복잡도는 O(n)으로 동일합니다.

# 예제 3) 연산 횟수 = n²

N = 100
cnt = 1

for i in range(N):
   for j in range(N):
      print("연산 횟수" + str(cnt))
      cnt += 1

 

예제 3은 시간 복잡도 도출 기준 두 번째를 보여주고 있습니다. 시간 복잡도는 가장 많이 중첩된 반복문을 기준으로 도출합니다. 따라서 위 예제에서는 이중 for 문이 전체 코드의 시간 복잡도 기준이 됩니다.

 

이렇게 내가 작성한 코드의 시간 복잡도를 도출할 수 있다면 코테에서 시간 초과가 발생했을 때 이 원리를 바탕으로 문제가 되는 코드 부분을 도출할 수 있습니다!!

 

빅-오 표기법별로 예제를 살펴본건 아니지만 대표적인 예제 먼저 살펴보았습니다. 나머지는 각 표기법별 알고리즘을 공부하며 차근차근 살펴보겠습니다.

---

‼️ 끝

앞으로(꾸준히!!!!) 중요한 파이썬 문법부터 알고리즘까지 공부하고 작성해 보겠습니다~