03. 알고리즘의 효율 분석

🧩 <코딩테스트 합격자 되기: 파이썬 편> 1독 스터디 기록입니다.

 

 

문제를 분석하여 시간 복잡도를 구한 다음 문제에 적합한 알고리즘을 찾을 수 있다.

 

시간 복잡도(time complexity)

알고리즘 수행 시간을 측정하는 방법에는 절대 시간을 측정하는 방법과 시간 복잡도를 측정하는 방법 두 가지가 있다. 절대 시간을 측정하는 방법은 프로그램 실행 환경에 따라 편차가 크기 때문에 코딩 테스트에서는 잘 활용하지 않는다.

 

시간 복잡도는 어떻게 측정하는가?

입력 크기에 대해 알고리즘이 시작한 순간부터 결괏값이 나올 때까지의 연산 횟수를 측정하면 된다.

 

그리고 이 측정 결과를 최선, 보통, 최악의 경우로 나눌 수 있다. 결괏값이 가장 빠르게 나오는 경우가 최선의 경우, 가장 늦게 나오는 경우가 최악의 경우이다. 즉 시간복잡도가 낮을 수록 알고리즘의 성능이 높다.

 

 

---

 

점근적 표기법

시간 복잡도는 입력 크기에 대한 연산 횟수라고 했다. 이 때 입력 크기가 현실의 특정 케이스에 의존하는 것은 의미가 없다. 시간 복잡도를 입력 크기에 따른 연산 횟수의 추이로 표현하는 방법을 '점근적 표기법'이라고 한다.

 

빅오 표기법(big-O notation)

점근적 표기법 중에서도 상한선을 활용하는 방법이다. 즉 최악의 경우에 대하여 시간 복잡도를 표현한다.

입력 크기가 $ x $, 연산 횟수가 $ f(x) $라면 $ f(x) $의 차수는 지우고 최고차항만 남겨 $ O(...) $로 표기하면 된다.

• $ 3x^{2}+5x+6 $ → $ O(x^{2}) $
• $ x+\textrm{log}x $  → $ O(x) $
• $ 2^{x}+10x^{5}+5x^{2} $  → $ O(2^{x}) $
• $ 5x^{2}-6x $  → $ O(x^{2}) $

 

🤔 이렇게 표기하는 이유는 무엇일까?

일단 아래와 같은 조건을 만족할 때 $ f(x) $ 의 최악의 시간 복잡도는  $ O(g(x)) $이다.

특정 시점 x 이후부터 항상 $ f(x)\leqslant C*g(x) $를 만족하는 상수 $ C $가 존재한다.

 

$ x $가 무한하게 커질 때 차수들에 의한 차이는 무시할 수 있을 정도로 작기 때문에 최고차항만 남긴다. '지수함수 > 다항함수 > 로그함수' 순으로 빠르게 증가하기 때문에 느리게 증가하는 함수를 지워야 한다.

 

 

---

 

추가 문제

각 수식을 $f(x)$라고 할 때 특정 시점 x 이후부터 항상 $ f(x)\leqslant C*g(x) $를 만족하는 $C\times g(x)$를 찾기

 

[01] $ 3x^{2}+5x+6 $

$ 30\times x^{2} $ 가 특정 지점부터 $ 3x^{2}+5x+6 $보다 항상 크다.

 

[02] $ x+\textrm{log}x $

$ 2x $가 특정 지점부터 $ x+\textrm{log}x $보다 항상 크다.

 

 

---

📕 Reference

• 코딩 테스트 합격자 되기: 파이썬 편, 박경록, 골든래빗.