Algoritmi di ordinamento
Salve ragazzi avrei dei problemi a capire i tempi logaritmici e non.
Mi aiutate a risolvere l'esercizio seguente, così magari mi chiarisco le idee:
Una azienda informatica ha appena annunciato la sua nuova rivoluzionaria CPU che è in grado ,tra le altre cose , di ordinare 7 elementi con 10 confronti. Compreresti il nuovo PC che usa processori di questo tipo? Giustifica in dettaglio la tua risposta.
Avrei anche un'altra domanda, mi sorge un dubbio,ho come un lapsus:
ma per quanto riguarda il tempo impiegato da algoritmi logaritmici che è O(nlogn) per esempio con il MergeSort, il logaritmo fa crescere n ,oppure lo abbassa?
Mi aiutate a risolvere l'esercizio seguente, così magari mi chiarisco le idee:
Una azienda informatica ha appena annunciato la sua nuova rivoluzionaria CPU che è in grado ,tra le altre cose , di ordinare 7 elementi con 10 confronti. Compreresti il nuovo PC che usa processori di questo tipo? Giustifica in dettaglio la tua risposta.
Avrei anche un'altra domanda, mi sorge un dubbio,ho come un lapsus:
ma per quanto riguarda il tempo impiegato da algoritmi logaritmici che è O(nlogn) per esempio con il MergeSort, il logaritmo fa crescere n ,oppure lo abbassa?
Risposte
mmm...ora non ricordo benissimo perchè gli algoritmi di ordinamento li ho fatti al primo modulo di algoritmi un paio di anni fà...cmq qual'è la complessità migliore per un algoritmo di ordinamento? Se il merge sort è un algoritmo ottimo per il problema dell'ordinamento ed ha complessità O(n*log(n)) mi verrebbe da pensare che:
7 elementi in 10 confronti
n=7
7*log(7) = 10 ? Se si allora risponderei che lo comprerei....ma booo prendilo con le pinze
7 elementi in 10 confronti
n=7
7*log(7) = 10 ? Se si allora risponderei che lo comprerei....ma booo prendilo con le pinze
scusa ma non ho capito
qualcun altro ha un'idea?
e se può rispondermi anche all'altra domanda
qualcun altro ha un'idea?
e se può rispondermi anche all'altra domanda
Laciando perdere gli algoritmi che sono su un piano differente, qui si parla di confronti.
lasciamo pure perdere le limitazioni sulle possibili permutazioni e ragioniamo solo sulla limitazione inferiore al problema dell'ordinamento cioè $\Omega(n*log_2(n))$ (per qualche info in più vedi es. post650816.html?hilit=scelte#p650816)
$n$ è il numeri di elementi da ordinare, perciò: $7*log_2(7) \approx 20$
questo vuol dire che quell'azienda vanta di ordinare con $10$ confronti cioè sottolimitare il limite teorico del problema dell'ordinamento, ovviamente è un assurdo e l'azienda ti sta fregando.
lasciamo pure perdere le limitazioni sulle possibili permutazioni e ragioniamo solo sulla limitazione inferiore al problema dell'ordinamento cioè $\Omega(n*log_2(n))$ (per qualche info in più vedi es. post650816.html?hilit=scelte#p650816)
$n$ è il numeri di elementi da ordinare, perciò: $7*log_2(7) \approx 20$
questo vuol dire che quell'azienda vanta di ordinare con $10$ confronti cioè sottolimitare il limite teorico del problema dell'ordinamento, ovviamente è un assurdo e l'azienda ti sta fregando.
ho due domande da farti hamming_burst
una è :
perchè hai fatto log in base 2 di 7
la seconda è un mio dubbio e l'avevo scritta anche nel messaggio:
prendendo la formula nlogn il logaritmo fa lievitare n?oppure lo fa abbassare
perchè prendendo la calcolatrice e mettendo una volta base 10 mi viene un numero minore di 1
mentre facendo il logaritmo naturale di 7 mi viene un numero maggiore di 1
Potresti spiegarmi questa tua scelta e questo mio dubbio?
una è :
perchè hai fatto log in base 2 di 7
la seconda è un mio dubbio e l'avevo scritta anche nel messaggio:
prendendo la formula nlogn il logaritmo fa lievitare n?oppure lo fa abbassare
perchè prendendo la calcolatrice e mettendo una volta base 10 mi viene un numero minore di 1
mentre facendo il logaritmo naturale di 7 mi viene un numero maggiore di 1
Potresti spiegarmi questa tua scelta e questo mio dubbio?
"maschulillo":
ho due domande da farti hamming_burst
una è :
perchè hai fatto log in base 2 di 7
è derivato dalla limitazione inferiore sull'albero delle scelte, leggi il link lo ho messo per questo motivo.
In pratica i confronti si fanno su due elementi su un calcolatore...
la seconda è un mio dubbio e l'avevo scritta anche nel messaggio:
prendendo la formula nlogn il logaritmo fa lievitare n?oppure lo fa abbassare
ovviamente lo fa aumentare, di poco perchè il logaritmo è abbastanze lento ma lo aumenta.
è una moltiplicazione e per ogni valore di $n>0$ (non ha senso valori negativi, sia per motivi di dominio che logici...) $n <= nlogn$.
[/quote][/quote]
perchè prendendo la calcolatrice e mettendo una volta base 10 mi viene un numero minore di 1
mentre facendo il logaritmo naturale di 7 mi viene un numero maggiore di 1
Potresti spiegarmi questa tua scelta e questo mio dubbio?
Sai come è l'andamento della funzione logaritmo cambiando la base (anche tramite visualizzazione cartesiana)?
$ln(7) > 1$
$log_7(7) = 1$
$log_10(7) < 1$
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo