2. 자주 사용하는 자료 구조의 시간 복잡도
▼ 표 2-2 자주 사용하는 자료 구조에 따른 시간 복잡도
|
자료 구조 |
탐색 |
삽입 |
삭제 |
|
배열 |
O(n) |
O(n) |
O(n) |
|
정렬된 배열 |
O(logn) |
O(n) |
O(n) |
|
연결 리스트 |
O(n) |
O(1) |
O(1) |
|
스택/큐 |
O(n) |
O(1) |
O(1) |
|
해시 |
O(1) |
O(1) |
O(1) |
|
이진 트리 |
O(logn) |
O(logn) |
O(logn) |
잠깐만요
연산에서 1초의 기준이란?
문제를 풀다 보면 시간 제한에 걸리곤 합니다. 연산이 비효율적이거나, 입력값과 맞지 않는 알고리즘을 사용했기 때문일 수도 있습니다. 1초에 몇 번까지 연산할 수 있는지 인터넷에서 검색해보면 ‘1억 번 연산에 1초’라는 말을 상당히 많이 볼 수 있습니다. 왜 1억 번일까요? 의외로 굉장히 단순한 이유입니다. CPU가 1초에 1억 번 연산하기 때문입니다.
채점 서버는 물리적 CPU를 바탕으로 연산하고, 코드를 돌리면서 시간 복잡도를 테스트합니다. 따라서 입력 데이터 10만 개를 정렬하는 경우 for 문 2개로 계산하면 O(n2)이므로 10만 X 10만 = 100억 정도의 연산이 발생하고, 이는 곧바로 시간 초과로 이어집니다. 하지만 그와 동시에 ‘시간이 지나면 컴파일러도 더 좋아질 것이고, CPU도 좋아질 테니 시간 여유가 더 생기지 않을까?’라는 생각이 떠오르겠지만 아쉽게도 그렇지 않습니다.