빅오 표기법

빅오 표기법 

알고리즘의 효율성을 표기하는 표기법.

시간 복잡도(시간 효율성)와 공간 복잡도(메모리 효율성)를 나타내는데 주로 사용

 

빅오 표기법의 특징

1. 상수항 무시 : 빅오 표기법은 데이터 입력값(n)이 충분히 크다고 가정함.

                     2중 for문이 아니라 for문이 2번 돌았다고 표기법이 바뀌지 않음

                     O(2N) -> O(N)

2. 영향력 없는 항 무시 : 가장 영향력이 있는 큰 항 외는 무시

                                O(N^2+2N+1) -> O(N^2)

 

빅오 표기법 성능 비교

https://noahlogs.tistory.com/27

빠름                                                             느림

O(1) < O(log n) < O(n)< O(n log n) < O(n^2) < O(2^n)

 

빅오 표기법 예제

O(1) : 스택에서 push , pop  :                        입력하는 데이터에 상관없이 항상 일정한 시간이 걸리는 알고리즘

O(log n) : 이진트리  :                                  한번 검색마다 검색범위가 절반씩 줄어드는 것

O(n) : for문 :                                             데이터가 증가함에 따라 처리시간도 증가, for문이 2개라고 증가 x

O(n log n) : 퀵 정렬, 병합 정렬, 힙 정렬

O(n^2) : 이중 for문, 삽입 정렬, 거품 정렬, 선택 정렬   

O(2^n) : 피보나치수열