TIL_20210122

(추후 보충하겠습니다)

 

시간 복잡도

Complexity analysis_

복잡도 분석은 알고리즘이 어떤 문제를 푸는 데 있어서 시간과 공간을 얼마나 차지하는지 나타내는 지표입니다.

시간과 공간의 복잡도는 그 알고리즘이 얼마나 효율적인지를 나타내기 때문에 중요합니다.

만약 시간과 공간이 무한정이라면 무한정한 공간에 모든 경우의 수를 계산하고 무한정한 시간동안 그 계산을 진행하면 되기 때문에 아무리 복잡한 문제나 알고리즘이라도 쉽게 해결할 수 있을 것입니다.

하지만 경우의 수가 기하급수적으로 늘어난다면 (바둑의 경우의 수는 100의 100제곱입니다..) 말 그대로 무한정한 시간동안 알고리즘이 진행되어질 수가 있습니다. 때문에 시간과 공간의 복잡도를 개선하여 똑같은 문제라도 효율성을 끌어올려 해결해야 합니다.

때문에 알고리즘을 짤 때 중요한 사항은 1. 돌아가느냐? 2. 얼마나 효율적인 시간 / 공간 복잡도로 풀었느냐? 가 되겠습니다.

 

 

Big-O Notation으로 시간 복잡도를 표시합니다.

제일 최선의 경우는 O(1)의 시간이 걸립니다 (바로 해결)

 

인자를 N이라고 했을 때

시간 복잡도의 순서는 왼쪽에서부터 빠른 것 -> 느린 것 일때

O(1) -> O(log n) -> O(n) -> O(n log n) -> O(n^2) 순입니다.