시간 복잡도

상수 시간 (Constant time)

만약 어떤 알고리즘의 T(n) 값이 입력 크기에 구애받지 않는 값에 의해서 한정된다면, 이 알고리즘은 상수 시간 (O(1) 시간이라고 쓰기도 함) 이라고 말할 수 있다. 예를 들면, 단 하나의 연산이 어떤 배열에서의 요소 위치를 알아내는 것을 수행한다고 할 때, 이 요소에 접근하는 것은 상수 시간이 걸린다. 그러나 순서가 정해져있지 않은 배열에서의 최소 값을 찾는 것은, 가장 작은 값을 결정하기 위해 어떤 배열에서의 각 요소를 훑는 것이 필요하기 때문에 상수 시간이 아니다. 이것은 그렇기 때문에 선형 시간 연산이며, O(n)시간이 소요된다. 그러나 만약 요소들의 개수를 미리 알고있고 변화가 없다면, 이러한 알고리즘은 상수 시간에 이루어질 수 있다고 말할 수 있다.
"상수 시간"이라는 이름에도 불구하고, 수행시간은 문제의 크기에 독립적일 필요가 없지만 수행시간의 상한은 문제의 크기에 독립적으로 제한된다. 예를 들면, "필요하다면 a와 b를 바꿔서 a≤b가 되도록 하시오"와 같은 것은, 시간이 이미 a≤b조건 만족여부에 종속적이라고 한다고 해도, 상수 시간을 갖는다고 할 수 있다. 그러나 요구되는 시간이 항상 최대 t인 상수 t가 존재하기도 한다.
아래는 상수 시간동안 수행되는 코드의 예제이다.

int index = 5;
int item = list[index];

if(조건이 참일 때) then
    상수 시간 동안 수행되는 어떤 연산을 실행
else
    상수 시간 동안 수행되는 어떤 연산을 실행
for i = 1 to 100
    for j = 1 to 200
        상수 시간 동안 수행되는 어떤 연산을 실행
만약 T(n)이 O(어떤 상수값)이라면, 'T(n)은 O(1)이다'라는 것과 동등하며, 이것을 표준 표기법으로 사용한다.

로그 시간 (Logarithmic time)

만약 T(n) = O(log n) 이라면, 이 알고리즘은 로그 시간이 걸린다고 말할 수 있다. 컴퓨터가 이진수 시스템을 사용하기 때문에, 로그는 밑을 대부분 2로 사용한다. (즉, log₂n, 때때로는 lg n 이라고 쓰임.) 그러나, 로그의 밑이 변할 때, logₐn와 logbn는 오로지 상수 승수에 따라서만 달라지며 이것은 빅-오 표기법에서는 버림한다; 그러므로 O(log n)은 로그의 밑과 상관없이 로그 시간 알고리즘에 대한 표준 표기법이 된다.
로그시간이 걸리는 알고리즘은 이진트리에서의 연산에서나 또는 이진 탐색에서 찾아볼 수 있다.
O(log n)알고리즘은 인스턴스당 연산이 각 인스턴스에 대해서 최대한 줄어드는 것이 필요하기 때문에, 높은 효율을 갖고 있다고 여긴다.
이런 타입의 가장 쉬운 예제 알고리즘은, 문자열을 절반으로 쪼개어 그 오른쪽의 문자열을 다시 또 절반으로 쪼개고, 이를 반복하는 알고리즘으로 생각할 수 있다. 이 알고리즘은 우리가 각각의 출력 이전에 문자열을 절반으로 나누기 때문에, O(log n)시간 (n은 문자열의 길이) 이 소요된다. 이것은 출력 횟수를 증가시키기 위해서는 문자열의 길이를 두배로 늘려야 함을 의미한다.
// 문자열의 오른쪽 절반을 재귀적으로 출력하는 함수.var right = function(str){
    var length = str.length;
    
    // Helper function
    var help = function(index){
        
        //재귀호출 부분: 오른쪽 절반을 출력
        if(index < length){
          
            //인덱스로 배열 끝까지 문자 출력
            console.log(str.substring(index, length));
            
            //재귀 호출 부분: 오른쪽 절반에 대해서 help를 호출
            help(Math.ceil((length + index)/2));
        }
        
        // Base Case: Do Nothing
    }
    help(0);}

다항 로그 시간 (Polylogarithmic time)

만약 T(n) = O(log n)ᵏ) 이라면, 이 알고리즘은 어떤 상수k에 대해 다항 로그 시간동안 수행된다고 말할 수 있다. 예를 들면, 행렬 체인 곱은 병렬 랜덤 접근 기계 (Parallel Random Access Machine: PRAM) 에서 다항 로그 시간에 해결할 수 있다.

서브-선형 시간 (Sub-linear time)

만약 T(n) = o(n) 이면, 이 알고리즘은 서브-선형시간동안 작동된다고 말할 수 있다. 특히 이 알고리즘은 위에서 정의된 시간 복잡도들을 가진 것들을 포함하며, O(n1/2) 인 Grover 탐색 알고리즘을 포함한다.
서브-선형 시간동안 작동하는 전형적인 알고리즘들은 병렬 프로세싱, 비표준 프로세싱을 사용하거나, 입력 구조에 대한 보장된 가정을 갖는다. 그러나 문자열의 처음부터 log(n)번째 비트 위치에서의 한 개의 비트를 갖는 모든 문자열의 집합과 같은 형식 언어는 입력의 모든 비트에 종속적일 수 있고, 서브-선형 시간에 가깝게 계산될 것이다.
서브-선형 시간 알고리즘이라는 특정 용어는 알고리즘들이 전형적인 일렬 기계 모델에서 작동하며 입력에 대해 우선 가정을 허용하지 않는다는 점에서, 위와는 다른 알고리즘을 말한다. 그러나 이 알고리즘들은 랜덤화 될 수 있고, 거의 가장 사소한 정도의 태스크들에 대해서는 반드시 랜덤화 되어야만 한다.
이러한 알고리즘은 반드시 전체 입력을 읽지 않고 결과를 제공해야 하기 때문에, 이것의 특별함은 상세 명세는 입력에 허용되는 접근에 굉장히 종속적이다. 보통 b₁,..., bₖ 로 표현되는 이진 문자열에 대해서, 알고리즘이 어떤 i에 대해 bᵢ의 값을 요청하거나 얻는데 O(1) 시간이 걸린다고 가정할 수 있다.
서브-선형 시간 알고리즘은 보통 랜덤화 되며, 오로지 대략적인 해결책만을 제공해준다. 사실, 0만 가지는 이진 문자열의 특성은 (비근사적인) 서브-선형 시간 알고리즘에 의해서 결정될 수 없다는 것을 쉽게 증명할 수 있다. 서브-선형 시간 알고리즘은 특성 테스팅 (Property testing) 조사에서 자연스럽게 나타난다.

선형 시간 (Linear time)

만약 시간복잡도가 O(n)이면, 이 알고리즘은 O(n)시간 혹은 선형 시간을 갖는다고 말할 수 있다. 약식으로 충분히 큰 입력 크기에 대해서 수행시간이 입력 크기에 따라 선형적으로 증가함을 의미한다. 예를 들어, 리스트의 모든 요소를 더하는 프로시저는 리스트의 길이에 비례하는 시간을 요구한다. 이러한 설명은 수행시간이 특히 작은 n의 값에 대해, 정확한 선형적인 비례형태로부터 상당히 편차를 가질 수 있기 때문에 다소 부정확하다.
종종 선형 시간은 알고리즘의 이상적인 특성으로 여겨진다. 많은 연구자들은 선형 시간이나 그보다 더 좋은 알고리즘을 만드는 것을 연구해왔다. 이러한 연구는 소프트웨어와 하드웨어적인 방법 모두를 포함한다. 수학적으로, 표준 계산 모델을 사용해 선형 시간을 절대 얻을 수 없는 알고리즘들은 하드웨어적인 관점에서 선형 시간동안 실행될 수 있다. 이것을 제공하는 병렬식 방법을 이용하는 하드웨어 기술이 존재하며, 예로 content-addressable 메모리와 같은 것이 있다. 이러한 선형시간 개념은 Boyer-Moore 알고리즘과 Ukkonen 알고리즘과 같은 문자열 매칭 알고리즘에서 사용된다.

선형 로그 시간 (Linearithmic time)

선형 로그 시간은 지수 k가 로그 항의 하나와 동일한 유사 선형 시간의 특이한 경우이다. 선형 로그 함수는 n log n 형태의 함수 즉, 선형과 로그항의 곱이다. 만약 T(n) = O(n log n) 이라면, 알고리즘은 선형로그 시간동안 실행된다고 말할 수 있다. 그러므로 선형로그 항은 선형 항 보다는 빠르게 증가하지만, 1보다 큰 지수를 가진 n의 다항식보다는 느리다.
많은 경우에, n log n 수행시간은 간단히 Θ(log n) 연산의 n 배 수행시간의 결과를 가진다. 예를 들면, 이진 트리 정렬은 n 크기의 배열 각 요소를 하나하나 삽입하여 이진 트리를 만든다. 자가 균형 이진 탐색 트리의 삽입 연산은 O(log n)시간이 걸리기 때문에, 전체 알고리즘은 선형 로그 시간이 걸린다.
비교 정렬은 Stirling 근사에 의해 log(n!) = Θ(n log n)이기 때문에, 최악의 경우 비교 횟수가 최소 선형 로그가 필요하다. 그리고 또한 T(n) = 2T(n/2) + O(n) 재귀 관계에서 빈번히 나타난다.

서브-이차 시간 (Sub-quadratic time)

만약 T(n) = o(n²)이면, 서브-이차 시간의 알고리즘이라고 말할 수 있다.
예를 들면, 간단히 비교 기반 정렬 알고리즘은 이차 (예를 들면, 삽입 정렬) 이지만 더 심화된 알고리즘은 서브-이차 (예를 들면, 쉘 정렬)인 것을 찾을 수 있다. 어떤 범용 정렬도 선형시간에 수행될 수 없지만, 이차에서 서브 이차로의 변경은 대단히 현실적으로 중요하다.

초다항 시간 (Superpolynomial time)

만약 T(n)이 모든 다항식 위에서 경계를 갖지 않는다면, 이것을 초다항 시간이 걸리는 알고리즘이라고 말할 수 있다. 이것은 모든 상수 c에 대해서 n이 입력 파라미터 일 때, ω(nᶜ)시간을 갖는다. (일반적으로, 이 n은 입력값에서의 비트 개수를 뜻한다.)
예를 들면, 크기 n 의 입력값에 대해 2ⁿ단계 실행되는 알고리즘은 초다항 시간을 요구한다. (좀 더 정확히 말하자면, 지수 시간이다.)
지수 자원을 사용하는 알고리즘은 분명하게 초다항이지만, 어떤 알고리즘들은 매우 약한 초다항일 뿐이다. 예를 들면, Adelman-Pomerance-Rumely 소수성 테스트가 n비트의 입력에 대해서 n의 시간동안 실행된다; 이것은 충분히 큰 n에 대해서 모든 다항 시간보다 빠르다. 하지만 입력 크기는 반드시 이것이 작은 지수의 다항식에 의해 지배될 수 없기 전에 비현실적인 크기가 되어야만 한다.
초다항 시간을 필요로하는 알고리즘은 복잡도 클래스 P밖에 놓인다. Cobham 논제는 이런 알고리즘이 비현실적임을 받아들인다. P vs. NP문제가 해결되지 않았기 때문에, 어떤 NP완비 문제도 다항 시간동안 실행될 수 있다고 알려진 것이 없다.

준-다항 시간 (Quasi-polynomial time)

준-다항 시간 알고리즘은 다항 시간보다 느리지만 지수 시간보다는 느리지 않은 알고리즘이다. 준-다항 시간 알고리즘의 최악의 경우 시간은, 어떤 고정된  에 대해  값을 갖는다. 정수 인수분해에 대해  시간이 소요되는 가장 잘 알려진 고전 알고리즘인 대표 숫자 영역 거르기 (general number field sieve) 는 실행 시간이 고정된 c에 대해서 로 나타낼 수 없기 때문에 준-다항시간 알고리즘이 아니다. 만약 준-다항 시간 알고리즘 정의에서의 상수 c가 1과 같다면, 우리는 다항시간 알고리즘을 얻을 수 있고, 1보다 작다면, 서브 선형 시간 알고리즘을 얻을 수 있다.
준-다항 시간 알고리즘은 전형적으로 NP-난제 문제에서 다른 문제로의 환원에서 생길 수 있다. 예를 들면, NP-난제 문제 하나가 3SAT이고, 이것을 다른 문제 B로 바꾸지만 이 문제의 크기는 이다. 이런 경우, 이 환원은 문제 B가 NP-난제임을 증명할 수 없다; 이 환원은 만약 3SAT에 대한 준-다항 시간 알고리즘이 없다면, 단지 B에 부합하는 다항시간 알고리즘이 없다는 것만을 보여줄 수 있다.
비슷하게, 우리가 알고있는 준-다항 시간 알고리즘은 몇가지 있지만, 다항 시간 알고리즘은 없다. 이런 문제는 근사 알고리즘에서 발생한다; 가장 유명한 예제는 방향성 Steiner 트리 문제이고, 이 문제는 정점 개수가 n인 트리에서  의 근사 인자를 달성하는 준-다항 시간 근사 알고리즘이다. 그러나, 다항 시간 알고리즘의 존재를 보여주는 것은 열린 문제이다.
다항시간은 아니지만, 준-다항 시간인 다른 해결 계산 문제들은 László Babai에 의한 그래프 동형 문제와 클릭의 합집합과 랜덤 그래프에서 가장 큰 클릭을 찾는 목표를 가지고 있는 planted clique 문제가 있다.
준-다항 알고리즘이 해결가능하긴 하지만, planted clique 문제는 다항 시간 해결방법이 없다고 추측된다; 이 planted clique의 경우는 계산 게임이론, 특성 테스팅, 기계학습에서의 다른 여러 문제들의 어려운 정도를 증명하기 위한 계산 난제 가정 (computational hardness assumption) 으로서 사용된다.
QP 복잡도 클래스는 모두 준-다항 시간 알고리즘으로 이루어져있다. 이것은 다음의 DTIME으로 정의된다.

NP-완비문제와의 연관

복잡도 이론에서, 미해결 문제인 P vs. NP문제는 NP문제 모두가 다항 시간 알고리즘인지의 여부를 묻는다. 3SAT문제 등과 같은, 모든 알려진 NP-완비문제 알고리즘들은 지수 시간이 걸린다. 실제로, 서브-지수 시간 알고리즘을 가지지 않는 많은 자연 NP-완비 문제들에 대해 추측이 되어왔다. 여기서 "서브-지수 시간"은 아래 두번째 정의에 표시되어 있다. (반면, 인접 행렬 방법을 사용한 많은 그래프 문제들은 입력 크기가 정점 개수의 제곱이기 때문에, 서브 지수 시간에 해결이 가능하다.)
이러한 k-SAT문제에 대한 가정은 지수 시간 가정으로 알려져있다. NP-완비 문제가 준-다항 시간 알고리즘을 갖고있지 않다고 생각되기 때문에, 근사 알고리즘 영역에서 근사적이지 않은 결과는 NP-완비 문제가 준-다항 시간 알고리즘을 갖지 않는다는 가정을 만든다. 예를 들면, 집합 덮개 문제의 비근사적 결과와 같은 것이다.

서브-지수 시간 (Sub-exponential time)

서브-지수 시간이라는 용어는 어떤 알고리즘의 수행시간이 다항시간보다 빠르지만 현저히 지수시간 보다는 작게 증가하는 것을 표현하는데 사용한다. 이러한 점에서, 서브-지수 시간 알고리즘은 오로지 지수 알고리즘보다는 다소 더 추적이 가능한 문제들이다. "서브-지수 시간"의 정확한 정의는 동의가 되어있지 않고, 아래의 두 정의가 폭넓게 사용되고 있다.

지수 시간 (Exponential time)

poly(n)이 n에서의 어떤 다항식이라고 할 때, 만약 T(n)이 2로 상한이 정해진다면, 이 알고리즘은 지수 시간을 갖는다고 말할 수 있다. 더 형식적으로, 만약 T(n)이 어떤 상수 k에 대해서 를 갖는다면, 지수 시간을 갖는다. 결정적 튜링 머신에 대해 지수 시간 알고리즘인 문제들은 EXP로 알려져있는 복잡도 클래스를 만든다.
가끔 지수 시간은 지수가 최대 n의 선형 함수일 때, T(n) = 2을 갖는 알고리즘으로 사용되기도 하며, 복잡도 클래스 E를 표현한다.