problema de explicação do tempo de execução para loop único

8

Estou analisando alguns tempos de execução de diferentes for-loops e, à medida que estou adquirindo mais conhecimento, estou curioso para entender esse problema que ainda tenho que descobrir. Eu tenho este exercício chamado "Quantas estrelas são impressas":

for (int i = N; i > 1; i = i/2) System.out.println("*");

As respostas para escolher são A: ~log N B: ~N C: ~N log N D: ~0.5N^2

Então a resposta deve ser A e eu concordo com isso, mas do outro lado ... Digamos o N = 500que seria Log Nentão? Seria 2,7. E daí se dissermos isso N=500em nosso exercício acima? Definitivamente, isso imprimiria mais han 2.7 estrelas? Como isso está relacionado?

Porque faz sentido dizer que, se o loop for fosse assim:

for (int i = 0; i < N; i++)

imprimiria Nestrelas.

Espero encontrar uma explicação para isso aqui, talvez eu esteja interpretando todas essas coisas erradas e pensando mal sobre isso. Desde já, obrigado.

algorithms complexity big-o runtime owwyess
fonte
como isso é diferente da sua pergunta anterior? Tempo de execução assintótica de para-ciclos
mosquito
Isso não tem nada a ver com tempos de execução assintóticos.
Owwess
1
Essa opção só faz sentido se o logaritmo de base 2 for utilizado, não o logaritmo de base 10.
precisa saber é o seguinte
3
Qual base você está assumindo para obter o Log 500 = 2,7? e essa base aparece em algum lugar do seu código? Nb você está sempre apenas um diferente constante fator com registros de bases diferentes
Caleth
2
@Caleth o logaritmo de base não aparecem no código: i = i/2a base é dois, porque o ciclo é repetido invertendo multiplicação por dois.

Respostas:

34

Você ignorou as principais características da base do logaritmo .

Como ié dividido por 2 em cada iteração, o tempo de execução é logarítmico com a base 2. E

log 2 (500) ~ 8,9

O que você está olhando é

log 10 (500) ~ 2,7

(logaritmo com base 10)

A propósito, a razão pela qual a base é frequentemente omitida nas discussões em tempo de execução (e sua calculadora provavelmente não possui um botão para o log 2 ) é que, devido aos mecanismos da matemática logarítmica, uma base diferente corresponde a um fator constante e, portanto, não é relevante quando você está ignorando fatores constantes de qualquer maneira. Pode ser calculado facilmente:

log a (x) = log b (x) / log b (a)

Michael Borgwardt
fonte
Isso faz todo o sentido, então, na verdade, é apenas minha falta de conhecimento sobre logaritmos. Obrigado pela resposta simples e clara.
owwyess
Obrigado @Michael Borgwardt. Qualquer chance de você dar o exemplo acima com N = 500. Como posso calcular isso em uma calculadora com apenas a base de log 10?
Owwess
2
@owwyess você dividir o resultado log10 por log 10 (2)
catraca aberração
Desculpe, eu tinha me confundido e dividido com log10 (10). Obrigado a todos.
Owwess
2
O fator constante mencionado no último parágrafo é de aproximadamente 3.322 para a base 2. Ou seja, você precisa de ~ 3,3 dígitos do binário para um dígito decimal. Ou, se preferir, um binário de 33 dígitos tem ~ 10 dígitos em decimal.
Captain Giraffe
8

Além da resposta de Michael Borgwardt , o caractere til antes de cada resposta deve ser lido como "proporcional a". Portanto, se você dobrar N (digamos, de 500 para 1000), verá que o tempo de execução (ou, neste caso, o número de estrelas impressas) aumentaria por um fator que seria igual a (log1000 / log 500), que é independente de qual base você usa.

Boluc Papuccuoglu
fonte
2
Eu sempre entendi que til significa aproximado, não proporcional. Essencialmente, ~é uma abreviação de ≅.
Davor Ždralo
1
Proporcional a é o ∝símbolo não ~! A ~é usado para indicar relações de equivalência ou aproximados igualdades (consulte a página da Wikipedia sobre til ).
Bakuriu 19/08/14