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 5n3 + 3n operações elementares para qualquer n (maior do que algum n0), a complexidade de tempo assintótica é O(n3).
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(Mn) e mn= O(T(n)) para algum M ≥ n > 1 é dito ser um algoritmo de tempo exponencial.
Tabela de tempos de complexidade comuns
[editar | editar código-fonte]A tabela a seguir resume algumas classes de complexidade comumente encontradas. Na tabela, poly(x) = xO(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)2 |
potência fracional | O(nc) 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(n2) | Bubble sort; Insertion sort; Direct convolution |
cúbico | O(n3) | 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(log2 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) | 2o(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 |
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
[editar | editar código-fonte]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
[editar | editar código-fonte]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.
// 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
[editar | editar código-fonte]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
[editar | editar código-fonte]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 b1,...,bk se assume que o algoritmo pode em tempo O(1) obter o valor de bi para qualquer i.
Tempo linear
[editar | editar código-fonte]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
[editar | editar código-fonte]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.[6] 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:
- In-place merge sort, O(n log2 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
[editar | editar código-fonte]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.[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 operações para uma constante A. Assim então rodando em tempo 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
[editar | editar código-fonte]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).