Complexidade de tempo - Time complexity

Gráficos de funções comumente usadas na análise de algoritmos , mostrando o número de operações N versus tamanho de entrada n para cada função

Na ciência da computação , a complexidade do tempo é a complexidade computacional que descreve a quantidade de tempo que o computador leva para executar um algoritmo . A complexidade do tempo é comumente estimada pela contagem do número de operações elementares realizadas pelo algoritmo, supondo que cada operação elementar leve um determinado período de tempo para ser executada. Assim, a quantidade de tempo gasto e o número de operações elementares realizadas pelo algoritmo são considerados relacionados por um fator constante .

Uma vez que o tempo de execução de um algoritmo pode variar entre diferentes entradas do mesmo tamanho, normalmente se considera a complexidade de tempo do pior caso , que é a quantidade máxima de tempo necessária para entradas de um determinado tamanho. Menos comum, e geralmente especificado explicitamente, é a complexidade de caso médio , que é a média do tempo gasto em entradas de um determinado tamanho (isso faz sentido porque há apenas um número finito de entradas possíveis de um determinado tamanho). Em ambos os casos, a complexidade do tempo é geralmente expressa em função do tamanho da entrada. Uma vez que essa função geralmente é difícil de calcular com exatidão e o tempo de execução para pequenas entradas geralmente não é consequente, geralmente se concentra no comportamento da complexidade quando o tamanho da entrada aumenta - ou seja, o comportamento assintótico da complexidade. Por isso, a complexidade de tempo é normalmente expresso usando grande notação S , tipicamente , , , , etc., em que n é o tamanho em unidades de bits de necessários para representar a entrada.

As complexidades algorítmicas são classificadas de acordo com o tipo de função que aparece na notação O grande. Por exemplo, um algoritmo com complexidade de tempo é um algoritmo de tempo linear e um algoritmo com complexidade de tempo para alguma constante é um algoritmo de tempo polinomial .

Tabela de complexidades de tempo comuns

A tabela a seguir resume algumas classes de complexidades de tempo comumente encontradas. Na tabela, poli ( x ) = x O (1) , ou seja, polinômio em  x .

Nome Classe de complexidade Tempo de execução ( T ( n )) Exemplos de tempos de execução Algoritmos de exemplo
tempo constante O (1) 10 Encontrar o valor mediano em uma matriz classificada de números

Calculando (−1) n

tempo de Ackermann inverso O ( α ( n )) Tempo amortizado por operação usando um conjunto disjunto
tempo logarítmico iterado O ( log *  n ) Coloração distribuída de ciclos
log-logarítmico O (log log n ) Tempo amortizado por operação usando uma fila de prioridade limitada
tempo logarítmico DLOGTIME O (log  n ) log  n , log ( n 2 ) Busca binária
tempo polilogarítmico poli (log  n ) (log  n ) 2
potência fracionária O ( n c ) onde 0 < c <1 n 1/2 , n 2/3 Pesquisando em uma árvore kd
tempo linear O ( n ) n , 2 n + 5 Encontrar o menor ou o maior item em uma matriz não classificada , algoritmo de Kadane , pesquisa linear
"n log-star n" tempo O ( n log * n ) Seidel 's polígono triangulação algoritmo.
tempo linearitmico O ( n log n ) n log n , log n ! Classificação de comparação mais rápida possível ; Transformação rápida de Fourier .
tempo quase-linear n poly (log n )
tempo quadrático O ( n 2 ) n 2 Tipo de bolha ; Tipo de inserção ; Convolução direta
tempo cúbico O ( n 3 ) n 3 Multiplicação Naive de dois n × n matrizes. Calculando correlação parcial .
tempo polinomial P 2 O (log n ) = poli ( n ) n 2 + n , n 10 Algoritmo de Karmarkar para programação linear ; Teste de primalidade AKS
tempo quase polinomial QP 2 poli (log  n ) n log log n , n log  n Mais conhecido O (log 2 n ) - algoritmo de aproximação para o dirigido problema árvore Steiner .
tempo subexponencial
(primeira definição)
SUBEXP O (2 n ε ) para todo ε > 0 Contém BPP, a menos que EXPTIME (veja abaixo) seja igual a MA .
tempo subexponencial
(segunda definição)
2 o ( n ) 2 n 1/3 Algoritmo mais conhecido para fatoração de inteiros ; anteriormente o melhor algoritmo para isomorfismo de grafos
tempo exponencial
(com expoente linear)
E 2 O ( n ) 1,1 n , 10 n Resolvendo o problema do caixeiro viajante usando programação dinâmica
tempo exponencial EXPTIME 2 poli ( n ) 2 n , 2 n 2 Resolvendo a multiplicação da cadeia de matriz por meio de pesquisa de força bruta
tempo fatorial O ( n !) n ! Resolvendo o problema do caixeiro viajante por meio de busca de força bruta
tempo exponencial duplo 2-EXPTIME 2 2 poli ( n ) 2 2 n Decidir a verdade de uma determinada declaração na aritmética Presburger

Tempo constante

Um algoritmo é chamado de tempo constante (também escrito como tempo O (1) ) se o valor de T ( n ) for limitado por um valor que não depende do tamanho da entrada. Por exemplo, acessar qualquer elemento único em uma matriz leva um tempo constante, pois apenas uma operação deve ser realizada para localizá-lo. De maneira semelhante, encontrar o valor mínimo em uma matriz classificada em ordem crescente; é o primeiro elemento. No entanto, encontrar o valor mínimo em uma matriz não ordenada não é uma operação de tempo constante, pois a varredura de cada elemento da matriz é necessária para determinar o valor mínimo. Portanto, é uma operação de tempo linear, levando um tempo O ( n ). Se o número de elementos é conhecido com antecedência e não muda, no entanto, esse algoritmo ainda pode ser considerado executado em tempo constante.

Apesar do nome "tempo constante", o tempo de execução não precisa ser independente do tamanho do problema, mas um limite superior para o tempo de execução deve ser limitado independentemente do tamanho do problema. Por exemplo, a tarefa "trocar os valores de um e b se assim for necessário que umb " é chamada constante de tempo, mesmo que o tempo pode depender de se é ou não já é verdade que umb . No entanto, existe alguma constante t tal que o tempo necessário é sempre no máximo t .

Aqui estão alguns exemplos de fragmentos de código executados 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

Se T ( n ) for O ( qualquer valor constante ), isso é equivalente e declarado na notação padrão como T ( n ) sendo O (1).

Tempo logarítmico

Diz-se que um algoritmo leva tempo logarítmico quando T ( n ) = O (log n ) . Uma vez que log a  n e log b  n estão relacionados por um multiplicador constante , e tal multiplicador é irrelevante para a classificação big-O, o uso padrão para algoritmos de tempo logarítmico é O (log n ), independentemente da base do logaritmo que aparece em a expressão do t .

Algoritmos que levam tempo logarítmico são comumente encontrados em operações em árvores binárias ou ao usar a pesquisa binária .

Um algoritmo O (log n ) é considerado altamente eficiente, pois a razão entre o número de operações e o tamanho da entrada diminui e tende a zero quando n aumenta. Um algoritmo que deve acessar todos os elementos de sua entrada não pode levar tempo logarítmico, pois o tempo gasto para ler uma entrada de tamanho n é da ordem de n .

Um exemplo de tempo logarítmico é dado pela pesquisa de dicionário. Considere um dicionário D que contém n entradas, classificadas em ordem alfabética . Supomos que, para 1 ≤ kn , pode-se acessar a k ésima entrada do dicionário em um tempo constante. Deixe D ( k ) denotar esta k ésima entrada. Sob essas hipóteses, o teste para ver se uma palavra w está no dicionário pode ser feito em tempo logarítmico: considere , onde denota a função chão . Se , então estamos prontos. Caso contrário, se , continuar a busca da mesma forma na metade esquerda do dicionário, caso contrário, continue da mesma forma com a metade direita do dicionário. Este algoritmo é semelhante ao método freqüentemente usado para localizar uma entrada em um dicionário de papel.

Tempo polilogarítmico

Diz-se que um algoritmo roda em tempo polilogarítmico se seu tempo T ( n ) for O ((log n ) k ) para alguma constante k . Outra maneira de escrever isso é O (log k n ) .

Por exemplo, a ordenação da cadeia de matriz pode ser resolvida em tempo polilogarítmico em uma máquina de acesso aleatório paralela , e um gráfico pode ser determinado como plano de uma forma totalmente dinâmica em tempo O (log 3 n ) por operação de inserção / exclusão.

Tempo sublinear

Diz-se que um algoritmo roda em tempo sublinear (freqüentemente escrito em tempo sublinear ) se T ( n ) = o ( n ) . Em particular, isso inclui algoritmos com as complexidades de tempo definidas acima.

Algoritmos típicos que são exatos e ainda executados em tempo sublinear usam processamento paralelo (como o cálculo do determinante da matriz NC 1 faz) ou, alternativamente, têm suposições garantidas na estrutura de entrada (como a busca binária de tempo logarítmico e muitos algoritmos de manutenção de árvore fazem) . No entanto, as linguagens formais , como o conjunto de todas as strings que têm 1 bit na posição indicada pelos primeiros log ( n ) bits da string, podem depender de cada bit da entrada e, ainda assim, ser computáveis ​​em tempo sublinear.

O termo específico algoritmo de tempo sublinear é geralmente reservado para algoritmos que são diferentes dos acima, pois são executados em modelos clássicos de máquina serial e não são permitidos pressupostos anteriores na entrada. No entanto, eles podem ser randomizados e, na verdade, devem ser randomizados para todas as tarefas, exceto as mais triviais.

Como tal algoritmo deve fornecer uma resposta sem ler a entrada inteira, suas particularidades dependem muito do acesso permitido à entrada. Normalmente, para uma entrada que é representada como uma string binária b 1 , ..., b k , assume-se que o algoritmo pode, em tempo O (1), solicitar e obter o valor de b i para qualquer i .

Os algoritmos de tempo sublinear são normalmente randomizados e fornecem apenas soluções aproximadas . Na verdade, a propriedade de uma string binária tendo apenas zeros (e nenhum) pode ser facilmente provada como não sendo decidível por um algoritmo de tempo sublinear (não aproximado). Algoritmos de tempo sublinear surgem naturalmente na investigação de testes de propriedades .

Tempo linear

Diz-se que um algoritmo leva tempo linear , ou tempo O ( n ) , se sua complexidade de tempo for O ( n ) . Informalmente, isso significa que o tempo de execução aumenta no máximo linearmente com o tamanho da entrada. Mais precisamente, isso significa que existe uma constante c tal que o tempo de execução é no máximo cn para cada entrada de tamanho n . Por exemplo, um procedimento que soma todos os elementos de uma lista requer um tempo proporcional ao comprimento da lista, se o tempo de adição for constante ou, pelo menos, limitado por uma constante.

O tempo linear é a melhor complexidade de tempo possível em situações em que o algoritmo tem que ler sequencialmente toda a sua entrada. Portanto, muitas pesquisas foram investidas na descoberta de algoritmos que exibem o tempo linear ou, pelo menos, o tempo quase linear. Esta pesquisa inclui métodos de software e hardware. Existem várias tecnologias de hardware que exploram o paralelismo para fornecer isso. Um exemplo é a memória endereçável por conteúdo . Este conceito de tempo linear é usado em algoritmos de correspondência de strings, como o algoritmo de Boyer-Moore e o algoritmo de Ukkonen .

Tempo quasilinear

Diz-se que um algoritmo roda em tempo quase -linear (também conhecido como tempo log-linear ) se T ( n ) = O ( n log k n ) para alguma constante positiva k ; o tempo linear é o caso k = 1 . Usando a notação soft O, esses algoritmos são Õ ( n ). Algoritmos de tempo quasilinear também são O ( n 1+ ε ) para cada constante ε > 0 e , portanto, rodam mais rápido do que qualquer algoritmo de tempo polinomial cujo limite de tempo inclui um termo n c para qualquer c > 1 .

Os algoritmos executados em tempo quase-linear incluem:

Em muitos casos, o n log n tempo de execução é simplesmente o resultado da execução de um Θ (log n operação) n vezes (para a notação, consulte Big O notação § família de notações Bachmann-Landau ). Por exemplo, a classificação de árvore binária cria uma árvore binária inserindo cada elemento da matriz de tamanho n um por um. Como a operação de inserção em uma árvore de busca binária de autobalanceamento leva tempo O (log n ), todo o algoritmo leva tempo O ( n log n ) .

As ordenações por comparação requerem pelo menos Ω ( n log n ) comparações no pior caso porque log ( n !) = Θ ( n log n ) , pela aproximação de Stirling . Também surgem frequentemente da relação de recorrência T ( n ) = 2 T ( n / 2) + O ( n ) .

Tempo subquadrático

Um algoritmo é chamado de tempo subquadrático se T ( n ) = o ( n 2 ) .

Por exemplo, algoritmos de classificação simples e baseados em comparação são quadráticos (por exemplo, classificação por inserção ), mas algoritmos mais avançados podem ser encontrados que são subquadráticos (por exemplo , classificação de shell ). Nenhuma classificação de propósito geral é executada no tempo linear, mas a mudança de quadrática para subquadrática é de grande importância prática.

Tempo polinomial

Diz-se que um algoritmo é de tempo polinomial se seu tempo de execução for limitado por uma expressão polinomial no tamanho da entrada do algoritmo, ou seja, T ( n ) = O ( n k ) para alguma constante positiva k . Problemas para os quais existe um algoritmo de tempo polinomial determinístico pertencem à classe de complexidade P , que é central no campo da teoria da complexidade computacional . A tese de Cobham afirma que o tempo polinomial é sinônimo de "tratável", "viável", "eficiente" ou "rápido".

Alguns exemplos de algoritmos de tempo polinomial:

  • A seleção tipo algoritmo de classificação no n inteiros executa operações para alguma constante A . Portanto, ele é executado no tempo e é 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 feitas em tempo polinomial.
  • As correspondências máximas nos gráficos podem ser encontradas em tempo polinomial.

Tempo polinomial forte e fraco

Em alguns contextos, especialmente em otimização , diferencia-se entre algoritmos de tempo fortemente polinomial e fracamente polinomial . Esses dois conceitos são relevantes apenas se as entradas para os algoritmos consistirem em inteiros.

O tempo fortemente polinomial é definido no modelo aritmético de computação. Neste modelo de computação, as operações aritméticas básicas (adição, subtração, multiplicação, divisão e comparação) levam um passo de unidade de tempo para serem executadas, independentemente dos tamanhos dos operandos. O algoritmo é executado em tempo fortemente polinomial se:

  1. o número de operações no modelo aritmético de computação é limitado por um polinômio no número de inteiros na instância de entrada; e
  2. o espaço usado pelo algoritmo é limitado por um polinômio no tamanho da entrada.

Qualquer algoritmo com essas duas propriedades pode ser convertido em um algoritmo de tempo polinomial, substituindo as operações aritméticas por algoritmos adequados para realizar as operações aritméticas em uma máquina de Turing . Se o segundo dos requisitos acima não for atendido, isso não é mais verdade. Dado o número inteiro (que ocupa espaço proporcional an no modelo da máquina de Turing), é possível calcular com n multiplicações usando quadrados repetidos . No entanto, o espaço usado para representar é proporcional e , portanto, exponencial em vez de polinomial no espaço usado para representar a entrada. Conseqüentemente, não é possível realizar este cálculo em tempo polinomial em uma máquina de Turing, mas é possível computá-lo polinomialmente por muitas operações aritméticas.

Por outro lado, existem algoritmos que são executados em várias etapas da máquina de Turing delimitadas por um polinômio no comprimento da entrada codificada em binário, mas não realizam uma série de operações aritméticas limitadas por um polinômio no número de números de entrada. O algoritmo euclidiano para calcular o maior divisor comum de dois inteiros é um exemplo. Dados dois inteiros e , o algoritmo realiza operações aritméticas em números com no máximo bits. Ao mesmo tempo, o número de operações aritméticas não pode ser limitado pelo número de inteiros na entrada (que é constante neste caso, sempre há apenas dois inteiros na entrada). Devido à última observação, o algoritmo não roda em tempo fortemente polinomial. Seu tempo de execução real, depende das magnitudes de e e não apenas no número de inteiros na entrada.

Um algoritmo executado em tempo polinomial, mas não fortemente polinomial, é executado em tempo fracamente polinomial . Um exemplo bem conhecido de um problema para o qual um algoritmo de tempo polinomial fraco é conhecido, mas não é conhecido por admitir um algoritmo de tempo fortemente polinomial, é a programação linear . O tempo fracamente polinomial não deve ser confundido com o tempo pseudo-polinomial .

Classes de complexidade

O conceito de tempo polinomial leva a várias classes de complexidade na teoria da complexidade computacional. Algumas classes importantes definidas usando o tempo polinomial são as seguintes.

P A classe de complexidade dos problemas de decisão que podem ser resolvidos em uma máquina de Turing determinística em tempo polinomial
NP A classe de complexidade dos problemas de decisão que podem ser resolvidos em uma máquina de Turing não determinística em tempo polinomial
ZPP A classe de complexidade dos problemas de decisão que podem ser resolvidos com erro zero em uma máquina de Turing probabilística em tempo polinomial
RP A classe de complexidade dos problemas de decisão que podem ser resolvidos com erro unilateral em uma máquina de Turing probabilística em tempo polinomial.
BPP A classe de complexidade dos problemas de decisão que podem ser resolvidos com erro bilateral em uma máquina de Turing probabilística em tempo polinomial
BQP A classe de complexidade dos problemas de decisão que podem ser resolvidos com erro bilateral em uma máquina de Turing quântica em tempo polinomial

P é a menor classe de complexidade de tempo em uma máquina determinística que é robusta em termos de mudanças no modelo da máquina. (Por exemplo, uma mudança de uma única fita Máquina de Turing para uma máquina multi-fita pode levar a um aumento de velocidade quadrática, mas qualquer algoritmo que é executado em tempo polinomial sob o mesmo modelo também faz isso no outro.) Qualquer dado abstrato máquina de vontade têm uma classe de complexidade correspondente aos problemas que podem ser resolvidos em tempo polinomial nessa máquina.

Tempo superpolinomial

Diz-se que um algoritmo leva tempo superpolinomial se T ( n ) não for limitado acima por nenhum polinômio. Usando pouca notação ômega , é o tempo ω ( n c ) para todas as constantes c , onde n é o parâmetro de entrada, normalmente o número de bits na entrada.

Por exemplo, um algoritmo executado por 2 n etapas em uma entrada de tamanho n requer tempo superpolinomial (mais especificamente, tempo exponencial).

Um algoritmo que usa recursos exponenciais é claramente superpolinomial, mas alguns algoritmos são superpolinomiais muito fracos. Por exemplo, o teste de primalidade de Adleman – Pomerance – Rumely é executado por tempo n O (log log n ) em entradas de n bits; isso cresce mais rápido do que qualquer polinômio para n grande o suficiente , mas o tamanho de entrada deve se tornar impraticamente grande antes que não possa ser dominado por um polinômio com grau pequeno.

Um algoritmo que requer mentiras tempo superpolynomial fora da classe de complexidade P . A tese de Cobham postula que esses algoritmos são impraticáveis ​​e, em muitos casos, são. Uma vez que o problema P versus NP não está resolvido, não se sabe se os problemas NP-completos requerem tempo superpolinomial.

Tempo quase polinomial

Algoritmos de tempo quase polinomial são algoritmos que funcionam por mais tempo do que o tempo polinomial, mas não tanto a ponto de ser tempo exponencial. O pior caso de tempo de execução de um algoritmo de tempo quase polinomial é para algum fixo . Pois obtemos um algoritmo de tempo polinomial, pois obtemos um algoritmo de tempo sublinear.

Algoritmos de tempo quase polinomial normalmente surgem em reduções de um problema NP-difícil para outro problema. Por exemplo, pode-se pegar uma instância de um problema difícil NP, digamos 3SAT , e convertê-la em uma instância de outro problema B, mas o tamanho da instância se torna . Nesse caso, essa redução não prova que o problema B é NP-difícil; esta redução mostra apenas que não há algoritmo de tempo polinomial para B, a menos que haja um algoritmo de tempo quase polinomial para 3SAT (e, portanto, todos de NP ). Da mesma forma, existem alguns problemas para os quais conhecemos algoritmos de tempo quase polinomial, mas nenhum algoritmo de tempo polinomial é conhecido. Esses problemas surgem em algoritmos de aproximação; um exemplo famoso é o problema da árvore de Steiner direcionado , para o qual existe um algoritmo de aproximação de tempo quase polinomial que atinge um fator de aproximação de ( n sendo o número de vértices), mas mostrar a existência de tal algoritmo de tempo polinomial é um problema aberto.

Outros problemas computacionais com soluções de tempo quase polinomial, mas sem solução de tempo polinomial conhecida, incluem o problema do clique plantado, no qual o objetivo é encontrar um grande clique na união de um clique e um grafo aleatório . Embora quase polinomialmente solucionável, conjecturou-se que o problema do clique plantado não tem solução de tempo polinomial; esta conjectura de clique plantado tem sido usada como uma suposição de dureza computacional para provar a dificuldade de vários outros problemas em teoria de jogos computacionais , teste de propriedade e aprendizado de máquina .

A classe de complexidade QP consiste em todos os problemas que possuem algoritmos de tempo quase polinomial. Ele pode ser definido em termos de DTIME da seguinte forma.

Relação com problemas NP-completos

Na teoria da complexidade, o problema não resolvido P versus NP pergunta se todos os problemas em NP têm algoritmos de tempo polinomial. Todos os algoritmos mais conhecidos para problemas NP-completos como 3SAT etc. levam tempo exponencial. Na verdade, é conjecturado para muitos problemas NP-completos naturais que eles não têm algoritmos de tempo subexponencial. Aqui, "tempo subexponencial" significa a segunda definição apresentada abaixo. (Por outro lado, muitos problemas de grafos representados de forma natural por matrizes de adjacência são solucionáveis ​​em tempo subexponencial simplesmente porque o tamanho da entrada é o quadrado do número de vértices.) Esta conjectura (para o problema k-SAT) é conhecido como a hipótese do tempo exponencial . Uma vez que se conjectura que problemas NP-completos não têm algoritmos de tempo quase polinomiais, alguns resultados de improximabilidade no campo dos algoritmos de aproximação fazem a suposição de que problemas NP-completos não têm algoritmos de tempo quase polinomiais. Por exemplo, consulte os resultados conhecidos de incompatibilidade para o problema de cobertura do conjunto .

Tempo subexponencial

O termo tempo subexponencial é usado para expressar que o tempo de execução de algum algoritmo pode crescer mais rápido do que qualquer polinômio, mas ainda é significativamente menor do que um exponencial. Nesse sentido, problemas que possuem algoritmos de tempo subexponencial são um pouco mais tratáveis ​​do que aqueles que possuem apenas algoritmos exponenciais. A definição precisa de "subexponencial" geralmente não é aceita e listamos as duas mais amplamente utilizadas a seguir.

Primeira definição

Diz-se que um problema é solucionável em tempo subexponencial se puder ser resolvido em tempos de execução cujos logaritmos crescem menores do que qualquer polinômio dado. Mais precisamente, um problema está em tempo subexponencial se para todo ε > 0 existe um algoritmo que resolve o problema no tempo O (2 n ε ). O conjunto de todos esses problemas é a classe de complexidade SUBEXP, que pode ser definida em termos de DTIME como segue.

Esta noção de subexponencial não é uniforme em termos de ε no sentido de que ε não faz parte da entrada e cada ε pode ter seu próprio algoritmo para o problema.

Segunda definição

Alguns autores definem o tempo subexponencial como tempos de execução em 2 o ( n ) . Esta definição permite tempos de execução maiores do que a primeira definição de tempo subexponencial. Um exemplo de tal algoritmo de tempo subexponencial é o algoritmo clássico mais conhecido para fatoração de inteiros, a peneira de campo de número geral , que funciona no tempo , em que o comprimento da entrada é n . Outro exemplo foi o problema de isomorfismo de grafos , que o algoritmo mais conhecido de 1982 a 2016 resolveu . No entanto, no STOC 2016, um algoritmo de tempo quase polinomial foi apresentado.

Faz diferença se o algoritmo pode ser subexponencial no tamanho da instância, no número de vértices ou no número de arestas. Na complexidade parametrizada , essa diferença é explicitada considerando pares de problemas de decisão e parâmetros k . SUBEPT é a classe de todos os problemas parametrizados que são executados em tempo subexponencial em k e polinomial no tamanho de entrada n :

Mais precisamente, SUBEPT é a classe de todos os problemas parametrizados para os quais existe uma função computável com e um algoritmo que decide L no tempo .

Hipótese de tempo exponencial

A hipótese de tempo exponencial ( ETH ) é que 3SAT , o problema de satisfatibilidade das fórmulas booleanas na forma normal conjuntiva com, no máximo, três literais por cláusula e com n variáveis, não pode ser resolvido no tempo 2 o ( n ) . Mais precisamente, a hipótese é que existe alguma constante absoluta c > 0 tal que 3SAT não pode ser decidido no tempo 2 cn por nenhuma máquina de Turing determinística. Com m denotando o número de cláusulas, ETH é equivalente à hipótese de que k SAT não pode ser resolvido no tempo 2 o ( m ) para qualquer inteiro k ≥ 3 . A hipótese do tempo exponencial implica P ≠ NP .

Tempo exponencial

Diz-se que um algoritmo é de tempo exponencial , se T ( n ) for limitado por 2 poli ( n ) , onde poli ( n ) é algum polinômio em n . Mais formalmente, um algoritmo é de tempo exponencial se T ( n ) é limitado por O (2 n k ) para alguma constante k . Problemas que admitem algoritmos de tempo exponencial em uma máquina de Turing determinística formam a classe de complexidade conhecida como EXP .

Às vezes, o tempo exponencial é usado para se referir a algoritmos que têm T ( n ) = 2 O ( n ) , onde o expoente é no máximo uma função linear de n . Isto dá origem à classe de complexidade E .

Tempo fatorial

Um exemplo de algoritmo executado em tempo fatorial é o bogosort , um algoritmo de classificação notoriamente ineficiente baseado em tentativa e erro . Bogosort classifica uma lista de n itens misturando repetidamente a lista até que seja encontrada para ser classificada. No caso médio, cada passagem pelo algoritmo bogosort examinará um dos n ! pedidos dos n itens. Se os itens forem distintos, apenas uma dessas ordens será classificada. Bogosort compartilha patrimônio com o teorema do macaco infinito .

Tempo exponencial duplo

Diz-se que um algoritmo é de tempo exponencial duplo se T ( n ) for limitado por 2 2 poli ( n ) , onde poli ( n ) é algum polinômio em n . Esses algoritmos pertencem à classe de complexidade 2-EXPTIME .

Algoritmos de tempo exponencial duplo bem conhecidos incluem:

Veja também

Referências