Little-OH Notation in dettaglio, CS Homework, esclusa l'assegnazione effettiva

Question

Sono seduto qui con questo incarico in un corso su algoritmi con enormi set di dati e l'uso della notazione ridotta mi ha confuso, anche se sono perfettamente fiducioso con Big-OH.

Non voglio una soluzione al compito e come tale non la presenterò. Invece la mia domanda è come interpreto la complessità del tempo o (log n)?

So dalla definizione che un algoritmo deve crescere asintoticamente più lento di O (log n), ma non sono sicuro se questo significhi che l'algoritmo deve essere in esecuzione in tempo costante o se è ancora permesso essere Log n in determinate condizioni, tale che c = 1 o se è davvero Log (N-1).

Dire che un algoritmo ha un tempo di esecuzione di O (log n) ma in effetti fa due iterazioni e come tale c = 2, ma 2*log n è ancora O (log n), ho ragione quando dico che questo non è valido per poco-oh?

Qualsiasi aiuto è molto apprezzato e se rigorosamente necessario per chiarimenti, fornirò l'incarico

Answer 1

Per dire il f è 'Little-oh-of G' f = o(g), significa che il quoziente

|f(x)/g(x)|

Approcci 0 come x si avvicina all'infinito. Riferendosi al tuo esempio di o(log n), quella classe contiene funzioni come log x / log (log x), sqrt(log x) E molti altri, così o(log x) Sicuramente non implica O(1). D'altro canto, log (x/2) = log x - log 2, Così

log (x/2) / log x = 1 - log 2 / log x -> 1

e log (x/2) non è in classe o(log x).

Answer 2

Per Little-OH, F (x) non deve essere più piccolo di G (x) per tutti x. Deve essere più piccolo solo dopo un certo valore di x. (Per la tua domanda, è ancora permesso di essere log n in determinate condizioni.)

Per esempio:

 let f(x) = 5000x and g(x) = x^2

f (x) / g (x) come x si avvicina all'infinito è 0, quindi f (x) è litte-o di g (x). Tuttavia, a x = 1, f (x) è maggiore di G (x). Solo dopo che x diventa maggiore di 5000 g (x) sarà più grande di f (x).

Quello che un po '-o ci dice davvero è che G (x) cresce sempre a un ritmo più veloce di F (x). Ad esempio, guarda quanto f (x) è cresciuto tra x = 1 e x = 2:

 f(1) = 5000
 f(2) = 10000 - f(x) became twice as big

Ora guarda G (x) sullo stesso intervallo:

 g(1) = 1
 g(2) = 4 - g(x) became four times bigger

Questo tasso aumenterà ancora di più a valori più grandi di X. Ora, poiché G (x) aumenta a una velocità più veloce e perché prendiamo X all'infinito, ad un certo punto diventerà più grande di F (x). Ma questo non è quello di cui si preoccupa un po ', si tratta del tasso di cambiamento.