Complexidade temporal

Em ciência da computação, a complexidade temporal de um algoritmo quantifica o montante de tempo tomado por este dado algoritmo rodar como uma função do comprimento de uma cadeia representando os dados de entrada^[1]:226. A complexidade temporal de um algoritmo é comummente expressada usando a notação big O, que exclui coeficientes e termos de baixa ordem. Quando expressado desta forma, a complexidade temporal é dita ser descrita assintoticamente. Por exemplo, se o tempo requerido por um algoritmo em todas as entradas de tamanho n é no máximo 5n³ + 3n operações elementares para qualquer n (maior do que algum n₀), a complexidade de tempo assintótica é O(n³).

A complexidade temporal é normalmente estimada através da contagem do número de operações elementares realizadas pelo algoritmo, em que uma operação elementar leva uma quantidade de tempo fixo para executar. Assim, a quantidade de tempo necessário e o número de operações elementares realizadas pelo algoritmo diferem no máximo por um fator constante.

Uma vez que o tempo de execução de um algoritmo pode variar com diferentes entradas do mesmo tamanho, utiliza-se comumente a complexidade de pior caso de um algoritmo, denotada por T(n), que define a quantidade máxima de tempo tomado em qualquer entrada de tamanho n. Menos comum, e usualmente especificado de forma explícita, há a medida de Complexidade de caso médio. As complexidades temporais são classificadas pela natureza da função T (n). Por exemplo, um algoritmo com T (n) = O (n) é chamado um algoritmo de tempo linear, e um algoritmo com T(n) = O(Mⁿ) e mⁿ= O(T(n)) para algum M ≥ n > 1 é dito ser um algoritmo de tempo exponencial.

Tabela de tempos de complexidade comuns

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

Nome do Tempo	Classe de Complexidade	Exemplo de Algoritmo
constante	O(1)	Determinar se um inteiro (representado em binário) é par
Função de Ackermann	O(α(n))	Tempo de Análise Amortizada por operação usando um conjunto disjunto
logaritmo iterado	O(log* n)	Coloração de Grafos
log-logaritmo	O(log log n)	Análise Amortizada por operação usando fila de prioridade ligada^[2]
logaritmo	DLOGTIME	Pesquisa binária
pollilogaritmo	poly(log n)	(log n)²
potência fracional	O(n^c) where 0 < c < 1	Busca em uma kd-tree
linear	O(n)	Encontrar o menor ou maior elemento em um array desordenado
"n log estrela n"	O(n log* n)	Algoritmo de Triangulação de Polígodo de Seidel
linearitmo	O(n log n)	O mais rápido comparison sort
quadrático	O(n²)	Bubble sort; Insertion sort; Direct convolution
cúbico	O(n³)	Calcular correlação parcial
polinomial	P	Algoritmo de Karmarkar para programação linear; Teste de Primalidade AKS
quasi-polinomial	QP	O melhor dos conhecidos algoritmos O(log² n)- de aproximação para uma árvore Steiner direcionada.
sub-exponencial (primeira definição)	SUBEXP	Assumindo conjecturas teóricas, BPP está contido em SUBEXP.^[3]
sub-exponencial (segunda definição)	2^o(n)	O melhor dos conhecidos algoritmos fatoração de inteiros e isomorfismo de grafos
exponencial (com expoente linear)	E	Resolver o problema do caixeiro viajante usando programação dinâmica
exponencial	EXPTIME	Resolver matrix chain multiplication através de busca por força bruta
fatorial	O(n!)	Resolver o problema do caixeiro viajante através de busca por força bruta
duplo exponencial	2-EXPTIME	Decidir a veracidade de uma declaração na Aritmética de Presburger

Tempo constante

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.

Aqui estão alguns exemplos de fragmentos de código que rodam em tempo constante:

int index = 5;
int item = list[index];
if (condition true) then
   perform some operation that runs in constant time
else
   perform some other operation that runs in constant time
for i = 1 to 100
   for j = 1 to 200
      perform some operation that runs in constant time

Tempo logarítmico

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 é, log₂ n, algumas vezes escrito como lg n). Mesmo sendo, pela mudança de base para os logaritmos, log_a n and log_b 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.

// Function to recursively print the right half of a string
var right = function(str){
    var length = str.length;

    // Helper function
    var help = function(index){

        // Recursive Case: Print right half
        if(index < length){

            // Prints characters from index until the end of the array
            console.log(str.substring(index, length));

            // Recursive Call: call help on right half
            help(Math.ceil((length + index)/2));
        }

        // Base Case: Do Nothing
    }
    help(0);
}

Tempo polilogarítmico

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.^[4]

Tempo sublinear

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.^[5] 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 b₁,...,b_k se assume que o algoritmo pode em tempo O(1) obter o valor de b_i para qualquer i.

Tempo linear

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.

Tempo quasilinear

Um algoritmo é dito ser quasilinear se T(n) = O(n log^k n) para qualquer constante k; sendo linearítmico um caso especial de quasilinear, onde k = 1.^[6] Usando a notação soft-O, estes algoritmos são Õ(n). Algoritmos de tempo quasilinear também são o(n^1+ε) 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:

In-place merge sort, O(n log² n)
Quicksort, O(n log n), em sua versão randômica, possui um tempo linearitmico na expectativa de entrada de pior cenário. Sua versão não randomizada possui um tempo linearitmico apenas quando considerada a complexidade de caso médio.
Heapsort, O(n log n), merge sort, introsort, binary tree sort, smoothsort, patience sorting, etc. no pior cenário.
Fast Fourier transforms, O(n log n)
Cálculo de monge array, O(n log n)

Tempo polinomial

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(n^k) para uma constante k.^[1]^[7] 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".^[8]

Alguns exemplos de algoritmos de tempo polinomial:

O algoritmo quicksort sobre n inteiros executa no máximo $An^{2}$ operações para uma constante A. Assim então rodando em tempo $O(n^{2})$ e sendo um algoritmo de tempo polinomial.
Todas as operações aritméticas básicas (adição, subtração, multiplicação, divisão e comparação) podem ser realizadas em tempo polinomial.
Acoplamento em grafos pode ser encontrado em tempo polinomial.

Fortemente e fracamente polinomial

Em alguns contextos, especialmente em otimização, pode-se diferencias algoritmos de tempo fracamente ou fortemente polinomial. Estes dois conceitos são relevantes apenas se a entrada para o algoritmo consiste de inteiros.

Tempo fortemente polinomial é definido no modelo aritmético da computação. Neste modelo de computação, as operações aritméticas básicas (adição, subtração, divisão, multiplicação e comparação) tomam somente uma unidade de tempo para serem executadas, independente do tamanho de seus operandos. Um algoritmo roda em tempo fortemente polinomial se ^[9]

O número de operações no modelo aritmético computacional estiver ligado por uma função polinomial do número de inteiros na entrada; e
O espaço usado pelo algoritmo esteja ligado por uma função polinomial ao tamanho da entrada.

Um algoritmo que roda em tempo polinomial mas não é fortemente polinomial, é dito que roda então em tempo fracamente polinomial.^[10] Um exemplo de um problema bem conhecido para o qual é usado um algoritmo fracamente polinomial, mas não é sabido se admite um algoritmo fortemente polinomial é a programação linear. Tempo fracamente polinomial não deve ser confundido com tempo pseudo-pol

Referências

↑ ^a ^b Sipser, Michael (2006).
↑ Mehlhorn, Kurt; Naher, Stefan (1990).
↑ Babai, László; Fortnow, Lance; Nisan, N.; Wigderson, Avi (1993).
↑ Bradford, Phillip G.; Rawlins, Gregory J. E.; Shannon, Gregory E. (1998).
↑ Kumar, Ravi; Rubinfeld, Ronitt (2003).
↑ Naik, Ashish V.; Regan, Kenneth W.; Sivakumar, D. (1995).
↑ Papadimitriou, Christos H. (1994).
↑ Cobham, Alan (1965).
↑ Grötschel, Martin; László Lovász; Alexander Schrijver (1988).
↑ Schrijver, Alexander (2003).

[Sipser-1] Sipser, Michael (2006).

[2] Mehlhorn, Kurt; Naher, Stefan (1990).

[bpp-3] Babai, László; Fortnow, Lance; Nisan, N.; Wigderson, Avi (1993).

[4] Bradford, Phillip G.; Rawlins, Gregory J. E.; Shannon, Gregory E. (1998).

[5] Kumar, Ravi; Rubinfeld, Ronitt (2003).

[6] Naik, Ashish V.; Regan, Kenneth W.; Sivakumar, D. (1995).

[7] Papadimitriou, Christos H. (1994).

[8] Cobham, Alan (1965).

[9] Grötschel, Martin; László Lovász; Alexander Schrijver (1988).

[10] Schrijver, Alexander (2003).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]