Em ciência da computação, a complexidade de tempo de um algoritmo quantifica a porção de tempo tomada por um algoritmo para rodar em função do tamanho da entrada do problema. A complexidade de tempo de um algoritmo é comumente expressada usando a notação big O, que suprime constantes multiplicativas e outros termos de menor ordem. Quando expressada dessa forma, a complexidade de tempo é descrita como assintótica, i.e., o tamanho da entrada tende ao infinito. Por exemplo, se o tempo requisitado por um algoritmo em todas as entradas de tamanho n é no máximo 5n3 + 3n, a assíntota da complexidade de tempo é O(n3).

Complexidade de tempo é comumente estimada pela contagem do número de operações elementares realizadas pelo algoritmo, onde a operação elementar toma a quantia fixa de tempo para realizar. A quantidade de tempo tomada e o número de operações elementares realizadas pelo algoritmo diferem no máximo de um fator constante.

Desde que o algoritmo deve tomar uma quantidade diferente de tempo mesmo dentro de entradas de mesmo tamanho, a medida mais comum de complexidade de tempo usada, o pior caso do algoritmo de complexidade de tempo, denotado T(n), é no máximo a quantidade de tempo usada numa entrada de tamanho n. A complexidade de tempo é classificada pela natureza da função T(n). Por exemplo, um algoritmo com T(n) = O(n) é chamado de algoritmo de tempo linear, e um algoritmo com T(n) = O(2n) é dito ser um algoritmo de tempo exponencial.

Tabela de complexidade de tempo comum A tabela a seguir resume algumas classes de complexidade de tempo comumente usadas. Na tabela, poly(x) = x0(1), isto é, polinomial em X.

Nome Classe de Complexidade Tempo de execução (T(n)) Exemplos de tempo de execução Exemplos de algoritmos Tempo constante O(1) 10 Determinando se o número é par ou ímpar Função inversa de Ackermann O(α(n)) Tempo amortizado por operação usando um conjunto dijunto Logaritmo Iterativo O(log-star(n) ) Algoritmo de Cole-Vishkin log-logarítmico O(log log n) Tempo amortizado por operação usando uma fila de prioridades limitada Tempo logarítmico DLOGTIME O(log n) log n, log(n2) Busca binária Tempo poli-logarítmico poly(log n) (log n)2 potência fracionária O(nc) onde 0 < c < 1 n1/2, n2/3 Procurando em uma kd-tree Tempo linear O(n) n Procurando o menor item em um array não ordenado "n log star n" O(nlog-star(n)) Algoritmo de triangulação de polígonos de Seidel. Tempo linearitmico O(n log n) n log n, log n! A ordenação por comparação mais rápida Tempo quadrático O(n2) n2 Bubble sort; Insertion sort Tempo cúbico O(n3) n3 Multiplicação ingênua de duas matrizes n×n. Calculando correlação parcial. Tempo polinomial P (classe de complexidade) 2O(log n) = poly(n) n, n log n, n10</sup> Algoritmo de Karkamar para programação linear; Teste de primalidade de AKS Tempo quasi-polinomial QP 2poly(log n) nlog log n, nlog n Melhor conhecido O(log2 n)-algoritmo de aproximação para o problema da árvore de Steiner dirigida. Tempo sub-exponencial(primeira definição) SUBEXP O(2nε) para todos ε > 0 O(2log nlog log n) Assumindo a complexidade do teorema de conjecturas, Polinômio probabilístico com limitação de erro está contido em um SUBEXP. Tempo sux-exponencial(segunda definição) 2o(n) 2n1/3 Melhor algoritmo conhecido para a fatoração de inteiros e isomorfismo em grafos Tempo exponencial E (classe de complexidade) 2O(n) 1.1n, 10n Resolvendo o problema do Caixeiro Viajante usando programação dinâmica Tempo exponencial EXPTIME 2poly(n) n!, nn, 2n2 Tempo fatorial O(n!) n! Resolvendo o problema do caxeiro viajante via busca com força-bruta Tempo duplamente exponencial 2-EXPTIME 22poly(n) 23n Decidindo a verdade de uma informação dada pela Aritmética de Presburger

Tempo Constante

Um algoritmo é dito ser em tempo constante (também escrito como executado em tempo O(1)) se o valor de T(n) é limitado por uma valor que não dependa do tamanho da entrada. Por exemplo, acessando um único elemento de um array usa tempo constante, visto que uma única operação foi executada para localizá-la. Encontrar o menor valor de um vetor não ordenado, contudo, não é uma operação de tempo constante, visto que é necessário olhar sobre todos os elementos do vetor para determinar qual é o menor valor de todos. Isto é, consequentemente, uma operação em tempo linear, em relação ao tamanho da entrada, utilizando tempo O(n). Se o número de elementos é conhecido posteriormente e não se altera, contudo, tal algoritmo pode ser dito que execute em tempo constante.

Apesar do nome "tempo constante", o tempo de execução pode não ser independente do tamanho da entrada, mas um limitante superior para o tempo de execução deve ser posto, independentemente do tamanho do problema. Por exemplo, a tarefa "trocar os valores de 'a' e 'b' tal que a=b" é dito como tempo tempo constante, mesmo que o tempo possa depender de que seja já verdade ou não que a = b. Existe uma constante t, contudo, tal que o tempo requerido seja, no máximo t.

Eis uns exemplos de trechos de códigos que rodam em tempo constante:

int index = 5; int item = list[index]; se (condição verdadeira) então execute alguma operação que rode em tempo constante senão execute alguma outra operação em tempo constante para i = 1 até 100 para j = 1 até 200 execute alguma operação que rode em tempo constante.

Se T(n) é O(valor constante), isto é equivalente a ser dito como, na notação padrão que T(n) sendo O(1).

Tempo logarítmico Um algoritmo é dito ter tempo logaritmo se T(n) = O(log n). Devido ao uso do sistema de números binários pelos computadores, o logaritmo é frequentemente de base 2 (isto é, log2 n, muitas vezes escrito lg n). Contudo, pela troca da equação base para logaritmos, loga n and logb n diferem apenas por uma constante multiplicadora, porque na notação big-O é descartada; logo O(log n) é a notação padrão para algoritmos de tempo logaritmo independente da base do logaritmo.

Algoritmos que executam em tempo logarítmico são comumente encontrados em operações em árvores binárias ou quando se usa busca binária

Tempo Poli-logarítmico Um algoritmo é dito rodar em tempo polilogaritmo se T(n) = O((log n)k), para alguma constante k. Por exemplo, a ordenação de uma cadeia de matrizes pode ser resolvida em tempo poli-logarítmico em uma máquina paralela de acesso aleatório.

Tempo sub-linear Um algoritmo é dito rodar em tempo sub-linear (frequentemente chamado tempo sublinear) se T(n) = o(n). Particularmente isso inclui algoritmos com complexidade de tempo definida acima, também tal como o O(n½) algoritmo de busca de Grover.

Para um algoritmo ser exato e ainda rodar em tempo sub-linear, é necessário usar processamento paralelo (como o cálculo de determinante de matrizes NC1 faz) ou processamento não-clássico (como a busca de Grover faz), ou alternativamente ter garantido uma suposição na estrutura da entrada (como a busca binária de tempo logaritmo e algoritmos de manuntenção de muitas árvores faz). Caso contrário, um algoritmo de tempo sub-linear não poderia ler ou aprender previamente toda a entrada para prover sua saída.

O termo específico algoritmo de tempo sublinear é usualmente reservado para algoritmos que são diferentes dos acimas uma vez que eles rodam sobre uma máquina serial clássica e não é permitido previamente supor a entrada. Eles são, contudo, passíveis de serem aleatorizados e, claramente, serão para todos, exceto nos casos mais triviais.

Eles, no entanto, são permitidos se randomizarem, e de fato precisam ser randomizados para tudo mas a maioria são tarefas triviais. Um algoritmo precisa prover uma resposta sem ler toda a entrada, isso é particularmente difícil dependendo do acesso permitido a entrada. Usualmente para uma entrada que é representada como uma string binária b1,...,bk é assumido que o algoritmo possa, em tempo O(1), pedir e obter o valor de bi para qualquer i.

Algoritmos de tempo sublinear são tipicamente aleatórios e provêm apenas aproximações da solução. De fato, a propriedade de string binários que contêm apenas zeros (e nenhum uns) pode ser facilmente mostrada que não é decídivel por um algoritmo (não-aproximado) de tempo sublinear. Algoritmos de tempo sublinear naturalmente surgem na investigação de teste de prioridade.

Tempo linear Um algoritmo é dito que usa tempo linear, ou tempo O(n), se sua complexidade de tempo é O(n). Informalmente, isto significa que para entradas grandes o suficiente o tempo de execução delas aumenta linearmente com o tamanho da entrada. Por exemplo, um procedimento que adiciona todos os elementos em uma lista requere tempo proporcional ao tamanho da lista. Esta descrição é levemente imprecisa, visto que o tempo de execução pode desviar significantemente de uma proporção precisa, especialmente para valores pequenos de n.

Tempo linear é comumente visto como um atributo desejável para um algoritmo. Muitas pesquisas foram investidas na criação de algoritmos exibindo (próximos a) tempos lineares ou melhores. Esta pesquisa inclui tanto abordagens de software como hardware. No caso de hardware, alguns algoritmos que, matematicamente falando, pode nunca alcançar tempo linear com os modelos de computação comum são aptos a rodar em tempo linear. Existem várias tecnologias de hardware que exploram paralelismo para prover isto. Um exemplo disto é memória de conteúdo endereçável. Este conceito de linearidade de tempo é usado em algoritmos de emparelhamento de strings tais como o algoritmo de Boyer-Moore e o algoritmo de Ukkonen.

Tempo Linearitmico/quasilinear Uma função linearitmica (conjunção de linear e logarítmica) é uma função do formato n . log n (isto é, um produto de termos lineares e logarítmicos). Um algoritmo é dito executar em tempo linearitmico se T(n) = O(n log n). Comparada a outras funções, uma função linearítmica é ω(n), o(n1+ε) para todo ε > 0 e Θ(n · log n). Um termo linearítmico cresce mais rápido que um termo linear, mas mais devagar que algum polinômio em n com expoente estritamente maior que 1.

Um algoritmo é dito executar em tempo quasilinear se T(n) = O(n logk n) para alguma constante k. Algoritmos de tempo qualisnear também são o(n1+ε) para todo ε > 0 e, portanto, executa mais rápido que um polinômio em n com expoente estritamente maior que 1.

Em muitos casos, o tempo de execução n . log n é simplesmente o resultado de executar T(log n) operações n vezes. Por exemplo, ordenação por árvores binárias cria uma árvore binária ao inserir cada elemento do vetor de tamanho n em cada vez. Visto que a operação de inserção em uma árvore binária de busca utiliza tempo O(log n), todo o algoritmo usa tempo linearitmico.

Ordenação de comparações requere ao menor uma quantidade de operações linearítmicas no pior caso, pois log(n!) = T(n log n), pela aproximação de Stirling. Eles aparecem frequentemente na relação de recorrência T(n) = 2 * T(n/2) + O(n).

Alguns algoritmos que executam em tempo linearitmico incluem: Comb sort, no caso médio e pior caso Quicksort no caso médio Heapsort, Merge sort, introsort, ordenação por árvore binária, smoothsort, patience sorting, etc. no pior caso Transformada Rápida de Fourier Cálculo do array de Monge

Tempo subquadrático Um algoritmo é dito subquadrático se T(n) = o(n2).

Por exemplo, a maioria dos algoritmos baseados em comparações ingênuas são quadráticos (por exemplo insertion sort), mais algoritmos mais avançados que são encontrados são subquadráticos (por exemplo shell sort). Nenhum tipo de ordenação com intúitos gerais roda em tempo linear, mas a mudança de quadrático para subquadrático é de grande importância prática.

Tempo Polinomial