Quindi cerchiamo di praticare l'idea di confrontare due polinomi,
per esempio, e decidere se
appartengono o meno alla stessa classe.
Quindi definiamo la classe stessa.
Per farlo, iniziamo con
l'idea della notazione Big-O,
che a volte è indicata è
sottolineata o nel testo scritto a mano.
La procedura qui è la seguente.
Fondamentalmente, presuppone che abbiamo due delle nostre funzioni
come x al quadrato e 5x al quadrato meno 100x.
Noi, in qualche modo, stiamo parlando
del limite superiore di
una funzione rispetto a un'altra.
Fondamentalmente, significa che una funzione è maggiore non
più che in un numero fisso
di volte rispetto all'altra.
In altre parole, dobbiamo annotare una disuguaglianza qui.
Fondamentalmente, supponiamo che abbiamo qualche quartiere
di un dato punto, a, per esempio.
Chiamiamo una funzione
big-o da un'altra funzione in questo quartiere.
Se c'è una costante,
costante positiva, C come la relazione, il
valore assoluto della relazione delle
funzioni f e g non supera
questo valore c. Quindi consideriamo,
per esempio, il nostro caso.
Abbiamo x al quadrato,
per esempio, chiamiamolo f è x al quadrato,
g è 5x al quadrato meno
100x e suppongo che x si avvicini all'infinito.
Quindi quello che faremo, diremo,
è che qualche funzione è maggiore dell'
altra in un quartiere dell'infinito.
Dobbiamo annotare qualcosa
come il valore assoluto di f
è minore o uguale a una
costante moltiplicata per il valore assoluto di g, va bene?
In altre parole, x al quadrato minore o maggiore di una
costante moltiplicata per Epsilon
[inudibile] 5x al quadrato meno 100x.
È abbastanza facile capire quale
costante sia effettivamente buono per noi qui.
Ad esempio, iniziamo con
la costante c, uguale a uno.
Beh, è ovvio che lo è,
perché se solo assumiamo che c è uguale a uno.
Quindi, otteniamo x al quadrato su un lato e
5x quadrati meno 100x sull'altro lato.
Se sottraiamo x al quadrato
da entrambi i lati, quindi, otteniamo funzioni,
che sono chiaramente positive da un certo punto,
perché stiamo guardando
una funzione parabolica con positivo.
Il mio coefficiente, quindi, c'
è una radice e dopo questa radice,
abbiamo solo valori positivi.
Così, questa disuguaglianza vale e uno.
F è Big-o verso G,
questo è stato un esempio.
Un codice sostiene facilmente che se abbiamo bisogno di
scambiare questa funzione che è ancora detiene,
solo perché invece di scrivere c è uguale a uno.
Cerchiamo di fare questo interpretare qui.
Quindi, fondamentalmente, dobbiamo dimostrare qualcosa, come questo qui.
Quindi, per fare ciascuno,
dobbiamo considerare un altro c nulla,
uno piccolo, ma uno grande.
Quindi, fondamentalmente, iniziamo con come c uguale a cinque.
Poi otteniamo un bel risultato qui.
Ma non è sempre il caso, perché, ad esempio,
diamo un'occhiata ad un caso più interessante.
Ad esempio, cosa fa [inudibile] funzioni,
seno di x e x,
come x si avvicina a zero? Sappiamo cosa?
Sono fondamentalmente equivalenti come ci si dovrebbe aspettare,
che seno x è fondamentalmente un Big-O di x.
È abbastanza facile, perché
il valore assoluto di seno x, come abbiamo detto,
mentre stavamo parlando del nostro secondo limite importante,
ora è maggiore del modello x,
perché il valore assoluto di x
è in realtà l'area del settore,
e seno di x è l'area del triangolo rispettivamente.
Quindi con questo, contiamo che
usando una costante c uguale a uno,
otteniamo questo assolutamente giusto.
Ma cosa succede se sostituiamo un punto di interesse da zero,
diciamo infinito?
Prima di tutto, le idee che seno di x
è Big-O verso x,
tiene ancora a questo punto, perché fondamentalmente,
seno di x non è maggiore di uno e x è il più grande.
Come puoi immaginare, x si avvicina all'infinito.
Pertanto, questa disuguaglianza vale ancora,
per esempio, per la stessa costante uguale a una.
Ma se lo cambiamo,
se cambiamo due funzioni,
allora otteniamo 380,
[inudibile] qui, perché seno x
e x non è correlato in tempi.
Perché seno x è ancora, scusa,
ti ho detto che abbiamo bisogno di
scambiare le funzioni e non l'abbiamo fatto.
Quindi e' un grande inganno qui.
Questo è meno ingannevole.
Quindi x è Big-o dal seno di x.
Quindi fondamentalmente, seno di x è
delimitato da uno e meno uno e x è illimitata.
Quindi, se abbiamo cercato di venire con l'idea
che x dovrebbe essere inferiore a qualche costante,
moltiplicato per seno di x e diciamo che questa
costante, per esempio, 10.000.
Allora, qual e' l'errore?
Quindi possiamo ad esempio,
prendere x più grande di due, dal momento che n,
questa equazione, ci sarà quasi
sicuramente solo cadere e
questo non è estremamente il caso.
Non e' giusto. Quindi, quando
stiamo parlando di notazione Big-o,
devi sempre considerare l'ordine qui.
Quale funzione, per quanto riguarda quale funzione? E' Big-o?