Cos'è ElectroYou | Login Iscriviti

ElectroYou - la comunità dei professionisti del mondo elettrico

Taglia di un problema: per Fib(N) -> log N

Linguaggi e sistemi

Moderatori: Foto UtentePaolino, Foto UtenteMassimoB

0
voti

[1] Taglia di un problema: per Fib(N) -> log N

Messaggioda Foto UtentePatras » 17 apr 2018, 7:41

Ciao a tutti!
Vi chiedo di aiutarmi per favore a capire cos'è la taglia di un problema o dimensione o comunque la chiamiate, che nel caso del problema di Fibonacci :
Fib(N) \implies \left \lceil \log_2(N) \right \rceil

Cosa potrebbe essere? Non riesco a trovare una definizione...
Io ho provato a fare anche l'albero... a vedere cosa può essere ma sia in termini di spazio occupato in memoria che in termini di prestazioni temporali non c'è il log_2 N da quello che vedo...

PS: per problema di Fibonacci si intende il calcolo della solita serie di Fibonacci.
Avatar utente
Foto UtentePatras
51 1 7
Frequentatore
Frequentatore
 
Messaggi: 129
Iscritto il: 24 mag 2017, 15:27

4
voti

[2] Re: Taglia di un problema: per Fib(N) -> log N

Messaggioda Foto Utentexyz » 17 apr 2018, 13:20

Complessità temporale di un algoritmo, di solito si indica con al notazione "O grande", nel tuo caso O(\log(n)):

https://en.wikipedia.org/wiki/Time_complexity
https://en.wikipedia.org/wiki/Big_O_notation

Quando si parla di complessità in informatica i logaritmi si intendono in base 2, quindi di solito viene omessa. Questa notazione deriva dalla notazione matematica introdotta da Donald E. Knuth nei sui libri "The Art of Computer Programming".

Esistono più algoritmi per calcolare la sequenza di Fibonacci, quello che ha appunto complessità O(\log(n)) è quello che usa le matrici:

https://kukuruku.co/post/the-nth-fibona ... in-olog-n/

L'uso dei right/left ceiling "⌈x⌉" si intende il numero intero maggiore più vicino a x:

https://en.wikipedia.org/wiki/Bracket_(mathematics)#Floor/ceiling_fun

Detto in parole semplici per trovare il centesimo numero di Fibonacci (354224848179261915075) con l'algoritmo sopra indicato impieghi al massimo \lceil\log_2(100)\rceil = \lceil 6.6438... \rceil = 7 passi.
Avatar utente
Foto Utentexyz
4.960 2 4 5
Master EY
Master EY
 
Messaggi: 1286
Iscritto il: 5 dic 2009, 18:37
Località: Italy Turin

0
voti

[3] Re: Taglia di un problema: per Fib(N) -> log N

Messaggioda Foto UtentePatras » 17 apr 2018, 15:43

Grazie mille, si conosco la complessità temporale di un algoritmo ma non credevo esistesse un algoritmo così veloce per Fibonacci... pensavo che il più veloce fosse quello semplice con una memoisazzione con prestazioni O(N)... invece la dimensione credevo riguardasse qualche proprietà degli alberi di decisione...

ma a prescindere dalla conoscenza a priori degli algoritmi veloci, sarebbe possibile matematicamente dimostrare che il migliore algoritmo che potrebbe esistere per Fib(N) avrebbe prestazioni O(log_2 N) ?
Mi ricordo che avevamo trovato un limite per Mergesort ma qui non saprei come farlo... Guardando l'algoritmo di Knuth che dà logN sembra solo il risultato di un bel lavoro su un problema ancora aperto...
Avatar utente
Foto UtentePatras
51 1 7
Frequentatore
Frequentatore
 
Messaggi: 129
Iscritto il: 24 mag 2017, 15:27

1
voti

[4] Re: Taglia di un problema: per Fib(N) -> log N

Messaggioda Foto Utentewruggeri » 17 apr 2018, 16:09

La risposta è: posto che il miglior algoritmo possibile per il calcolo della serie di Fibonacci abbia complessità logaritmica, salvo impedimenti dovuti alle specificità del problema (e non mi pare che ne abbia, ma dovrei controllare) dovresti poterlo dimostrare.

PS:
Patras ha scritto:memoisazzione


La parola è memoization... non italianizziamo i termini inglesi, per favore, che si finisce per far confusione e commettere errori grammaticali: la "z" che da inizio alla sillaba "zio" non è MAI preceduta da un'altra "z"!!!
Rispondo solo a chi si esprime correttamente in italiano.
Se non conosci un argomento, non parlarne.
Gli unici fatti sono quelli dimostrabili, il resto è opinione.
Non dirò una parola sulla politica e sul M5S, del quale aspetto solo l'estinzione.
Avatar utente
Foto Utentewruggeri
4.011 1 6 13
Expert EY
Expert EY
 
Messaggi: 728
Iscritto il: 25 nov 2016, 18:46

1
voti

[5] Re: Taglia di un problema: per Fib(N) -> log N

Messaggioda Foto Utentexyz » 17 apr 2018, 16:47

Difficile dimostrare matematicamente se un algoritmo è il migliore in assoluto e se qualcuno, per questo specifico problema, sia riuscito a farlo. Quando si trova un algoritmo con complessità logaritmica di solito si è contenti di averlo trovato.

Qui esiste una comparazione di alcuni algoritmi per la sequenza di Fibonacci:

https://www.nayuki.io/page/fast-fibonacci-algorithms

esiste oltre all'algoritmo matrix exponentiation un altro algoritmo chiamato fast doubling, il quale risulta sulla carta più veloce perché rimuove alcuni calcoli ridondanti ma la sua complessità asintotica è uguale al precedente.
Avatar utente
Foto Utentexyz
4.960 2 4 5
Master EY
Master EY
 
Messaggi: 1286
Iscritto il: 5 dic 2009, 18:37
Località: Italy Turin

0
voti

[6] Re: Taglia di un problema: per Fib(N) -> log N

Messaggioda Foto UtentePatras » 17 apr 2018, 17:45

scusate l'errore orribile in ogni caso la versione "italiana" corretta sarebbe memoizzazione (in realtà non esiste in italiano)... anche io non la userei mai ma l'ho sentita a voce troppe volte quindi ho provato a scriverla...

riguardo all'algoritmo vi ringrazio per le risposte mi avete risolto il dubbio
Avatar utente
Foto UtentePatras
51 1 7
Frequentatore
Frequentatore
 
Messaggi: 129
Iscritto il: 24 mag 2017, 15:27


Torna a PC e informatica

Chi c’è in linea

Visitano il forum: Nessuno e 2 ospiti