코딩 테스트 합격자 되기 스터디 1주차 : 시간복잡도

시간복잡도

시간복잡도란, 알고리즘의 성능을 나타내는 지표로 입력 크기에 대한 연산 횟수의 상한을 의미한다.
(입력 크기 = 처리해야 할 데이터양)

 

입력값을 기준으로 자료구조 및 알고리즘을 고려한다.

컴퓨터가 초당 연산할 수 있는 최대 횟수는 약 1억 번이다.

ex) N값이 1,000,000일경우 N^2은 사용할 수 없지만 logN은 사용할 수 있다.

  * N^2 = 1,000,000 * 1,000,000 = 제한시간 1초 초과

  * logN = 2^19 < 1,000,000 < 2^20 = 제한시간 1초 이내 계산

 

점근적 표기법

정확한 연산횟수가 아닌 연산횟수의 추이를 활용해 시간복잡도를 표기

최악의 경우를 고려해서 점근적 표기법으로 나타내는 것을 빅오표기라고 한다.

시간 복잡도N의 가용 범위

시간 복잡도	N의 가용범위
O(log⁡N)	10억
O(N)	1,000만~2,000만
O(Nlog⁡N)	100만
O(N^2)	3,000~5,000
O(N^3)	200~300
O(2^N)	20~25
O(N!)	10

 

 알고리즘별 성능

정렬 알고리즘	최선	평균	최악
버블 정렬	O(n^2)	O(n ^2)	O(n ^2)
힙 정렬	O(n log n)	O(n log n)	O(n log n)
삽입 정렬	O(n ^2)	O(n ^2)	O(n ^2)
합병 정렬	O(n log n)	O(n log n)	O(n log n)
퀵 정렬	O(n log n)	O(n log n)	O(n ^ 2)
선택 정렬	O(n^2)	O(n ^ 2)	O(n ^ 2)
셸 정렬	O(n)	O(n^1.5)	O(n^2)

 

자료 구조별 성능

Data Structure	Search (Average)	Insert (Average)	Delete (Average)	Search (Worst)	Insert (Worst)	Delete (Worst)
Sorted Array
Array
Linked List
Doubly Linked List
Stack
Hash Table
Binary Search Tree
B-Tree
Red-Black Tree
AVL Tree

 

 

[출처] 코딩테스트 합격자 되기 - C++