[자료구조] Big-Oh Notation

T(N) = n^2 + 2n + 1이라고 하면 최대 차수인 2차항의 값을 제외하고 나머지 값들은 극한으로 보냈을 때 무의미해지게 된다. 따라서 시간복잡도 상에서는 T(N) = n^2로 볼 수 있다. Big-Oh Notation 상에서는 O(n^2) 로 표현한다. 

 

Big-Oh Notation은 두개의 함수 f(n)과 g(n)이 주어졌을 때 모든 n>=n0에 대하여 f(n)<= cg(n)을 만족하는 두개의 상수 c와 n0가 존재하면 f(n)의 Big-O는 O(g(n))이 된다는 것이다.

Big-Oh Notation은 T(n)이 다항식으로 표현이 된 경우 최고차항의 차수가 된다.

 

Big-Oh Notation

 

Big-Oh Notation 에서 시간 복잡도는 다음과 같이 그려진다. 

O(1) < O(logn )<O(n)< O(nlogn) < O(n^2)