[자료구조] 4.알고리즘의 복잡도(Complexity of Algorithms)

알고리즘의 복잡도

• 알고리즘의 복잡도(Complexity)는 문제 풀이 방식 혹은 코드가 얼마나 복잡한지 혹은 단순한지를 의미하는 용어가 아니다. 해당 용어는 문제의 크기(일반적으로 데이터 원소의 개수)가 커짐에 따라서 얼마나 큰 시간을 혹은 리소스를 요구하는지를 의미한다.

• 알고리즘의 복잡도는 소요되는 성질에 따라 다음의 두가지로 나누어진다.

  • 시간 복잡도(Time Complexity)
  • 공간 복잡도

---

시간 복잡도

• 시간 복잡도는 문제의 크기가 커짐에 따라서, 문제를 해결하는 데 소요되는 “시간”이 “어떤 양상”으로 증가하는가를 다룬다.

• 시간 복잡도는 다음의 두 분류로 나누어진다.

  1. 평균 시간 복잡도 (Average Time Complexity)

     : 임의의 패턴들이 인풋되었다고 가정했을 때, 소요되는 처리 시간의 평균

  2. 최악 시간 복잡도 (Worst-case Time Complexity)

     : 임의의 인력 패턴 중, 가장 긴 시간을 소요하게 만드는 입력에 대한 처리 시간

---

빅오 표기법(Big-O Notation)

• 알고리즘의 복잡도를 표현하는 데 있어서 점근 표기법(Asymptotic Notation)을 흔히 사용한다.
• 그리고, 점근 표기법 중에는 Big-O Noation표기법이 존재한다.

  • Big-O Noation은 함수 증가 양상을 대략적으로 표현하고있기에,
    알고리즘의 시간 복잡도와 공간 복잡도를 나타내는데 주로 사용된다.

  • \(O(\log n), O(n), O(n^2), O(2^n)\)등으로 표기한다.

(1) 빅오 표기법 성능

위의 자료는 빅오 표기의 시간 복잡도에 대한 성능을 비교한 차트이다.
해당 차트에 제시된 성능을 비교하면 다음과 같이 요약할 수 있다.
(좌에서 우로 갈수록 알고리즘의 효율성이 낮아진다)

\[O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(2^n) < O(n!)\]

(2) 빅오 표기법 예시

• 선형 시간 알고리즘: \(O(n)\)
  • 의미: 입력의 크기에 비례하는 시간 소요
  • 예시: 선형 배열에서 최댓값을 찾는 경우
  • Average-Case: \(O(n)\)
  • Worst-Case: \(O(n)\)
• 로그 시간 알고리즘: \(O(\log n)\)
  • 의미: 입력의 크기의 로그에 비례하는 시간 소요
  • 예시: 이진 탐색
• 이차 시간 알고리즘: \(O(n^2)\)
  • 의미: 입력의 크기의 제곱에 비례하는 시간 소요
  • 예시: 삽입 정렬
  • Best-Case: \(O(n)\), 선형 배열이 이미 정렬되어있을 때는 순서대로 살펴보면됨
  • Worst-Case: \(O(n^2)\), 선형 배열이 목표 순서의 역순으로 정렬되어 있을 경우
• 로그선형 시간 알고리즘: \(O(n\log n)\)
  • 의미: 입력의 크기의 로그선형에 비례하는 시간 소요
  • 특징: 입력 패턴에 따라 정렬 속도에 차이가 있지만, 정렬 문제에 대해서는 \(O(n\log n)\)보다 낮은 복잡도를 갖는 알고리즘은 존재할 수 없음이 증명됨
  • 예시: 병합 정렬
    • 병합정렬은 다음과 같이 Divide & Conquer방식을 채택하는 로직이다.

---

References

• Programmers, 어서와! 자료구조와 알고리즘은 처음이지?
• Big-O Cheat Sheet