알고리즘의 복잡도

• 시간 복잡도 (Time Complexity): 문제의 크기와 이를 해결하는 데 걸리는 시간 사이의 관계
• 공간 복잡도 (Space Complexity): 문제의 크기와 이를 해결하는 데 필요한 메모리 공간 사이의 관계

1 시간 복잡도

• 평균 시간 복잡도 (Average Time Complexity): 임의의 입력 패턴을 가정했을 때 소요되는 시간의 평균
• 최악 시간 복잡도(Worst-case Time Complexity): 가장 긴 시간을 소요하게 만드는 입력에 따라 소요되는 시간

2 Big-O Notation

• 점근 표기법(asymptotic notatoon)의 일종
• 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현한다
• 알고리즘의 복잡도를 표현할 때 흔히 사용된다

• e.g., 입력의 크기가 n일 때 $O(logn), O(n), O(2^n), O(n^2)$
• 계수는 그다지 중요하지 않다. 시간복잡도를 볼 때 입력의 크기가 기하급수적으로 크는 것을 가정하기 때문에 계수는 큰 의미가 없다

2.1 선형 시간 알고리즘 - $O(n)$

• 입력의 크기에 비례하는 시간 소요
• 예시: n개의 무작위로 나열된 수에서 최댓값을 찾기 위해 선형 텀색 알고리즘을 적용하는 경우
  • 최댓값은 끝까지 다 살펴보기 전까지는 알 수 없다
  • Average case: O(n)
  • Worst case: O(n)

2.2 로그 시간 알고리즘 - $O(logn)$

• 입력의 크기의 로그에 비례하는 시간 소요
• 예시: n개의 크기 순을 정렬된 수에서 특정 값을 찾기 위해 이진 탐색 알고리즘을 적용하는 경우
  • 효율이 좋은 알고리즘

2.3 이차 시간 알고리즘 - $O(n^2)$

• 예시: 삽입 정렬(insertion sort)
  • 삽입정렬은 정렬되지 않은 자료를 정렬된 부분 중 알맞은 위치에 삽입하며 정렬하는 알고리즘
  • 삽입정렬은 하나의 원소를 집어넣을 때 n만큼 비교해야 하고, 그 동작을 원소의 개수만큼 반복해야 하므로 O(n^2)
  • Best case: O(n) ← 정렬된 경우
  • Worst case: O(n^2)

2.4 보다 나은 (낮은) 복잡도를 가지는 정렬 알고리즘

• 예: 병합 정렬(merge sort) - O(nlogn)
  • 정렬할 데이터를 반씩 나누어 각각 정렬시킨다 (divide & conquer)
  • 각 원소를 보고 줄세우면 되므로 O(n) 만큼, 이걸 합치는 데에 O(logn)
    → O(nlogn)

2.5 꽤나 복잡한 문제

• 유명한 예: 배낭 문제(Knapsack problem)
  • 특정 용량이 정해진 배낭에 다양한 무게의 물건을 담으려고 할 때, 어떻게 담아야 최대 가치를 가질 수 있을까?
  • 모든 경우의 수를 직접 해보고 그 중에서 가장 가치가 좋은 것을 고르면 된다
    → O(2^n)
  • dynamic programming으로 효율적으로 풀 수 있다