알고리즘의 효율성을 평가하는 방법
평가 방법은 시간 복잡도/공간 복잡도 두 가지로 볼 수 있습니다.
공간 복잡도
메모리(자원) 공간을 효율적으로 사용하는지 혹은 프로그램을 실행 시킨 후 완료하는데 필요로 하는 자원 공간의 양에 대한 개념입니다.
시간 복잡도
프로그램의 입력값과 연산 수행 시간의 상관관계를 나타내는 척도로 알고리즘의 절대적인 실행 시간을 나타내는 것이 아닌 알고리즘을 수행하는데 몇 번의 연산이 이루어졌는지를 확인합니다.
하드웨어의 발전으로 시간 복잡도 보다는 중요도가 떨이지고 또한 시간과 공간은 반비례적인 경향이 있기에 알고리즘의 효율성을 평가하는 척도는 시간 복잡도를 더 우선순으로 합니만 공간 복잡도가 중요하지 않다는 의미는 아닙니다.
복잡도를 나타내는 표기법 점근 표기법
알고리즘은 실행환경에 따라 다르게 측정될 수 있습니다.
하드웨어, OS, 사용 언어 등 모든게 동일한 환경을 맞출 수 없기 때문에
기본 연산(산술 연산, 제어 연산 등)의 실행 횟수로 성능을 분석합니다.
알고리즘(코드)이 복잡할 수록 효율성을 평가하는 것이 어렵기 때문에 이를 단순화 하여 점근 표기법을 사용합니다.
| CASE 1 | CASE 2 |
|---|---|
| n² + 2n + 3 | 5000n + 10000 |
위 두 케이스 중 어떤 알고리즘이 효율적인지 한번에 확인할 수 없습니다.
그렇기 때문에 최고차항만을 비교하여 판단할 수 있습니다.
값이 커지면 커질 수록 다른 항들의 값이 의미가 없어집니다.
| CASE 1 | CASE 2 |
|---|---|
| n² + 2n + 3 | 5000n + 10000 |
| n² | 5000n |
| n² | n |
| O(n²) | O(n) |
빅오 표기법 / big-O notation
점근 표기법의 유형 중 중요하게 봐야할 유형은 빅오(Big-O)입니다.
그외 유형 : 리틀오(Little-o), 오메가(Omega), 세타(Theta)
빅오 표기법 - 최악의 성능이 나올 때의 연산량이 어느정도 걸릴것인지
동일한 알고리즘이라 하더라도 어떤 입력이 들어왔냐에 따라 효율성이 달라질 수 있습니다. 따라서 모든 경우의 수 중 최악의 경우에서 얼마만큼의 효율성이 나오는지 확인해야하는데, 그때 사용하는 방법이 빅오 표기법입니다.
