O(n^2 * 2^(log n)) == O(n^2) ?
Perché penso che questo potrebbe essere il caso:
Nel grande O, prendi solo le parti del termine che sono più rilevanti, giusto? %codice%. Il O(n^2 + 3n + 9) == O(n^2) ha un'influenza molto maggiore sul risultato del termine rispetto a n^2 -part. link
Il tuo ragionamento è errato. La regola per cui puoi scartare termini irrilevanti si applica solo ai termini additivi, ma nel tuo caso le parti vengono moltiplicate.
Se il logaritmo nel tuo caso ha base 2, 2^ld(n) è in realtà n, quindi la complessità totale è n^3 , che sicuramente non è n^2 .
Supponendo che "log" sia il logaritmo naturale:
2 log (n) = exp (log 2 * log n) = exp (log n * log 2) = n log (2)
e O (n 2 2 (log n) ) = O (n (2 + log 2) ) ≈ O (n 2.693 )
Se "log" è il logaritmo di base 10, allora è O (n 2.301 ). Se "log" è il logaritmo di base 2, allora è O (n 3 ). Scrivi il log 10 o ln o ld per chiarire cosa intendi. Spesso la differenza è irrilevante, ma in questo caso è ovviamente importante.
E tu non "prendi solo le parti che sono più rilevanti". Puoi ignorare le parti che non aumentano il risultato di più di un fattore limitato. Qui, il fattore 2 (log n) non è chiaramente un fattore limitato.
Leggi altre domande sui tag big-o