빅오(Big-O) 표기법과 시간복잡도
1. 빅오 표기법이란? 알고리즘이 해당 차수이거나 그보다 낮은 차수의 시간복잡도 및 공간복잡도를 가진다는 의미이다. 프로그램이 돌아가는 동안, 정확한 단계(step) 의 수를 결정하는 작업은 매우 어렵고 복잡하기 때문이다. 예를 들면 3n+5는 3n과 근사한 것으로 판단한다는 뜻이다. 빅오 표기법은 f(n)∈O(g(n))과 같이 표기된다. O(n), O(n^2) 등과 같이 표기 되며 O(n+10)=O(n)으로 간주한다고 생각하면된다. 위 그래프와 같이 빅오 표기법은 성능(수행시간 및 횟수)은 다음과 같다. O(1) < O(log n) < O(n) < O(n * log n) < O(n²) < O(n³) < O(2^n) < O(n!) O(n^2)이상의 성능을 가지는 알고리즘은 가용가치가 없다고 판단하면 된다..
알고리즘
2021. 5. 3. 15:09
