Algorithm & Time Complexity

📌 알고리즘이란

문제 해결을 위해 정해진 절차, 방법 or 과정을 나타내는 것. 계산 실행을 위한 단계적 절차

 

특성

• 정확성
• 수행성
• 유한성
• 효율성

알고리즘 분류

• 문제 해결 방식에 따른 분류
  • 분할 정복 알고리즘 (Divide-and-Conquer)
  • 그리디 알고리즘 (Greedy)
  • 동적 계획 알고리즘 (Dynamic Programming)
• 문제에 기반한 분류
  • 정렬 알고리즘
  • 그래프 알고리즘
  • 기하 알고리즘
• 특정 환경에 따른 분류
  • 병렬 알고리즘 (GPU)
  • 분산 알고리즘 (블록체인)
  • 양자 알고리즘

---

📌 알고리즘과 성능

• 시간 (빠르기)
• 공간 (메모리)

---

📌 시간 복잡도

• 코드에서 연산의 횟수를 기반으로 표현한 실행 시간
• 점근 표기법(Asymtotic notation)을 이용해 나타냄
• O (Big-O), Ω (Big-Omega), Θ (Big-Theta) 표기법이 있음
  • 일반적으로 O (Big-O) notation을 가장 많이 사용

Big-O notation

O(g(n)) = { f(n) : there exist positive constants c and n₀ such that 0 ≤ f(n) ≤ c·g(n) for all n ≥ n₀ }

f(n) is O(g(n)) if there exist constants c > 0 and n₀ ≥ 0 so that for all n ≥ n₀, we have f(n) ≤ c·g(n). In this case, we will say that f is asymptotically upper-bounded by g.

 

✅ f(n)은 n이 충분히 커지면, g(n)의 상수배보다 크지 않다는 것을 의미

✅ g(n)의 성장을 상한선으로 삼아, f(n)의 성장을 묶는 것이 핵심.

 

---

📌 시간 복잡도 표기법

O-표기의 정의

• 모든 n ≥ n₀에 대해서 f(n) ≤ cg(n)이 성립하는 양의 상수 c와 n₀가 존재하면, f(n) = O(g(n))이다.

O-표기의 의미

• n₀와 같거나 큰 모든 n (즉, n₀ 이후의 모든 n)에 대해서 f(n)이 cg(n)보다 크지 않다는 것

 

✅ g(n)을 f(n)의 상한(Upper Bound)이라고 함.

 

자주 사용하는 Big-O notation

• O(1) : 상수 시간 
• O(log n) : 로그 시간 
• O(n) : 선형 시간 (Linear time)
• O(nlogn) : 로그 선형 시간
• O(n²) : 이차 시간 
• O(n³) : 3차 시간 
• O(nᵏ) : 다항식 시간, k는 상수
• O(2ⁿ) : 지수 시간

---

📌 알고리즘 분석

정렬 문제 : n개의 숫자가 입력으로 주어졌을 때, 이를 기준에 맞게 정렬해 출력하는 문제

 

선택 정렬 알고리즘 (Selection Sort)

• idx 0 값부터 리스트를 순회하며 가장 작은 값을 찾아 위치를 조정하는 방식

for i in range(0, n-1):
    min_index = i
    for j in range(i+1, n):
        if arr[j] < arr[min_index]:
            min_index = j
    swap(arr[i], arr[min_index])

• 시간 복잡도 : O(n²)
  • 입력 데이터가 정렬되어있든, 아니든 항상
  • 비교 횟수는 n², 교환 횟수는 n임.
• 공간 복잡도 : O(1)
  • 추가 메모리 사용 없이, 제자리 정렬