análise de tempo do algoritmo "tamanho da entrada" vs "elementos de entrada"

Ainda estou um pouco confuso com os termos "comprimento da entrada" e "tamanho da entrada" quando usado para analisar e descrever o limite superior assintomático de um algoritmo

Parece que o tamanho da entrada do algoritmo depende muito do tipo de dados e do algoritmo de que você está falando.

Alguns autores referem-se ao tamanho da entrada para o tamanho dos caracteres necessários para representar a entrada; portanto, "abcde" se usado como conjunto de entrada em um algoritmo terá um "comprimento de entrada" de 6 caracteres.

Se em vez de caracteres tivermos número (números inteiros, por exemplo), às vezes a representação binária é usada em vez de caracteres, para que o "comprimento da entrada" seja calculado como (Sendo L o número máximo no conjunto de entrada) . $N*log(L)$

Existem outros problemas que mesmo se o conjunto de entrada são números, eles descrevem o "comprimento de entrada" como "variáveis de decisão", portanto, para um conjunto de entrada de comprimento N com números na faixa de o comprimento de entrada é apenas N ( soma de subconjuntos, por exemplo), ou ainda mais complicado, o número de valores binários de lugares necessários para declarar o problema (o que acredito ser exatamente o mesmo que ) $0-2^{32}$ $N*log(L)$

Então:

depende do algoritmo?
O que significa e quando usar cada tamanho de entrada "versão"
Existe alguma regra que eu possa usar para decidir qual usar?

complexity-theory terminology algorithm-analysis time-complexity runtime-analysis Jesus Salas
fonte

No sentido mais formal, o tamanho da entrada é medido em referência a uma implementação do algoritmo da Turing Machine e é o número de símbolos do alfabeto necessários para codificar a entrada.

Naturalmente, isso é bastante abstrato e é muito difícil trabalhar na prática, ou pelo menos muito irritante - precisaríamos considerar como especificar os delímetros, etc. etc. O que acontece normalmente na prática é que procuramos uma medição proxy do tamanho da entrada - algo mais conveniente e acessível, mas que não causa problemas matemáticos em nossa análise.

Usando o exemplo "abcde", normalmente o alfabeto que usamos para a entrada é pequeno; portanto, mesmo usando a medição de proxy de caracteres, sabíamos que, mesmo em uma máquina de Turing, podemos, se nos incomodarmos, especifique uma codificação de entrada que converteria "abcde" para alguma forma codificada que tivesse comprimento no máximo para alguma constante . Essa expansão por uma constante normalmente não faria diferença em nossa análise assintótica, pois descartamos rotineiramente fatores constantes. $5$ $5\times c$ $c$

Em um caso diferente, geralmente medimos o tamanho de um gráfico de entrada pelo número de vértices . Claramente, se queremos especificar gráficos arbitrariamente grandes, o tamanho da entrada codificada não é simplesmente - o que aconteceu com as bordas, por exemplo? O que sabemos é que podemos usar um esquema de codificação razoável que representa o gráfico em bits. Isso é um pouco mais de expansão do que constante, mas em muitos casos interessantes, estamos lidando apenas com granularidade de polinômios, e os polinômios se compõem muito bem de várias maneiras - em particular, por exemplo, se determinamos que nosso tempo de execução é $n$ $n$ $N = c\cdot n^{2}\log n$ onde é um polinômio, sabemos que existe algum polinômio tal que , portanto, quando voltamos à medida formal da entrada , ainda estamos no tempo polinomial. $O(p(n))$ $p$ $p'$ $O(p(n)) = O(p'(N))$

Um lugar onde isso pode cair é quando você está trabalhando com números. Como um número com magnitude pode ser codificado em bits, se nosso tempo de execução fosse , seria - exponencial no tamanho real da entrada - o que tornaria a magnitude uma má escolha para um proxy para o tamanho da entrada, se quisermos falar sobre a participação em por exemplo (quando você chega a Fortemente- completo e Fraco- $m$ $n = O(\log m)$ $O(m)$ $O(2^{n})$ $m$ $\mathcal{P}$ $\mathcal{NP}$ $\mathcal{NP}$ -complete, lembre-se disso). Por outro lado, se tudo o que nos interessava fosse a decidibilidade, seria uma medida de proxy suficientemente boa.

Portanto, embora não exista uma regra declarada para escolher uma medida de proxy para o tamanho da entrada, o requisito é que a expansão ou contração do tamanho do proxy em comparação com o tamanho da entrada seja compatível com o que você está tentando provar. Como regra geral, mudanças constantes de fator quase nunca importam, fatores polinomiais pequenos normalmente são bons e funcionam na maior parte da teoria básica que você vê, grandes fatores polinomiais ainda podem funcionar na teoria, mas podem ser uma surpresa desagradável na prática, e quantidades exponenciais de mudança são normalmente muito extremas.

Luke Mathieson
fonte

Obrigado pela resposta. Realmente interessante a parte em que você fala sobre a seleção do proxy certo para falar sobre a participação em P ou NP para a entrada, pode ser uma nova pergunta completa! Além disso, e voltando à pergunta anterior. Na sua opinião, qual deles seria o melhor proxy para um algoritmo cuja entrada é um conjunto de números inteiros? Eu acho que talvez vai depender do algoritmo? Eu vejo três opções possíveis: N (sendo o comprimento do conjunto) N * Log (L) (L sendo o valor máximo) e Log (Sum (conjunto)).

Jesus Salas

@JesusSalas, definitivamente pode depender do que você faz com eles, mas

seria a resposta mais simples "perto o suficiente da codificação TM", mas ainda pode ser interessante observar o tempo de execução em termos de

ou talvez

e a magnitude do maior número - é claro que isso é apenas

, mas às vezes pode ser mais fácil analisar as coisas com medidas não óbvias.

N \log L

$N\log L$

N

$N$

N

$N$

2^{\log L}

$2^{\log L}$

Luke Mathieson

Isso cobre as bases, mas existem algumas imprecisões. Representar "abcde" em uma máquina de Turing não ocupa

caracteres

: são necessários cinco caracteres se você escolher o alfabeto certo. E você não precisa de

bits para representar um gráfico

vertex: a matriz de adjacência é exatamente

bits.

5 c

$5c$

c n^{2} \log n

$cn^2\log n$

n

$n$

n^{2}

$n^2$

David Richerby

Talvez quando usar N ou N log L possa depender do custo para o algoritmo operar em cada elemento de entrada. Eu acho que se tivermos uma suposição de que o algoritmo usa tempo constante para fazer seu trabalho em cada elemento de entrada independentemente do seu tamanho em bits (e isso não é abusado), então N é provavelmente o correto, resultando em O (N) . Por outro lado, se o tamanho do elemento de entrada em bits aumentar o custo de operação, então N log L parecerá mais preciso, pois deveríamos expressar no limite superior quais propriedades da entrada estão envolvidas no crescimento

Jesus Salas

5

$5$

c = 1

$c=1$

c = \log_{2} 5

$c = \log_{2}5$

5

$5$

O (n^{2} \log n)

$O(n^{2}\log n)$ bits, mas é um limite superior bastante robusto que pode lidar com ambas as codificações normais.

Luke Mathieson

análise de tempo do algoritmo "tamanho da entrada" vs "elementos de entrada"

Respostas: