250904 - 빅오 표기법 여러가지 함수 정리

수업을 듣는데

지수함수가 뭔지 그림을 못 그리겠더라..

이럴순 없지

 

1. O(1)

입력 크기와 무관하게 실행 시간이 일정한 경우

ex. 조회

 

2. O(log n)

입력 크기가 커질수록, 실행 시간은 로그 비율로 증가

데이터가 두 배로 늘어날 때, 실행 횟수는 1번만 늘어남

ex. 이진 탐색

 

2를 몇 번 곱해야 N이 나올까? = log2N

1이 될 때까지 N을 2로 몇 번 곱해야 할까? = log2N

ex. 2를 세 번 곱해야 8이 나오니 log28 = 3

 

 

 

3. O(n)

입력 크기에 비례하여 실행 시간이 증가

ex. 선형 탐색

 

 

4. O(n log n) [로그함수]

입력이 커질수록 n보다 조금 더 빠르게 증가

ex. 병합 정렬, 퀵 정렬

 

5. O(n^2) [다항함수]

입력 크기의 제곱에 비례

중첩 반복문

ex. 버블 정렬, 삽입 정렬

 

6. O(n^3)

입력 크기의 세제곱에 비례

3중 반복문

ex. 행렬 곱셈

 

7. O(n^k)

다중 반복문에서 발생

k 가 클수록 실행 시간은 폭발적으로 증가

 

8. O(2^n) [지수함수]

입력 크기 n이 1씩 증가할 때마다 실행 시간이 2배씩 증가

최악이군..

 

9. O(n!)

입력 크기 n에 대해 n! 번 연산이 필요

 

참고 자료

https://www.mathfactory.net/11244

수학 공식 | 고등학교 > 로그함수의 뜻과 그래프

https://velog.io/@on-n-on-turtle/%EB%88%84%EA%B5%AC%EB%82%98-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%99%80-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B9%85%EC%98%A4%ED%91%9C%EA%B8%B0%EB%B2%95

[누구나 자료구조와 알고리즘] O(N), O(1), O(logN), 로그 뜻, 빅오표기법, 상수시간, 로그시간