[알고리즘] 빅오 표기법

빅오 표기법(Big-O Notation)

- 가장 빠르게 증가하는 항만을 고려.

- 3N^3 + 5N^2 + 1,000,000 -> O(N^3)

 

출처 - 나동빈 유튜브

- 일반적으로 cpu 기반의 개인 컴퓨터의 연산 횟수가 5억을 넘어가는 경우 :

python을 기준으로 통상 5 ~ 15초 가량의 시간이 소요됨.

 

- 시간제한이 1초인 문제를 만났을 때, 일반적인 기준

• N의 범위가 500인 경우 : 시간복잡도가 O(N^3)인 알고리즘
• N의 범위가 2,000인 경우 : 시간복잡도가 O(N^2)인 알고리즘
• N의 범위가 100,000인 경우 : 시간복잡도가 O(NlogN)인 알고리즘
• N의 범위가 10,000,000인 경우 : 시간복잡도가 O(N)인 알고리즘