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

[Patras]

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 :


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 da quello che vedo...

PS: per problema di Fibonacci si intende il calcolo della solita serie di Fibonacci.

[xyz]

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

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à è 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 passi.

[Patras]

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 ... 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 ?
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...

[rugweri]

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:

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"!!!

[xyz]

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.

[Patras]

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