Come fa f (n)

Question

Ho letto Questo tutorial in termini di complessità del tempo , e sono un po 'perplesso sulla sua spiegazione di Big $ o $ notazione. Scrive:

.

$ o (g (n))= $ { $ f (n) $ Esistono costanti positive $ c $ e $ n_0 $ tale che $ 0 \ Leq F (n) \ leq c * g (n) $ per tutti $ n> n_0 $ .

Il modo in cui lo capisco, $ c * g (n) $ denota $ c $ moltiplicato di $ G (n) $ . Se questo è il caso, in che modo l'espressione precedente specifica il tempo e non solo quella $ c * g (n) $ è maggiore di $ f (n) $ ? O sono errato, e questa è una notazione che non capisco? La mia comprensione della complessità del tempo è molto rudimentale, quindi perdonami se questo è solo uno stupido errore da parte mia.

Answer 1

.

Come fa f (n)

no. La notazione Bachmann-Landau è semplicemente un modo composto per confrontare il tasso di crescita delle funzioni. Non dice nulla di cosa significano quelle funzioni , e possiamo essere abbastanza sicuri che Bachmann non stia pensando ai computer quando ne è salito nel 1894.

Quale significato assegnato a tali funzioni dipende da te. Ad esempio, quando si analizzano gli algoritmi di smistamento basati sul confronto, in genere assumiamo $ N $ per essere il numero di elementi nella raccolta e $ f (n) $ per essere il numero di confronti o il numero di swap o il numero di confronti e swap.

Nota anche che tutto questo è sempre relativo a un modello di macchina o un modello di costo.

Come esempio molto semplice, se dovessi chiederti qual è la complessità algoritmica del caso peggiore del caso per la copia di un elenco, vorresti dire $ o (n) $ . Ma in realtà, la risposta corretta sarebbe "Non posso dirti perché non hai specificato il modello della macchina". Perché, ad esempio, in una macchina di Turing, la copia di un elenco è $ o (n ^ 2) $ , perché per ogni elemento è stato copiato, la testa del TM ha guidare ulteriormente e ulteriormente e ulteriormente per raggiungere la fine della lista per scrivere il prossimo elemento.

Answer 2

dicendo che il tempo di esecuzione di un algoritmo è in $ o (G (n)) $ dà, come hai notato, solo un limite superiore. Inoltre, il limite superiore è dato con le costanti $ c $ e $ n_0 $ sconosciuto. Quindi sì, è un'informazione piuttosto debole sul tempo di esecuzione.

la costante non specificata $ c $ può contenere le informazioni sul costo reale delle operazioni di base dell'algoritmo, che possono essere sconosciute e / o variabili tra le corse Ma ancora noto per costare una quantità di tempo che è limitato. La costante non specificata $ n_0 $ riflette che il limite dato si riferisce a dimensioni di grandi dimensioni dell'ingresso (o qualunque dei parametri $ N $ < / span> rappresenta).

Altri simboli sono usati per dare altri tipi o Informazioni più precise sul tempo di esecuzione.