C++ 시간 복잡도

 

이름	수행시간	알고리즘 예시	설명
상수 시간	O(1)	값을 검색할 때, 객체에서 키를 알거나 배열에서 인덱스를 알고 있으면 언제나 한 단계만 걸림.	입력값 n 이 주어졌을 때, 알고리즘이 문제를 해결하는데 오직 한 단계만 거침
지수 시간	O(C^n)	동적 계획법을 사용한 외판원 문제 해결	문제를 해결하기 위한 단계의 수는 주어진 상수값 C 의 n 제곱
선형 시간	O(n)	정렬되지 않은 배열에서 가장 작은 수 또는 가장 큰 수를 탐색	문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가짐
로그 시간	O(log n)	배열에서 값을 찾을 때, 어느 쪽에서 시작할지를 알고 있으면 검색하는 시간이 두배로 줄어듦	입력값 n 이 주어졌을 때, 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듦.