Sto imparando gli algoritmi e mi sono imbattuto in qualcosa di molto interessante.
Il limite asintotico dell'equazione lineare (a * n)+b è O(n^2) , per tutto a > 0.
Questo è lo stesso limite di a * n^2 + b * n + c , che è sorprendente.
È importante rendersi conto che O(f) rappresenta un insieme di funzioni, per cui c*f è un limite superiore asintotico per una percentuale costante dic.
Proprio come c'è più di un numero più grande di 1 , non c'è solo una singola funzione che si qualifica come limite superiore asintotico per una funzione.
Il limite più stretto per (a*n) + b) è O(n) , ma è anche in O(n^2) , ma questo è molto generoso e non fornisce tante informazioni quanto lo è in O(n) , perché quello è un affermazione molto più strong.
Ti suggerisco di dare un'occhiata a questa domanda simile per ulteriori informazioni.
In parole povere, qualsiasi due funzioni può essere limitata dallo stesso limite. La cosa a cui teniamo veramente è se il limite è stretto o allentato. qualsiasi costante O (1), le funzioni lineari e quadratiche possono essere sicuramente delimitate da O (n 2 ), o O (n 3 ), o O (n 4 ), o O (e n ).
Ma considerare un limite molto allentato non può davvero fornire molte informazioni su una funzione stessa. Quindi, in pratica, dovremmo sempre scegliere il limite più stretto per una funzione. Di solito, quando parliamo del limite, potrebbe implicitamente essere il limite più stretto.
Leggi altre domande sui tag algorithms complexity