Tempo di esecuzione di un algoritmo su un computer più veloce?

Question

Tempo di esecuzione di un algoritmo su un computer più veloce?

#1 da (2 voti)

-1

Un algoritmo impiega 1 secondo per eseguire un set di dati di dimensione N su un particolare computer. Sostituiscilo con un computer 10 volte più veloce. Quale sarà la dimensione del set di dati che è possibile elaborare in 1 secondo sul nuovo computer se il tempo di esecuzione per un set di dati di dimensione n è proporzionale a n ^ 2?

Sto attraversando un periodo difficile a risolvere questa domanda. Penso che se la macchina è 10 volte più veloce, dovrebbe essere in grado di eseguire 10 volte la quantità di dati. Ciò significa che potrebbe fare un set di dati di dimensioni 10N. Ma non sarebbe questo solo se il tempo di esecuzione fosse proporzionale a n? Se il tempo di esecuzione aumenta in modo quadratico man mano che l'input aumenta, il dataset non deve essere inferiore a 10 N?

complexity

posta JaredL 21.09.2018 - 17:01

fonte

1 risposta

Leggi altre domande sui tag complexity

Esiste qualcosa come un'entità interna in DFD? Come utilizzare le richieste pull per le revisioni del codice con un repository remoto condiviso?

score 2 · Accepted Answer

La complessità theta-O può essere pensata come quante operazioni discrete devono essere eseguite per raggiungere lo stato finale. Quindi, se ha complessità O (n ^ 2), esegue al massimo n ^ 2 operazioni. La complessità non ha nulla a che fare con la velocità stessa del computer. In realtà è solo vagamente correlato alla velocità di calcolo. Significa solo quanto lavoro deve fare il computer per raggiungere il risultato.

La velocità di un computer ha a che fare con quante operazioni discrete è possibile eseguire al secondo. Dal momento che vuoi sapere che cosa sceglieresti per eseguire 10 operazioni discrete, prova a chiedere, "quale N aumenterebbe il numero complessivo di operazioni per 10?" la risposta sarebbe la radice quadrata di 10.