Spiegazione del grande theta e della notazione asintotica

Big Omega ci dice il limite inferiore del runtime di una funzione e Big O ci dice il limite superiore.

Spesso sono diversi e non possiamo dare una garanzia sul runtime: varierà tra i due limiti e gli input. Ma cosa succede quando sono uguali? Quindi possiamo dare un limite theta (Θ): la nostra funzione verrà eseguita in quel momento, indipendentemente dall'input che le diamo.

In generale, vogliamo sempre dare un limite theta, se possibile, perché è il limite più preciso e più stretto. Se non possiamo dare un limite theta, la prossima cosa migliore è il limite O più stretto possibile.

Prendi, ad esempio, una funzione che cerca un array per il valore 0:

def containsZero(arr): #assume normal array of length n with no edge cases for num x in arr: if x == 0: return true return false
  1. Qual è il caso migliore? Bene, se l'array che diamo ha 0 come primo valore, ci vorrà un tempo costante: Ω (1)
  2. Qual è il caso peggiore? Se l'array non contiene 0, avremo iterato attraverso l'intero array: O (n)

Gli abbiamo dato un omega e un limite O, quindi per quanto riguarda theta? Non possiamo dargliene uno! A seconda dell'array che gli diamo, il runtime sarà da qualche parte tra costante e lineare.

Cambiamo un po 'il nostro codice.

def printNums(arr): #assume normal array of length n with no edge cases for num x in arr: print(x)

Riesci a pensare a un caso migliore e uno peggiore ?? Non posso! Non importa quale array gli diamo, dobbiamo iterare attraverso ogni valore dell'array. Quindi la funzione impiegherà ALMENO n tempo (Ω (n)), ma sappiamo anche che non impiegherà più di n tempo (O (n)). Cosa significa questo? La nostra funzione impiegherà esattamente n tempo: Θ (n).

Se i limiti sono confusi, pensaci in questo modo. Abbiamo 2 numeri, x e y. Ci viene dato che x <= ye che y <= x. Se x è minore o uguale a y e y è minore o uguale a x, allora x deve essere uguale a y!

Se hai familiarità con gli elenchi collegati, mettiti alla prova e pensa ai tempi di esecuzione di ciascuna di queste funzioni!

  1. ottenere
  2. rimuovere
  3. Inserisci

Le cose si fanno ancora più interessanti se si considera una lista doppiamente collegata!

Notazione asintotica

Come misuriamo il valore delle prestazioni degli algoritmi?

Considera come il tempo sia una delle nostre risorse più preziose. In informatica, possiamo misurare le prestazioni con la quantità di tempo necessaria per completare un processo. Se i dati elaborati da due algoritmi sono gli stessi, possiamo decidere la migliore implementazione per risolvere un problema.

Lo facciamo definendo i limiti matematici di un algoritmo. Queste sono le notazioni big-O, big-omega e big-theta, o le notazioni asintotiche di un algoritmo. Su un grafico il big-O sarebbe il più lungo che un algoritmo potrebbe richiedere per un dato set di dati, o il "limite superiore". Big-omega è come l'opposto di big-O, il "limite inferiore". È qui che l'algoritmo raggiunge la sua massima velocità per qualsiasi set di dati. Big theta è il valore esatto delle prestazioni dell'algoritmo o un intervallo utile tra limiti superiori e inferiori stretti.

Qualche esempio:

  • "La consegna avverrà entro la tua vita." (big-O, upper-bound)
  • "Posso pagarti almeno un dollaro." (big-omega, limite inferiore)
  • "La massima oggi sarà di 25 ° C e la minima sarà di 19 ° C." (big-theta, stretto)
  • "È un chilometro a piedi dalla spiaggia." (big-theta, esatto)

Maggiori informazioni:

//www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-big-theta-notation //stackoverflow.com/questions/10376740/what-exactly-does-big-%D3% La notazione A8 rappresenta //www.geeksforgeeks.org/analysis-of-algorithms-set-3asymptotic-notations/