Complexidade temporal

A tabela a seguir resume algumas classes de complexidade comumente encontradas. Na tabela, poly(x) = xO(1), i.e., polinomial em x.

Um algoritmo é dito de tempo constante (também escrito como tempo O(1)) se seu valor de T(n) é ligado à um outro valor que não depende do tamanho da entrada. Por exemplo, acessar qualquer elemento específico em um array leva tempo constante, pois apenas uma operação deve ser realizada para localiza-lo. No entanto, encontrar o valor mínimo em um array desordenado não é de tempo constante, uma vez que deve se escanear cada elemento do array para se determinar o valor mínimo. Assim, esta é uma operação de tempo linear, tomando tempo O(n). Se o número de elementos é conhecido previamente e não se altera, pode-se encontrar um algoritmo para esta operação em tempo constante. Apesar do nome "tempo constante", o tempo de execução não tem de ser independente do tamanho do problema, mas um limite superior para o tempo de execução tem que ser definido de forma independente do tamanho da entrada. Por exemplo, a tarefa "trocar os valores de a e b, se necessário, de modo que a≤b" é de tempo constante, mesmo que não se saiba se a troca será realizada, pois não sabemos se a ≤ b. No entanto, existe alguma constante t de tal modo que o tempo requerido é sempre no máximo T.

Um algoritmo é dito tomar tempo logarítmico se T(n) = O(log n). Devido ao uso do sistema numeral binário pelos computadores, o logaritmo é com frequência de base 2 (isto é, log2 n, algumas vezes escrito como lg n). Mesmo sendo, pela mudança de base para os logaritmos, loga n and logb n diferem apenas por um multiplicador constante, o qual em notação big-O é descartado; assim O(log n) é a notação padrão para algoritmos de complexidade de tempo logarítmica, independente da base deste logaritmo. Algoritmos de tempo logaritmo são frequentemente encontrados em operações comárvore binária ou busca binária. Um algoritmo O(log n) é considerado altamente eficiente, uma vez que as operações por instância requeridas diminuem a cada instância recorrente. Um exemplo muito simples deste tipo é um algoritmo que corta uma corda em metade, em seguida, reduz a metade direita no meio, e assim por diante. Levará O (log n) (n sendo o comprimento da corda) desde que cortar a corda ao meio antes de cada iteração (fazemos a suposição de que console.log e str.substring rodam em tempo constante). Isto significa que, a fim de aumentar o número de cópias, temos que dobrar do comprimento da corda.

Um algoritmo é dito rodar em tempo polilogarítmico se T(n) = O((log n)k), para alguma constante k. Por exemplo, o problema matrix chain ordering pode ser resolvido em tempo polilogarítmico em uma Parallel Random Access Machine.

Um algoritmo é dito ser executado em tempo sublinear se T(n) = O (n). Em particular, isto inclui algoritmos com as complexidades de tempo definidos acima, bem como outros, tais como o Algoritmo de Busca de Grover O(n½) . O termo específico algoritmo de tempo sublinear é normalmente reservado para algoritmos que rodam sobre as clássicas máquinas seriais (excluindo as de processo paralelo e de processamento não-clássico) e onde não são permitidas informações prévias sobre a entrada. Porém, lhes é permitido serem randômicas, e assim devem ser randômicas para todas exceto as mais triviais das tarefas. Assim, tais algoritmos devem ser capazes de prover uma resposta sem avaliar toda a entrada e são altamente dependentes do acesso à mesma. Usualmente para uma entrada que é representada como uma cadeia binária b1,...,bk se assume que o algoritmo pode em tempo O(1) obter o valor de bi para qualquer i.

Um algoritmo é dito ter tempo linear, ou O (n), se sua complexidade de tempo é O (n). Informalmente, isto significa que para grandes tamanhos de entrada, o tempo de execução aumenta linearmente com o tamanho da entrada. Por exemplo, um procedimento que acrescenta-se todos os elementos de uma lista requer tempo proporcional ao comprimento da lista. Esta descrição é um pouco imprecisa, já que o tempo de execução pode desviar-se significativamente a partir de uma proporcionalidade, especialmente para pequenos valores de n. Muita pesquisas foram geradas na criação de algoritmos exibindo (quase) tempo linear ou melhor. Estas pesquisas incluem tanto software e métodos de hardware. No caso do hardware, alguns algoritmos que, matematicamente falando, nunca podem atingir o tempo linear com modelos de computação padrão são capazes de rodar em tempo linear. Há várias técnicas de hardwares que fazem uso do paralelismo para tal feito. Um exemplo é a memória content-addressable. Este conceito de tempo linear é usado em algoritmos de identificação de strings, como os de Boyer-Moore e Ukkonen.

Um algoritmo é dito ser quasilinear se T(n) = O(n logk n) para qualquer constante k; sendo linearítmico um caso especial de quasilinear, onde k = 1. Usando a notação soft-O, estes algoritmos são Õ(n). Algoritmos de tempo quasilinear também são o(n1+ε) para todo ε > 0, e assim rodam mais rápido do que qualquer polinomial em n com expoente estritamente maior do que 1. Algortimos que rodam em tempo quasilinear, incluem:

Um algoritmo é dito ser de tempo polinomial se seu tempo de execução é limitado superiormente por uma expressão polinomial no tamanho da entrada do algoritmo, i.e., T(n) = O(nk) para uma constante k. Problemas para os quais um algoritmo de tempo polinomial existe pertencem à classe de complexidade P, que é o campo central da teoria da complexidade computacional. A Tese de Cobham determina que este tempo polinomial é um sinônimo para "tratável", "eficiente", ou "rápido". Alguns exemplos de algoritmos de tempo polinomial: