Paaiškinta didžioji teta ir besimptotinis žymėjimas

„Big Omega“ nurodo apatinę funkcijos vykdymo laiko ribą, o „Big O“ - viršutinę.

Dažnai jie skiriasi ir mes negalime pateikti garantijos vykdymo laikui - jis skirsis tarp dviejų ribų ir įvesties. Bet kas nutinka, kai jie vienodi? Tada galime suteikti susietą teta (Θ) - per tą laiką mūsų funkcija veiks, nesvarbu, kokį įnašą jai duosime.

Apskritai, jei įmanoma, mes visada norime suteikti susietą tetą, nes ji yra tiksliausia ir griežčiausiai surišta. Jei negalime susieti teta, kitas geriausias dalykas yra kuo griežtesnis O susietas.

Paimkime, pavyzdžiui, funkciją, kuri masyvo ieško 0 reikšmei:

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. Koks geriausias atvejis? Na, jei masyvas, kurį mes jam suteikiame, yra 0 kaip pirmoji reikšmė, tai užtruks pastovų laiką: Ω (1)
  2. Koks blogiausias atvejis? Jei masyve nėra 0, mes pakartosime visą masyvą: O (n)

Mes suteikėme jai surištą omega ir O, o kaip bus su teta? Mes negalime jam to duoti! Priklausomai nuo masyvo, kurį jam suteiksime, vykdymo laikas bus kažkur tarp pastovaus ir tiesinio.

Šiek tiek pakeiskime savo kodą.

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

Ar galite sugalvoti geriausią ir blogiausią atvejį ?? Aš negaliu! Nesvarbu, kokį masyvą mes jam suteikiame, turime kartoti kiekvieną masyvo vertę. Taigi funkcija užtruks mažiausiai n laiko (Ω (n)), bet mes taip pat žinome, kad tai užtruks ilgiau nei n laiko (O (n)). Ką tai reiškia? Mūsų funkcija užtruks tiksliai n laiko: Θ (n).

Jei ribos yra painios, pagalvokite apie tai taip. Mes turime 2 skaičius, x ir y. Mums duota, kad x <= y ir kad y <= x. Jei x yra mažesnis arba lygus y, o y yra mažesnis arba lygus x, tada x turi būti lygus y!

Jei esate susipažinę su susietais sąrašais, išbandykite save ir pagalvokite apie kiekvienos iš šių funkcijų vykdymo laiką!

  1. gauti
  2. pašalinti
  3. papildyti

Viskas tampa dar įdomiau, kai atsižvelgiate į dvigubai susietą sąrašą!

Asimptotinis žymėjimas

Kaip mes matuojame algoritmų našumo vertę?

Apsvarstykite, kaip laikas yra vienas iš vertingiausių mūsų išteklių. Skaičiuodami, mes galime įvertinti našumą, kiek laiko užtrunka procesas. Jei dviem algoritmais apdorojami duomenys yra vienodi, galime nuspręsti, kaip geriausiai įgyvendinti problemą.

Tai darome apibrėždami matematines algoritmo ribas. Tai yra big-O, big-omega ir big-theta arba asimptotiniai algoritmo žymėjimai. Grafike didelis-O būtų ilgiausias algoritmas, kurį galėtų atlikti bet kuris duomenų rinkinys, arba „viršutinė riba“. „Big-omega“ yra tarsi „big-O“ priešingybė, „apatinė riba“. Štai kur algoritmas pasiekia didžiausią greitį bet kokiam duomenų rinkiniui. Didžioji teta yra arba tiksli algoritmo našumo vertė, arba naudingas diapazonas tarp siaurų viršutinių ir apatinių ribų.

Keletas pavyzdžių:

  • „Pristatymas bus jūsų gyvenime.“ (didelis-O, viršutinė riba)
  • - Aš galiu tau sumokėti bent vieną dolerį. (didelė omega, apatinė riba)
  • „Šiandien aukščiausia temperatūra bus 25ºC, o žema - 19ºC.“ (didelė teta, siaura)
  • - Iki paplūdimio nueisite kilometrą. (tikslioji teta)

Daugiau informacijos:

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