Big O Notation 1 (대문자 O 표기법)

Big O notation (대문자 O 표기법)

Big - O 케이스

O(1): Constant 

- 데이터의 수(N)와 관계없이 항상 같은 시간에 계산을 끝내는 알고리즘.
ex) 연결 리스트의 맨 앞에 값 추가, Array의 Push(), Pop() 등..

 

O(log N): Logarthmic 

 

- N의 크기가 제곱이 되면 시간이 배가 된다. 문제를 해결하는데 필요한 단계의 수가 연산마다 점차 줄어드는 알고리즘.
ex) 이진 탐색, 재귀가 순기능으로 이뤄지는 경우

 

O(N): Linear 

- N의 크기가 증가하는만큼 비례하여 처리시간이 증가하는 알고리즘.
ex) 선형 탐색(연결 리스트에서의 탐색 등..), Stack, Queue 등에서의 access.

 

O(N log N): Linear-Logarithmic 

- N이 커질때 '로그'배 만큼 더 커지는 알고리즘.
ex) Merge sort, Heap sort..

 

O(N2): qudratic 

- N이 커지면 처리시간이 급수적으로 늘어나는 알고리즘.
ex) 이중 루프! , Insertion sort, Bubble sort, Selection sort...
- 단, 이중 루프에서 m이 n보다 작은 경우 O(nm)으로 표시하는 것이 바람직하다.
ex) Radix sort

 

O(2N): Exponential 

- N이 커지면 처리시간이 기하급수적으로 늘어나는 알고리즘.
ex) 피보나치 수열, 재귀가 역기능을 하는 경우..

 

O(N!): Factorial 

- 으악! 20!만 되도 1018이다.. 외판원은 똑똑해야만 한다.
ex) Travelling salesman problem을 brute-force하게 풀었을 때....

 

예제

 

 

 

---

참고 (Reference)

https://velog.io/@happygyu/

Time complexity와 Big-O 표기법

 

Youtube Babo_Coding

 

 

http://web.mit.edu/16.070/www/lecture/big_o.pdf

 

https://velog.io/@kyunghwan1207/

[알고리즘] 시간복잡도(Time Complexity)와 Big-O표기법(Big-O Notation)