legge di Moore e algoritmo quadratico

Question

legge di Moore e algoritmo quadratico

#1 da (3 voti)
#2 da (2 voti)

0

Stavo passando attraverso un video (da coursera - by sedgewick ) in cui sostiene che you cannot sustain Moore's law using a quadratic algorithm . Elabora in questo modo

Nell'anno 197 * costruisci un computer di potenza X, e devi contare N oggetti. Ciò richiede M giorni

Secondo Moore's law , hai un computer di potenza 2X dopo 1,5 anni. Ora hai 2N oggetti da contare.

Se usi un algoritmo quadratico,

Nell'anno 197 * + 1,5, richiede (4M) / 2 = 2M giorni

4M perché l'algoritmo è quadratico e divisione per 2 a causa del raddoppio della potenza del computer.

Lo trovo difficile da capire. Ho provato a lavorare con questo come sotto

To count N objects using comp=X , it takes M days.
-> N/X = M

After 1.5 yrs ,you need to count 2N objects using comp=2X
-> 2N/(2X) -> N/X -> M days

dove vado storto? qualcuno può per favore aiutarmi a capire?

algorithms

posta damon 19.10.2013 - 13:58

fonte

2 risposte

2

Quando Sedgwick parla di un algoritmo "quadratico", intende uno in cui lo sforzo è non proporzionale alla dimensione dell'input. Ad esempio, se hai dieci lettere nel tuo alfabeto, ci sono 100 possibili parole di due lettere, ma se hai venti lettere, sono 400 possibili parole, non solo 200. In altre parole, l'algoritmo fa qualcosa di più che "fai qualcosa con ogni oggetto "- di solito," fai qualcosa ad ogni combinazione di k oggetti ". Pertanto, se si assume che le dimensioni dell'ingresso crescano proporzionalmente con il tempo e il proprio algoritmo è super-lineare (ad esempio quadratico), allora una semplice crescita della potenza di calcolo in proporzione al tempo non è sufficiente per tenere il passo con la crescita del problema.

Devo notare che questa è una semplificazione eccessiva di entrambi i lati del problema. Non esiste una regola generale in base alla quale le dimensioni dell'input dei problemi del mondo reale aumentano in proporzione al tempo: molto spesso crescerà molto più lentamente o molto più velocemente (sebbene di solito non per molto tempo). E la legge di Moore non è una legge ma solo un'osservazione empirica, e non si trattava di velocità della CPU, ma del numero di componenti a transistor per chip, che ha poco a che fare con essi. In effetti, per un certo periodo di tempo le CPU tradizionali non hanno aumentato le loro velocità di clock come hanno fatto negli anni '90, anche se il conteggio dei transistor continua a salire. Quindi tutto ciò è una visione astratta di alto livello della domanda. In pratica, hai quasi sempre bisogno di guardare più da vicino al tuo problema per decidere se rimarrà possibile o meno.

risposta data 19.10.2013 - 14:19

fonte

Leggi altre domande sui tag algorithms

Qual è uno dei pochi principali cambiamenti da Java 6 a Java 7, JBoss non potrebbe farlo già con Java 5? [duplicare] Perché questa convenzione di sintassi?

score 3 · Accepted Answer

Consenti a T(N) il tempo (in giorni) necessario per eseguire un algoritmo per N oggetti su un computer di "potenza 1", quindi il numero di giorni necessari è il primo

T(N)/X

e secondi

T(2N)/2X

Ora imposta T (N) = N nel tuo primo caso e T (2N) = 4N nel tuo secondo caso, e penso che puoi fare da solo la matematica rimanente.

Onestamente, "contare gli oggetti" non è un buon esempio, perché dà la nozione di un tempo di esecuzione di O (N). Forse hai visto il tuo errore più facilmente se avessi sostituito "contando" con "ordinamento".