Cosa si intende per trovare costanti reali e intere nella notazione Big Oh?

Question

Cosa si intende per trovare costanti reali e intere nella notazione Big Oh?

#1 da (5 voti)
#2 da (0 voti)

0

Dal mio libro "Strutture dati e algoritmi in Java: Sesta edizione" la definizione di Big Oh è la seguente:

Let f(n) and g(n) be functions mapping positive integers to positive real numbers. We say that f(n) is O(g(n)) if there is a real constant c > 0 and an integer constant n0 >= 1 such that f(n) <= c * g(n) for n >= 0

Quindi mostrano che la funzione 8n + 5 è O(n) e usa la seguente giustificazione:

By the big-Oh definition, we need to find a real constant c > 0 and integer constant n0 >= 1 such that 8n+5 <= c * n for every integer n >= n0. It is easy to see that a possible choice is c = 9 and n0 = 5. Indeed, this is one of infinitely many choices available because there is a trade-off between cd and n0. For example, we could rely on constant c = 13 and n0 = 1

Nei miei studi di laurea, ho imparato che il grande O è solo il più grande fattore crescente in un metodo f(n) e come tale questa descrizione è nuova per me. Posso rispondere alle domande trovando il più grande fattore, ma non posso giustificare. Mi avrebbe aiutato se avessi saputo:

Che cosa si intende con "una costante reale c > 0 " e "una costante intera n0 >= 1 " Che cosa significano?
Di quali trade-off si parla quando dicono che c'è un compromesso tra c e n0 ?
Perché la scelta tra c e n0 è importante? Sembra strano selezionare valori arbitrari come c = 9999999999 e n0=1 e quindi concludere che effettivamente f(n) è Big-Oh di O(g(n)) solo perché 8*1 + 5 <= 999999999* 1

Non riesco a immaginare un caso in cui una funzione f(n) sarebbe maggiore di c*n se sei libero di scegliere c .

complexity big-o

posta Zimano 27.01.2018 - 20:08

fonte

2 risposte

Leggi altre domande sui tag complexity big-o

(AI) algoritmo per ottimizzare i parametri di input I database SQL tradizionali possono essere completamente sostituiti da NewSQL?

score 5 · Answer 1

La differenza qui è tra la tua definizione informale ("il più grande fattore crescente") e una rigorosa definizione matematica di O (n). Come fai a sapere che "il più grande fattore di crescita" in (n + log n) è n piuttosto che log n?

Potresti avere un piccolo foglio di regole che usi in modo da poter esaminare una serie semplice di fattori (indovino polinomi, logaritmi, esponenziali e forse fattoriali), ma cosa hai intenzione di fare quando ottieni qualcosa non sai come una funzione di Bessel ? Cos'è Big O per 1 / J ₀ (n) + e ⁿ? La definizione matematica formale ti dà la possibilità di elaborare in modo univoco Big O per la funzione qualsiasi .

score 0 · Answer 2

Cercherò di aiutarti a sviluppare intuizioni su questo. Quindi, per cominciare, la nozione è espressa in termini di funzioni che mappano interi positivi a numeri reali positivi. Dal momento che il contesto è l'informatica, è probabile che ciò sia dovuto al fatto che è una rappresentazione di come una variabile discreta, la dimensione dell'input (un numero intero, n ), mappa al tempo di esecuzione, che è un numero reale. Nota che nel mondo reale ci sono molti fattori che possono influenzare i tempi di esecuzione in vari modi, quindi in generale, non sarà una funzione "carina". Ma in analisi, facciamo alcune ipotesi che ci permettono di creare una stima abbastanza buona, qualcosa su cui possiamo lavorare (ad esempio, abbiamo questa nozione di operazioni elementari che richiedono un tempo fisso e assumiamo che possiamo semplicemente contarle e ignorare altre sottigliezze).

Successivamente, qual è il significato della costante reale c e del numero intero n0 ? La costante c è solo un moltiplicatore. Siamo interessati a classificare gli algoritmi in base alla loro crescita in un numero relativamente piccolo di categorie, quindi, ad esempio, se qualcosa cresce al massimo linearmente (proporzionale a n ), non ci interessa davvero se è 0.5*n o 10*n o 20.125*n (o c*n ) - trattiamo tutto come la stessa complessità temporale. Se guardi il grafico di c*n , la costante c la ridimensiona solo in verticale, in modo che per qualche valore di c , c*n sia sempre >= f(n) per i grandi valori di n (cioè, limita f(n) da sopra).

Che dire di n0 ? In generale, vogliamo sapere come si comporta l'algoritmo per i grandi valori di n . Per alcuni intervalli di valori iniziali e finiti che n può assumere, il valore di f(n) (il tempo di esecuzione) può superare il valore corrispondente di g(n) . Intuitivamente, questo è dovuto al fatto che per valori inferiori di n , c'è un'interazione tra vari fattori che contribuiscono al tempo di esecuzione, quindi non possiamo veramente dire cosa sta succedendo. Ma man mano che n cresce, uno di loro diventa dominante e le cose diventano più chiare (ad esempio, un termine nella funzione f(x) inizia a crescere più rapidamente di tutti gli altri - motivo per cui possiamo ignorarli, BTW). Ciò significa che possiamo trovare alcuni n = n0 dopo di che f(n) <= c*g(n) è sempre true (il valore effettivo di n0 non ha importanza, solo che esiste).

Questo è ciò che illustra la Figura 4.5. Puoi anche (ri?) Leggere la discussione proprio sotto l'Esempio 4.6.