Como faço para encontrar o tempo de execução determinada velocidade algoritmo e velocidade do computador?

Question

Atualmente estou trabalhando através de uma atribuição que lida com Big-O e tempos de execução. Eu tenho esta pergunta-me mostrado que parece ser muito fácil, mas eu não tenho certeza se eu estou fazendo isso corretamente. O resto dos problemas têm sido bastante difícil, e eu sinto que estou esquecendo algo aqui.

Primeiro, você tem essas coisas: Algoritmo A, que tem um tempo de execução de 50N ^ 3. Computador A, que tem uma velocidade de 1 milissegundo por operação. Computador B, que tem uma velocidade de 2 milissegundos por operação. Uma instância de tamanho 300.

Eu quero encontrar quanto tempo leva algoritmo A para resolver esta instância no computador A, e quanto tempo leva-lo no computador B.

O que eu quero fazer é sub 300 em para n, então você tem 50 * (300 ^ 2) = 4500000.

Em seguida, multiplique o resultado por 1 para o primeiro computador, e 2 para o segundo computador.

Isto parece estranho para mim, embora, porque ele diz que o "tempo de execução" é 50n ^ 3, não "o número de operações é 50n ^ 3", por isso fico com a sensação de que estou multiplicar tempos em tempos e iria acabar com unidades de milissegundos ao quadrado, o que não parece certo em tudo.

Eu gostaria de saber se estou certo, e se não, o que a pergunta realmente significa.

Answer 1

Não faria sentido se você teve O (n ^ 3), mas você não está usando a notação O grande no seu exemplo. Ou seja, se você tivesse O (n ^ 3) você saberia a complexidade do algoritmo, mas você não sabe o número exato de operações como você disse.

Em vez disso, parece que você é dado o número exato de operações que são tomadas. (Mesmo sei que não é explicitamente indicado). Então, substituindo n faria sentido.

Big O notação descreve como o tamanho da entrada teria efeito o seu tempo de execução ou o uso de memória. Mas com Big O que você não poderia deduzir uma hora exata em execução, mesmo dada a velocidade de cada operação.

Colocar uma explicação de por que a sua resposta parece tão simples (como eu descrevi acima) também seria uma maneira segura. Mas tenho certeza que mesmo sem ele você vai ter as marcas para a questão.

Answer 2

Bem, além da falta de sentido de descobrir quanto tempo alguma coisa vai tomar este caminho na maioria dos computadores modernos, embora possa fazer ter alguns o que significa que em um sistema embarcado, ele parece certo para mim a maneira que você fez isso.

Se o algoritmo precisa 50N ^ 3 operações para concluir alguma coisa, onde n é o número de elementos para processar, em seguida, substituindo 300 para n lhe dará o número de operações a realizar, não uma unidade de tempo.

Assim se multiplicam com o tempo por operação e você terá o tempo necessário.

Parece certo para mim.

Answer 3

As suas 50 * n ^ 3 dados é chamado de "tempo de execução", mas isso é porque o modelo utilizado para avaliações de velocidade assume uma máquina com várias operações básicas, onde cada uma delas leva 1 unidade de tempo.

No seu caso, a execução do algoritmo leva 50 * 500 ^ 3 unidades de tempo. No computador A cada unidade de tempo é de 1 ms, e em 2ms computador B.

Esperamos que este coloca algum sentido para as unidades,
Asaf.