Complexidade de tempo
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).
Imagem: Força Aérea Brasileira - Página Oficial · BY-NC-SA · Openverse
A tabela a seguir resume algumas classes de complexidade de tempo comumente usadas. Na tabela, poly(x) = x0(1), isto é, polinomial em X.
Imagem: Senado Federal · BY · Openverse
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.
Imagem: Senado Federal · BY · Openverse
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
Imagem: Senado Federal · BY · Openverse
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.
Imagem: Senado Federal · BY · Openverse
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.
Imagem: Senado Federal · BY · Openverse
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.
Imagem: Senado Federal · BY · Openverse
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.
Imagem: Senado Federal · BY · Openverse
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.
Imagem: Senado Federal · BY · Openverse
Um algoritmo é dito ser de tempo polinomial se o tempo de execução dele é limitado superiormente por uma expressão polinomial do tamanho da entrada para o algoritmo, T(n) = O(nk) para algumas constantes k. Problemas para algoritmos de tempo polinomial existem pertencendo a classe de complexidade P, que é central no campo da teoria da complexidade computacional. A tese de Bobham afirma que tempo polinomial é um sinônimo para "dócil", "viável", "eficiente", ou "veloz". Alguns exemplos de algoritmos de tempo polinomial:
Tempo forte e fracamente polinomial
Em alguns contextos, especialmente em otimização, existe uma diferença entre o tempo fortemente polinomial e algoritmos de tempo fracamente polinomial. Estes dois conceitos são relevantes apenas se as entradas para os algoritmos consistem de inteiros. Tempo fortemente polinomial é definido no modelo aritmético de computação. Neste modelo de cálculo as operações aritméticas básicas (adição, subtração, multiplicação, divisão e comparação) dão um passo na unidade de tempo para realizar, independentemente do tamanho dos operandos. O algoritmo é executado em tempo fortemente polinomial se Qualquer algoritmo com essas duas propriedades podem ser convertidos para 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 do requisito acima não for satisfeito, então este não é mais verdadeiro. Dado o inteiro 2n (que ocupa um espaço proporcional ao n), é possível calcular com n multiplicações usando quadratura repetida. No entanto, o espaço usado para representar é proporcional a 2n, e, assim, exponencial ao invés de polinomial no espaço usado para representar a entrada. Por isso, não é possível realizar este cálculo em tempo polinomial em uma máquina de Turing, mas é possível calcular que pelas muitas operações aritméticas polinomialmente.
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 tempo polinomial são as seguintes: P é o 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 máquina de Turing única fita para uma máquina multi-fita pode levar a um aumento de velocidade quadrática, mas qualquer algoritmo que é executado em tempo polinomial em um modelo também faz isso no outro.) Qualquer máquina abstrata terá uma classe de complexidade correspondente aos problemas que podem ser resolvidos em tempo polinomial em sua máquina.
Imagem: Senado Federal · BY · Openverse
Um algoritmo é dito que utiliza tempo superpolinomial se T(n) não limitante superiormente por nenhum polinômio. Ele utiliza tempo ω(nc) para todas as constantes c, onde n é o parâmetro de entrada, tipicamente o número de bits da entrada. Por exemplo, um algoritmo que tida por ( ... ) passos em uma entrada de tamanho n requere tempo superpolinomial (mais especificamente, tempo exponencial). Um algoritmo que usa recursos exponenciais é claramente superpolinomial, mas alguns algoritmos são só fracamente superpolinomiais. Por exemplo, o teste de primalidade de Adleman-Pomerance-Rumely roda em tempo nO(log log n) em entrda de n bits; isto cresce mais rápido que qualquer outro polinômio com n grande o suficiente, mas o tamanho da entrada deve se tornar impraticavelmente grande antes de não ser dominado por um polinômio de grau pequeno. Um algoritmo que fora provado que requere tempo superpolinomial não pode ser resolvido em tempo polinomial, e logo é conhecido como estando fora da classe de complexidade P. A tese de Cobham conjectura que estes algoritmos são impraticáveis e, em muitos casos, eles são. Visto que o problema P versus NP não fora resolvido, nenhum algoritmo de um problema NP-Completo é conhecido atualmente para rodar em tempo polinomial.
