Notazione asintotica: n (log n) (log n) semplifica?

Question

Se ho un algoritmo che richiede n log n passaggi (ad es.heapsort), dove i passaggi richiedono log n tempo (ad es.confronto/scambio di interi "grandi" nell'intervallo da 0 a n-1), qual è il limite asintotico per l'intero processo.

Ovviamente possiamo dire "n (log n) (log n)", ma faccio fatica a convincermi che non posso semplificarlo in "n log n".Allo stesso tempo, ho difficoltà a giustificare l'istinto che insiste che io possa farlo.

Il mio istinto è semplicemente sbagliato su questo?

MODIFICARE

Sembra che il mio semplice esempio per evitare di complicare il problema abbia complicato il problema.Vabbè.

Il vero motivo della domanda è che spesso ho un algoritmo standard con una complessità nota, ma implementato utilizzando diversi contenitori sottostanti, in modo che i singoli passaggi siano O(log n) anziché O(1).Ad esempio, l'algoritmo di minimizzazione dell'automa di Hopcroft è O(n log n) - ma se inizi a utilizzare contenitori di alberi binari per gli stati, le transizioni e i risultati intermedi, i passaggi stessi diventano O(log n) - O(n log n) è non è più valido perché il presupposto degli accessi O(1) non è valido.

Tuttavia, le persone affermeranno che ci sono n stati e m transizioni, ma n e m tendono ad essere correlati linearmente per gli automi, assumendo che il numero di annotazioni di transizione sia costante e che gli automi siano più o meno deterministici.

Non mi sono preoccupato troppo di questo in passato: i casi con cui lavoro non sono molto grandi.Ma, beh, sto eseguendo un importante refactoring del mio codice degli automi e ho pensato che avrei potuto anche fare i conti correttamente per alcuni algoritmi chiave mentre procedo.

MODIFICARE

Inoltre sono sempre più convinto che il "n (log n) (log n)" sia sbagliato.

Se a è O(b log b) dove b è O(log c), cos'è a in termini di c?

Answer 1

Ecco una prova per contraddizione:

Diciamo che una funzione f (n) = n (log n) (log n). Supponiamo che pensiamo che sia anche theta (n log n), quindi in altre parole c'è una a per cui f (n) & Lt; = a * n log n vale per n grande

Ora considera f (2 ^ (a + 1)):

f (2 ^ (a + 1)) = 2 ^ (a + 1) * log (2 ^ (a + 1)) * log (2 ^ (a + 1)) = 2 ^ (a + 1 ) * log (2 ^ (a + 1)) * (a + 1), che è chiaramente più grande di un * 2 ^ (a + 1) * log (2 ^ (a + 1)) e abbiamo una contraddizione . pertanto f (n) non è una funzione n log n.

Answer 2

In generale, non è possibile moltiplicare le complessità in questo modo: per l'heap ordinamento, N indica il numero di elementi nell'heap, mentre per i grandi numeri interi, N probabilmente indica il limite superiore dei possibili valori. In generale, questi non devono essere correlati, quindi è piuttosto N log N log M (dove M è l'intervallo che gli articoli possono prendere).

In un'applicazione specifica, molto probabilmente, i numeri interi grandi seguono una distribuzione specifica. Ad esempio, si può sapere che sono tutti inferiori a 10 ^ 20. In tal caso, le operazioni di confronto richiedono un tempo costante (determinato da un limite superiore di 10 ^ 20). Quindi, anche il registro M è costante e l'intera complessità è in O (N registro N).

Answer 3

Non sarai in grado di ridurre n (log n) (log n) a n (log n) semplicemente perché non si tratta di una riduzione di un fattore costante.

Cosa c'è che non va in 2^<=> ?

Answer 4

Ok, la misura generale della complessità di un programma è la seguente:

Complessità O(f(n)) significa che esiste c, in modo tale che il numero dei passi corrispondenti della macchina di Turing prima che termini non sia maggiore di c*f(n), dove n è la lunghezza dell'input.

In questa definizione si tiene conto di tutto, perché i numeri interi possono essere arbitrariamente grandi e anche le operazioni aritmetiche su di essi aumenterebbero la funzione sotto O(n).

Ma se avessimo programmato direttamente le macchine di Turing, la tua domanda non sarebbe sorta.Nel mondo reale preferiamo astrarre.Mentre calcoliamo ancora i "passi" necessari per eseguire il programma, presupponiamo che siano necessarie determinate operazioni un passo.Supponiamo che per diversi motivi:

• Potrebbe assomigliare al lavoro reale della CPU, dove ogni aggiunta di numeri interi a 32 bit è effettivamente un passo (ed esistono algoritmi che effettivamente ne abusano, ad es."dominatori bit-verctor").
• Confrontiamo diversi algoritmi nello stesso dominio (ad esempio, confrontando gli ordinamenti di array misurando il numero di confronti).

In questo caso (il tuo primo EDIT), se vuoi concretizzare la tua misura di complessità, dovresti semplicemente moltiplicare le funzioni sotto O.Se quello che pensavi di fare un passo ora consideri di fare O(log N) passi, allora la quantità di passi concretizzati aumenta di un fattore O(log N).Pertanto la complessità totale è O(Nceppo nceppo N).

---

Per quanto riguarda il tuo secondo EDIT, la situazione è diversa.Lascia che il tuo algoritmo sia una complessità di O(nceppo N).Ma sai che l'input consiste in M numeri, ciascuno di log K cifre, quindi `N = O(Mlog K) (dobbiamo separare i conti, ecc.).È matematicamente corretto quindi scrivere la complessità complessiva come O(M * log K * (log M + log log K)), quindi non ci sono problemi qui.Ma di solito eliminiamo i dettagli non necessari per trovare una base comune su cui confrontare diversi algoritmi.