Suuri teeta- ja oireeton merkitys selitetty

Big Omega kertoo funktion ajonajan alarajan ja Big O kertoo ylärajan.

Usein ne ovat erilaisia, emmekä voi antaa takuua suoritukselle - se vaihtelee kahden rajan ja tulojen välillä. Mutta mitä tapahtuu, kun he ovat samanlaisia? Sitten voimme antaa sidotun teeta (Θ) - toimintomme toimii tuona aikana riippumatta siitä, minkä panoksen annamme sille.

Yleensä haluamme aina antaa teeta-sidoksen, jos mahdollista, koska se on tarkin ja tiukin sidottu. Jos emme voi antaa teeta-sidosta, seuraava paras asia on tiukin mahdollinen O-sidos.

Otetaan esimerkiksi funktio, joka etsii matriisista arvoa 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. Mikä on paras tapa? No, jos sille annetulla taulukolla on ensimmäinen arvo 0, se vie vakioaikaa: Ω (1)
  2. Mikä on pahin tapaus? Jos matriisi ei sisällä 0, iteroidaan koko taulukko: O (n)

Olemme antaneet sille omega- ja O-sidoksen, joten entä teeta? Emme voi antaa sille yhtä! Annetusta taulukosta riippuen ajonaika on vakion ja lineaarisen välissä.

Muutetaan koodiamme hieman.

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

Voitteko ajatella parasta ja pahinta tapausta? En voi! Riippumatta siitä, minkä taulukon annamme sille, meidän on toistettava taulukon jokaisen arvon läpi. Joten toiminto kestää vähintään N aikaa (Ω (n)), mutta tiedämme myös, että se ei vie kauemmin kuin n aika (O (n)). Mitä tämä tarkoittaa? Toimintamme vie tarkalleen n aikaa: Θ (n).

Jos rajat ovat hämmentäviä, ajattele asiaa näin. Meillä on 2 numeroa, x ja y. Meille annetaan, että x <= y ja että y <= x. Jos x on pienempi tai yhtä suuri kuin y ja y on pienempi tai yhtä suuri kuin x, niin x: n on oltava yhtä suuri kuin y!

Jos tunnet linkitetyt luettelot, testaa itseäsi ja ajattele näiden toimintojen ajoaikoja!

  1. saada
  2. Poista
  3. lisätä

Asiat muuttuvat vieläkin mielenkiintoisemmiksi, kun tarkastellaan kaksoislinkitettyä luetteloa!

Asymptoottinen merkintä

Kuinka mitataan algoritmien suorituskykyarvo?

Mieti, kuinka aika on yksi arvokkaimmista resursseistamme. Laskennassa voimme mitata suorituskykyä prosessin suorittamiseen kuluvalla ajalla. Jos kahden algoritmin käsittelemät tiedot ovat samat, voimme päättää parhaasta toteutuksesta ongelman ratkaisemiseksi.

Teemme tämän määrittelemällä algoritmin matemaattiset rajat. Nämä ovat iso-O, iso-omega ja iso-teeta tai algoritmin asymptoottiset merkinnät. Kaaviossa iso-O olisi pisin, mitä algoritmi voisi ottaa mihin tahansa tietojoukkoon, tai "yläraja". Big-omega on kuin iso-O: n vastakohta, "alaraja". Siellä algoritmi saavuttaa huippunopeuden mille tahansa tietojoukolle. Iso teeta on joko tarkka algoritmin suorituskykyarvo tai hyödyllinen alue kapean ylä- ja alarajan välillä.

Joitain esimerkkejä:

  • "Toimitus on siellä elämäsi aikana." (iso-O, yläraja)
  • "Voin maksaa sinulle vähintään yhden dollarin." (iso-omega, alaraja)
  • "Korkein lämpötila on tänään 25 ºC ja matala on 19 ºC." (iso-teeta, kapea)
  • "Rannalle on kilometrin kävelymatka." (iso-teeta, tarkka)

Lisää tietoa:

//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/