[Algorithm] 3. 알고리즘의 효율 분석

On this page

• 3. 알고리즘의 효율 분석
  • 03-1 시간 복잡도란?
  • 03-2 시간 복잡도 계산해보기

3. 알고리즘의 효율 분석

코딩 테스트 합격자 되기 - 파이썬 편 책 정리 내용입니다.

---

03-1 시간 복잡도란?

- 시간 복잡도(time complexity)

• 알고리즘의 성능을 나타내는 지표

• 입력 크기에 대한 연산 횟수의 상한

• 알고리즘이 실행되는 제한 시간과 관련

• 낮으면 낮을수록 좋다.

- 알고리즘 수행 시간을 측정하는 방법

1. 절대 시간을 측정하는 방법

   • 말 그대로 실행 후 결과가 나올 때 까지의 시간을 측정하면 된다.

   • 프로그램을 실행하는 환경에 따라 달라질 수 있어서 코딩 테스트에서는 잘 활용하지 않는다.

2. 시간 복잡도를 측정하는 방법

   • ’연산 횟수’와 관련

   • 최선(best), 보통(normal), 최악(worst)의 경우로 나뉜다.

   • 점근적 표기법: 입력 크기에 따른 연산 횟수의 추이를 활용해서 시간 복잡도를 표현하는 방법 = 어떤 함수의 증가하는 추세를 표현하는 표기법

- 빅오 표기법(big-O notation)

• 최악의 경우에 대하여 시간 복잡도를 표현하는 방법

• 연산 횟수가 \(f(x)\) 라고 할 때 함수의 최고차항을 남기고 계수를 지워 \(O(...)\) 와 같이 표기하면 된다.

  ex) \(f(x)=2x^2+3x+5\) 라면 시간 복잡도는 \(O(x^2)\)

• 다음을 만족하는 \(C\) 가 있으면 \(f(x)\) 의 최악의 시간 복잡도는 \(O(g(x))\) 라고 쓴다.

  • 특정 x 시점 이후부터 항상 \(f(x)\ge C\times g(x)\) 를 만족

  • \(C\) 는 상수

• \(x \rightarrow \infty\) 를 상상!

- 시간 복잡도를 코딩 테스트에 활용하는 방법

• 연산 횟수는 1,000~3,000만 정도로 고려해서 시간 복잡도를 생각

  시간 복잡도	최대 연산 횟수
  \(O(N!)\)	10
  \(O(2^n)\)	20~25
  \(O(N^3)\)	200~300
  \(O(N^2)\)	3,000~5,000
  \(O(N\text{log}N)\)	100만
  \(O(N)\)	1,000~2,000만
  \(O(\text{log}N)\)	10억

  ex) 1차원 배열 문제에서 \(O(N)\) 이 허용하는 연산 횟수는 1,000만 이므로 데이터의 개수가 1,000만개 이하면 이 알고리즘은 사용해도 된다.

03-2 시간 복잡도 계산해보기

- 별 찍기 문제

• N을 입력 받으면 N번째 줄까지 별을 1개부터 N개 까지 늘려가며 출력하는 문제

  *

  **

  ***

  …

  **********

• 연산 횟수 : \(f(N) = 1+ 2+...+N = \frac{N(N+1)}{2}\)

- 박테리아 수명 문제

• 초기 박테리아 세포 개수가 N일 때 해마다 세포 개수가 이전 세포 개수의 반으로 준다면 언제 모든 박테리아가 죽을까?

  예를 들어, N이 16인 경우 16→8→4→2→1→0(소멸) 5번 과정을 거치므로 답은 5이다.

  현재 박테리아의 수가 N이라면 1년 뒤의 박테리아 수는 \(\frac{1}{2}\times N\) 이다.

  Y년 후의 박테리아 수는 \((\frac{1}{2})^Y\times N\) 이다.

  그러면 박테리아의 소멸 시기는 \((\frac{1}{2})^Y\times N\) 의 값이 최초로 1보다 작아질 때 이므로

  \((\frac{1}{2})^Y\times N \le 1\)

  \(\Rightarrow N \le 2^Y\) 로그를 취하면

  \(\Rightarrow \text{log}_2N \le Y\)

• 즉, \(Y \ge \text{log}_2N\) 이므로 \(O(\text{log} N)\) 의 시간 복잡도를 가진다.

• 앞으로 특정 값을 계속 반으로 줄이는 동작을 한다면 시간 복잡도를 \(O(\text{log} N)\) 이라 생각하면 된다.

---

Q & A

1. 시간복잡도가 무엇인지 정의하고, 왜 알고리즘의 성능을 평가할 때 중요한지 설명하세요.
   • 알고리즘의 성능을 나타내는 지표이며 입력 크기에 대한 연산 횟수의 상한이다. 알고리즘이 실행되는 제한 시간과 관련되어있기에, 문제를 풀기 전 미리 계산하는 과정이 필요하다.
2. 빅오 표기법이 무엇인지 설명하고, 알고리즘의 시간복잡도를 표현할 때 빅오 표기법이 사용되는 이유를 설명하세요.
   • 최악의 경우에 대하여 시간 복잡도를 표현하는 방법이며 연산 횟수를 계산한 뒤 함수의 최고차항을 남기고 계수를 지워 표현하는 방법이다. 빅오 표기법이 사용되는 이유는 x가 커지면서, 값이 역전되는 상황이 발생할 수 있다. 빅오표기법은 x가 무한히 커지는 상황을 상정하여 이러한 상황을 방지한다.
3. 빅오 표기법에서 최악의 경우(worst-case)를 고려하는 이유는 무엇인가요? 실제 상황에서 최악의 경우 시간복잡도가 중요한 이유를 설명하세요.
   • 모든 경우의 수에서 알고리즘이 문제를 처리하는 것을 고려해야 하기 때문이다. 어떤 상황에서는 프로그램이 동작하고, 어떤 상황에서는 동작하지 않는 상황이 발생하면 안되기 때문에 최악의 경우를 고려한다.
4. 빅오 표기법을 사용하여 알고리즘의 효율성을 평가할 때 나타날 수 있는 한계점이나 오해는 무엇인지 설명하세요.
   • 최악의 경우만을 고려하여 최선과 보통의 상황은 고려되지 않는다는 점, 계수를 지우기 때문에 예를들어 2n^2과 1000n^2의 알고리즘이 동일하게 평가된다는 점이 있을 것 같다.