[이산수학4-3]Analysis of Algorithms(알고리즘 분석)

시간 복잡도(Time complexity) - 세상에는 다양한 알고리즘이 있지만, 그중에는 무의미한 알고리즘도 있습니다. Program으로 작성해 돌리기에는 time이 너무 오래 걸리거나 사용하는 컴퓨터 자원이 하드웨어 스펙을 뛰어 넘는 경우가 있습니다.

이러한 경우를 예측하고 피하기 위해서 알고리즘 분석은 매우 중요합니다. 시간 복잡도와 input의 크기에 따라 현실에서 걸리는 시간. - 위 표에서 가장 큰 것을 살펴보면 한평생 output을 내지 못하는 알고리즘도 있는 것을 확인할 수 있습니다. - 위 표에서 주목해야 할 점은 Θ(n)인 알고리즘이 n=10^6일 때 1sec가 걸린다는 것입니다. ▷ Best-case time - 모든 크기 n의 inputs에서 알고리즘이 종료되는 최소 시간. ▷ Worst-case time - 모든 크기 n의 inputs에서 알고리즘이 종료되는 최대 시간. ▷ Average-case time - 모든 크기 n의 inputs에서 알고리즘이 종료되...