자바 알고리즘 인터뷰 05. 빅오 표기법

 

보통 시간 복잡도를 구할 때는 연산 횟수를 고차 다항식으로 나타내서 차수로 표기하는 방법을 사용한다

 

- O(1) : 해시 테이블 조회, 삽입 연산 / 연결리스트 끝 값 삽입 연산

- O(log n) : 이진 탐색

- O(n) : 리스트에서 최대값이나 최소값 찾기

- O(n*log n) : 병합 정렬, java의 DualPivotQuicksort 방식을 사용하는 Arrays.sort()의 평균

- O(n^2) : 버블 정렬, Arrays.sort()의 최악

- O(2^n) : 피보나치 재귀 함수