Contexto de complexidade computacional - Context of computational complexity
Na teoria da complexidade computacional e na análise de algoritmos , várias métricas são definidas para descrever os recursos, como tempo ou espaço, de que uma máquina precisa para resolver um problema específico. Interpretar essas métricas de forma significativa requer contexto, e esse contexto está frequentemente implícito e depende do campo e do problema em consideração. Este artigo descreve várias partes importantes do contexto e como elas afetam as métricas.
Definições de variáveis
As métricas são geralmente descritas em termos de variáveis que são uma função da entrada. Por exemplo, a declaração de que a classificação por inserção requer comparações O ( n 2 ) não tem sentido sem definir n , que neste caso é o número de elementos na lista de entrada.
Como muitos contextos diferentes usam as mesmas letras para suas variáveis, pode surgir confusão. Por exemplo, a complexidade dos testes de primalidade e algoritmos de multiplicação pode ser medida de duas maneiras diferentes: uma em termos dos inteiros sendo testados ou multiplicados, e uma em termos do número de dígitos binários (bits) nesses inteiros. Por exemplo, se n é o inteiro sendo testado para primalidade, a divisão experimental pode testá-lo em Θ (n 1/2 ) operações aritméticas; mas se n for o número de bits no inteiro sendo testado para primalidade, ele requer Θ (2 n / 2 ) tempo. Nos campos da criptografia e teoria computacional dos números , é mais comum definir a variável como o número de bits nos inteiros de entrada.
No campo da teoria da complexidade computacional , a entrada é geralmente especificada como uma string binária (ou uma string em algum alfabeto fixo), e a variável é geralmente o número de bits nessa string. Essa medida depende da codificação específica da entrada, que deve ser especificada. Por exemplo, se a entrada for um inteiro especificado usando codificação unária , a divisão experimental exigirá apenas Θ (n 1/2 ) operações aritméticas; mas se a mesma entrada for especificada em binário (ou qualquer base maior), a complexidade aumenta para Θ (2 n / 2 ) operações, não porque o algoritmo está levando algum tempo adicional, mas porque o número de bits na entrada n tornou-se exponencialmente menor. Na outra direção, circuitos sucintos são representações compactas de uma classe limitada de grafos que ocupam exponencialmente menos espaço do que representações comuns como listas de adjacência. Muitos algoritmos de gráfico em circuitos sucintos são EXPTIME-completos , enquanto os mesmos problemas expressos com representações convencionais são apenas P-completos , porque as entradas do circuito sucinto têm codificações menores.
Os algoritmos sensíveis à saída definem sua complexidade não apenas em termos de entrada, mas também de saída. Por exemplo, o algoritmo de Chan pode calcular o casco convexo de um conjunto de pontos no tempo O ( n log h ), onde n é o número de pontos na entrada eh é o número de pontos no casco convexo resultante, um subconjunto de os pontos de entrada. Como cada ponto de entrada pode estar no casco convexo, uma análise em termos da entrada sozinha produziria o tempo O ( n log n ) menos preciso .
A complexidade de alguns algoritmos depende não apenas dos parâmetros da entrada, mas também dos parâmetros da máquina em que o algoritmo está sendo executado; conforme mencionado em #Metric sendo medido abaixo, isso é típico na análise de algoritmos que são executados em sistemas com hierarquias de cache fixas, onde a complexidade pode depender de parâmetros como tamanho do cache e tamanho do bloco.
Maquina abstrata
Para analisar um algoritmo com precisão, deve-se supor que ele está sendo executado por uma máquina abstrata específica . Por exemplo, em uma máquina de acesso aleatório , a pesquisa binária pode ser usada para localizar rapidamente um determinado valor em uma lista classificada em apenas O (log n ) comparações, onde n é o número de elementos na lista; em uma máquina de Turing , isso não é possível, uma vez que ela só pode mover uma célula de memória por vez e, portanto, requer Ω ( n ) etapas para chegar a um valor arbitrário na lista.
Além disso, diferentes máquinas abstratas definem diferentes operações primitivas , que são operações que podem ser realizadas em tempo constante. Algumas máquinas, como as máquinas de Turing, permitem que apenas um bit de cada vez seja lido ou escrito; elas são chamadas de operações de bits, e o número de operações de bits necessárias para resolver um problema é chamado de complexidade de bits . A complexidade de bits se generaliza para qualquer máquina onde as células de memória são de um tamanho fixo que não depende da entrada; por esse motivo, algoritmos que manipulam números muito maiores do que os registros em PCs comuns são normalmente analisados em termos de sua complexidade de bits. Dito de outra forma, a complexidade do bit é a complexidade quando o tamanho da palavra é um único bit, onde o tamanho da palavra é o tamanho de cada célula de memória e registro.
Outro modelo comumente usado tem palavras com log n bits, onde n é uma variável dependendo da entrada. Por exemplo, em algoritmos de gráfico , é típico supor que os vértices são numerados de 1 a n e que cada célula de memória pode conter qualquer um desses valores, de modo que eles podem se referir a qualquer vértice. Isso se justifica em problemas em que a entrada usa Ω ( n ) palavras de armazenamento, uma vez que em computadores reais, a célula de memória e o tamanho do registro são tipicamente selecionados para poder indexar qualquer palavra na memória. As operações com essas palavras, como cópias e operações aritméticas, são consideradas como operando em tempo constante, em vez de tempo O (log n ). O número de operações de palavras necessárias para resolver um problema neste modelo às vezes é chamado de complexidade de palavras .
Na teoria da complexidade computacional , os pesquisadores definem intencionalmente as classes de complexidade de uma forma destinada a torná-las independentes da máquina - isto é, se um problema reside em uma classe particular em relação a uma máquina "razoável" particular, estará nessa classe em relação a qualquer máquina "razoável". Por exemplo, como mencionado acima, a complexidade de tempo da pesquisa binária depende se uma máquina de Turing ou uma máquina de acesso aleatório é usada; mas independentemente da escolha da máquina, está em P , a classe dos algoritmos de tempo polinomial. Em geral, P é considerada uma classe independente de máquina porque qualquer operação que pode ser simulada em tempo polinomial pode ser assumida como exigindo um tempo constante, uma vez que pode ser tratada como uma sub-rotina sem exceder o limite de tempo polinomial.
As máquinas Oracle são máquinas que possuem uma operação específica que podem realizar em tempo constante; esta operação pode ser arbitrariamente complexa e pode afetar dramaticamente a complexidade dos algoritmos executados na máquina. Por exemplo, se alguém tem um oráculo para resolver qualquer problema NP-completo , então qualquer problema em NP pode ser resolvido em tempo polinomial (enquanto sem o oráculo, nenhum algoritmo de tempo polinomial é conhecido para muitos desses problemas). As máquinas Oracle são impraticáveis de construir, mas úteis na teoria para determinar quais técnicas de prova serão eficazes.
Métrica sendo medida
É comum dizer sem qualificação que a classificação por inserção requer tempo O ( n 2 ); no entanto, não faz sentido dizer que a complexidade de bits da classificação por inserção é O ( n 2 ), a menos que os elementos sendo classificados sejam de tamanho constante. Se os elementos forem assumidos como inteiros entre 1 e n , então a complexidade da palavra onde as palavras têm log n bits seria O ( n 2 ), mas é preferível ter um modelo que permita a classificação de listas diferentes de listas de pequenos inteiros, como listas de strings. Nesse caso, em vez de medir o número de etapas de tempo que a máquina abstrata executa, é preferível definir uma métrica específica apropriada para o problema em questão. Para algoritmos de classificação de comparação , que examinam a entrada usando apenas comparações e a modificam usando apenas trocas (trocas), a métrica típica é o número de comparações de elementos realizadas, o número de trocas de elementos realizadas ou a soma deles. Diferentes algoritmos de classificação de comparação podem ser comparados usando essas métricas, mas para comparação útil com algoritmos de classificação de não comparação, como classificação de raiz , uma métrica diferente deve ser usada e o conjunto de elementos deve ser restrito.
Como as operações do disco são ordens de magnitude mais lentas do que os acessos à memória principal, a métrica típica usada em algoritmos baseados em disco é o número de buscas no disco ou o número de blocos lidos do disco, que dependem tanto da entrada quanto dos parâmetros do disco. Os acessos à RAM e as operações da CPU são "gratuitos". Da mesma forma, em muitos modelos usados para estudar estruturas de dados, como o modelo esquecido de cache , as operações em dados em cache são consideradas "livres" porque são normalmente ordens de magnitude mais rápidas na prática do que o acesso à memória principal. Conseqüentemente, a métrica típica usada é o número de perdas de cache, que depende da entrada e dos parâmetros do cache.