Seletatud suur teeta ja asümptootiline tähistus

Suur Omega ütleb meile funktsiooni tööaja alumise piiri ja Suur O ülemise piiri.

Sageli on need erinevad ja me ei saa tööajale garantiid anda - see varieerub kahe piiri ja sisendite vahel. Aga mis juhtub, kui nad on ühesugused? Siis saame teeta (Θ) siduda - meie funktsioon töötab selle aja jooksul, olenemata sellest, millise sisendi me sellele anname.

Üldiselt tahame teeta võimaluse korral alati siduda, kuna see on kõige täpsem ja tihedam. Kui me ei oska teeta-sidet anda, on järgmine parim asi võimalikult range O-seos.

Võtame näiteks funktsiooni, mis otsib massiivilt väärtust 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. Mis on parim juhtum? Noh, kui selle massiivi esimese väärtusena on 0, võtab see konstantset aega: Ω (1)
  2. Mis on halvim juhtum? Kui massiiv ei sisalda 0, siis kordame kogu massiivi: O (n)

Oleme andnud omega ja O seotud, mis siis teeta? Me ei saa seda anda! Sõltuvalt sellest, millise massiivi me talle anname, jääb käitamisaeg konstantse ja lineaarse vahele.

Muudame natuke oma koodi.

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

Kas suudate välja mõelda parima ja halvima juhtumi ?? Ma ei saa! Sõltumata sellest, millise massiivi me sellele anname, peame kordama massiivi iga väärtust. Nii et funktsioon võtab vähemalt N aega (Ω (n)), kuid me teame ka, et see ei võta kauem aega kui n aega (O (n)). Mida see tähendab? Meie funktsioon võtab täpselt n aega: Θ (n).

Kui piirid on segased, mõelge sellele niimoodi. Meil on 2 numbrit, x ja y. Meile antakse, et x <= y ja y <= x. Kui x on väiksem või võrdne y-ga ja y on väiksem või võrdne x-ga, siis peab x olema võrdne y-ga!

Kui olete lingitud loenditega tuttav, proovige ennast ja mõelge kõigi nende funktsioonide tööajale!

  1. saada
  2. eemalda
  3. lisama

Asjad muutuvad veelgi huvitavamaks, kui kaalute topeltlingitud loendit!

Asümptootiline tähis

Kuidas mõõta algoritmide jõudlusväärtust?

Mõelge, kuidas aeg on üks meie väärtuslikumaid ressursse. Arvutamisel saame tulemuslikkust mõõta protsessi lõpuleviimiseks kuluva ajaga. Kui kahe algoritmi poolt töödeldavad andmed on ühesugused, võime probleemi lahendamiseks otsustada parima rakendamise.

Teeme seda algoritmi matemaatiliste piiride määratlemisega. Need on suur-O, suur-oomega ja suur-teeta ehk algoritmi asümptootilised tähised. Graafikul oleks suur-O pikim, kui algoritm võib antud andmekogumi jaoks kasutada, või ülemine piir. Suur-oomega on nagu suure-O vastand, “alumine piir”. Seal jõuab algoritm kõigi andmekogumite tippkiiruseni. Suur teeta on kas algoritmi täpne jõudlusväärtus või kasulik vahemik kitsa ülemise ja alumise piiri vahel.

Mõned näited:

  • "Tarneaeg saabub teie elu jooksul." (suur-O, ülemine piir)
  • "Ma võin teile maksta vähemalt ühe dollari." (suur-oomega, alumine piir)
  • "Kõrge temperatuur on täna 25 ºC ja madal 19 ºC." (suur-teeta, kitsas)
  • "Rannani on kilomeetrine jalutuskäik." (suur-teeta, täpne)

Rohkem informatsiooni:

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