Big-O Notation (점근 표기법)

1. Big-O Notation(점근 표기법)이란?

• 알고리즘의 시간 복잡도를 나타내는 방법에는 여러 가지가 있다. 그들 중 현재 가장 널리 쓰이는 표기법이다.
• 점근 표기법은 큰 수의 법칙을 적용하여 트랙잭션의 최악의 경우를 택하여 시간 복잡도를 표현한다.
  'f = 5n+8', 'g = 2n' 이라면, n이 ∞로 갈 때, 이 둘은 수렴하므로 O(n)로 같은 취급을 하는 것이다.
• 가장 보편화된 방법이지만 이론적인 느낌이 강하기 때문에, 본인의 데이터에 따라 시간 복잡도를 따져볼 필요가 있다.

 

 

2. 자료구조별 트랜잭션 시간 복잡도

 

 

3. 정렬 알고리즘 시간 복잡도