Stavo esaminando questa domanda molto discussa e altamente votata su SO e incappato in un commento che ha ottenuto 5 upvotes.
Quindi presumo che questo sia stato un grande commento.Ma mi ha fatto girare la testa allo stesso tempo. Qualcuno può spiegare questo commento? Il commento dice:
You can't compare big-O values directly without thinking about constant factors. For small lists (and most lists are small), ArrayList's O(N) is faster than LinkedList's O(1).
tutto ciò che O (1) significa è che richiede tempo costante, ma non necessariamente 1 unità di tempo. Quindi, per un esempio concreto, supponiamo che LinkedList impieghi 3 secondi per accedere a qualsiasi elemento. Questo è in tempo costante, ma è piuttosto lento. Non è difficile immaginare una situazione in cui abbiamo un Arraylist con accesso O (n), ma dove n è abbastanza piccolo da non richiedere più di 2 secondi per l'accesso. In questi casi, ArrayList sarebbe effettivamente più veloce di LinkedList.
La definizione di BigO significa che hai definito una funzione in cui hai limitato il tempo di esecuzione in funzione della dimensione di input, per tutti i valori maggiori di qualche fattore costante.
Che cos'è un fattore costante? Fondamentalmente è la parte del tempo di esecuzione che non dipende dalla dimensione di input. Diciamo che il tuo elenco collegato è stato memorizzato in Cina. Anche se è O (1), ogni operazione comporta un volo in Cina. Questo è un fattore costante, non cambia mai. Tuttavia, la scalabilità dell'algoritmo è ancora O (1) perché il volo verso la Cina è la stessa quantità di tempo indipendente dal numero di elementi nell'elenco.
Quindi sì, questa affermazione è vera nella pratica: "Non puoi confrontare direttamente i valori di O grande senza pensare a fattori costanti."
questa affermazione probabilmente non è vera, dipende dall'implementazione: "Per gli elenchi di piccole dimensioni (e la maggior parte degli elenchi sono piccoli), l'O (N) di ArrayList è più veloce di O (1) di LinkedList."
Hai mai sentito di un mucchio di Fibonacci? Questo è un famigerato esempio di enorme fattore costante. Vedi qui: SO sull'heap di Fibonacci
Ogni notazione O grande nasconde un fattore costante dietro di essa. Una funzione O (N) potrebbe essere f (N) = N o g (N) = 100000000N; allo stesso modo, O (1) potrebbe essere t (N) = 1 o k (N) = 100000000000.
Nell'esempio sopra, per f (N) ek (N), quando N < 100000000000, il tempo lineare f (N) è in realtà più veloce del tempo costante k (N).
La definizione di O (f (n)) significa che il tempo di esecuzione dell'algoritmo specificato è minore o uguale a c * f (n), per alcuni c > 0 e per alcuni n > n '(cioè grandi valori di n andando verso l'infinito).
Quindi O (1) implica che il tempo di esecuzione è inferiore a qualche costante, per esempio j.
E O (n) implica che il tempo di esecuzione è inferiore a qualche costante, per esempio k, volte n. Quindi k * n.
Dato che stiamo assumendo che le liste siano piccole, ciò significa che n è un numero molto piccolo. Ora, a seconda dell'implementazione, anche i valori di je k possono variare. È del tutto possibile che il tempo costante di O (1) sia molto lungo, diciamo nell'ordine dei secondi. Ed è anche possibile che il fattore costante O (n) possa essere molto breve, diciamo nell'ordine dei microsecondi. In questo caso, con un piccolo valore di n, è chiaro che l'algoritmo O (n) può sovraperformare l'algoritmo O (1) (n microsecondi contro pochi secondi).
L'affermazione originale è sicuramente corretta - non puoi davvero confrontare facilmente Big-O senza considerare costanti, ma principalmente a piccoli valori di n . Una volta arrivati a valori più grandi, le differenze diventano più chiare.
Leggi altre domande sui tag algorithms linked-list