[알고리즘] 알고리즘의 복잡도(Complexity of Algorithms)

알고리즘의 복잡도

복잡도

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

시간 복잡도

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

Big-O Notation

• 점근 표기법(asymptotic notation)의 하나
• 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현(알고리즘의 복잡도를 표현할 때 흔히 쓰임)
• $O(logn), O(n), O(n^2), O(2^n)$ 등으로 표기
• 알고리즘의 복잡도를 Big-O Notation으로 표현하면 입력의 크기가 커짐에 따라서 얼마나 실행 시간의 관계를 나타낼 수 있다. (이때, 계수는 그다지 중요하지 않음)

예시

• 입력의 크기가 n일 때,
  • $O(logn)$: 입력의 크기의 로그에 비례하는 시간 소요
  • $O(n)$: 입력의 크기에 비례하는 시간 소요

알고리즘의 복잡도

• 선형 시간 알고리즘 - $O(n)$
  ex. n개의 무작위로 나열된 수에서 최댓값을 찾기 위해 선형 탐색 알고리즘을 적용

  • 최댓값: 끝까지 다 살펴 보기 전까지는 알 수 없음
  • Average case: $O(n)$
  • Worst-case: $O(n)$

• 로그 시간 알고리즘 - $O(logn)$
  ex. n개의 크기 순으로 정렬된 수에서 특정 값을 찾기 위해 이진탐색 알고리즘을 적용

• 이차 시간 알고리즘 - $O(n^2)$
  ex. 삽입 정렬(insertion sort) - 삽입하는 방식으로 정렬

  • Best case: $O(n)$
  • Worst case(역순으로 정렬되어 있을 때): $O(n^2)$

• 삽입 정렬보다 나은(낮은) 복잡도를 가지는 정렬 알고리즘
  예: 병합 정렬(merge sort) - $O(nlogn)$

  • 정렬할 데이터를 반씩 나누어 각각을 정렬시킨다. ($O(nlogn)$
  • 정렬된 데이터를 두 묶음씩 한 곳에 합친다. ($O(n)$)
  • 두개를 반복해서 하나로 만든다. $O(nlogn)$
  • 참고: 입력 패턴에 따라 정렬 속도에 차이가 있지만 정렬 문제에 대해 $O(nlogn)$보다 낮은 복잡도를 갖는 알고리즘은 존재할 수 없음이 증명되어 있음

• 복잡한 문제
  ex. 배낭 문제 (Knapsack Problem)

  • 배낭에는 15kg까지만 담을 수 있다
  • 서로 다른 값과 무게를 가지는 아이템들이 존재 ($4:12kg, $2:2kg, $1:1kg, $10:4kg, $2:1kg)
  • 어떤 아이템을 담아야 최대의 가치를 얻을 수 있을지 구하는 문제
  • 복잡도가 앞에나온 문제들보다 큰 문제이다.