Come posso trovare il tempo di esecuzione dato la velocità dell'algoritmo e la velocità del computer?

Question

Attualmente sto lavorando a un incarico che si occupa di Big-O e tempi di esecuzione. Mi viene presentata questa domanda che sembra molto semplice, ma non sono sicuro che lo stia facendo correttamente. Il resto dei problemi è stato piuttosto difficile e mi sembra di trascurare qualcosa qui.

Innanzitutto, hai queste cose: Algoritmo A, che ha un tempo di esecuzione di 50n ^ 3. Computer A, che ha una velocità di 1 millisecondo per operazione. Computer B, che ha una velocità di 2 millisecondi per operazione. Un'istanza di dimensioni 300.

Voglio scoprire quanto tempo impiega l'algoritmo A per risolvere questa istanza sul computer A e quanto tempo impiega sul computer B.

Quello che voglio fare è sub 300 in per n, quindi hai 50 * (300 ^ 2) = 4500000.

Quindi, moltiplicalo per 1 per il primo computer e per 2 per il secondo computer.

Questo mi sembra strano, perché dice il "tempo di esecuzione". è 50n ^ 3, no, "il numero di operazioni è 50n ^ 3", quindi ho la sensazione che sto moltiplicando di volta in volta, e finirei con unità di millisecondi al quadrato, che non sembra proprio tutti.

Vorrei sapere se ho ragione e, in caso contrario, cosa significa effettivamente la domanda.

Answer 1

Non avrebbe senso se tu avessi O (n ^ 3) ma non stai usando una grande notazione O nel tuo esempio. Cioè se avessi O (n ^ 3) conosceresti la complessità del tuo algoritmo ma non conosceresti il ??numero esatto di operazioni come hai detto.

Invece sembra che ti venga dato il numero esatto di operazioni che vengono eseguite. (Anche sapere che non è esplicitamente dichiarato). Quindi sostituire n avrebbe senso.

La notazione O grande descrive come la dimensione dell'input influirebbe sul tempo di esecuzione o sull'utilizzo della memoria. Ma con Big O non è stato possibile dedurre un tempo di esecuzione esatto anche data la velocità di ciascuna operazione.

Fornire una spiegazione del perché la tua risposta sembra così semplice (come ho descritto sopra) sarebbe anche un modo sicuro. Ma sono sicuro che anche senza di essa otterrai i voti per la domanda.

Answer 2

Beh, a parte l'inutilità di capire quanto tempo impiegherà questo modo sulla maggior parte dei computer moderni, anche se potrebbe avere un po ' in un sistema incorporato, mi sembra giusto il come l'hai fatto.

Se l'algoritmo richiede 50n ^ 3 operazioni per completare qualcosa, dove n è il numero di elementi da elaborare, la sostituzione di 300 con n ti darà il numero di operazioni da eseguire, non un'unità di tempo.

Quindi moltiplica il tempo per operazione e otterrai il tempo necessario.

Mi sembra giusto.

Answer 3

I tuoi dati 50 * n ^ 3 sono chiamati "tempo di esecuzione", ma questo perché il modello utilizzato per le valutazioni della velocità presuppone una macchina con diverse operazioni di base, in cui ciascuna di queste richiede 1 unità di tempo.

In questo caso, l'esecuzione dell'algoritmo richiede 50 * 500 ^ 3 unità di tempo. Sul computer A ogni unità di tempo è 1 ms e sul computer B 2 ms.

Spero che questo abbia un senso nelle unità,
Asaf.