Објашњена велика тета и асимптотска нотација

Велики Омега нам говори доњу границу времена извршавања функције, а Велики О нам горњу границу.

Често су различити и не можемо дати гаранцију за време извршавања - она ​​ће се разликовати између две границе и улаза. Али шта се дешава када су исти? Тада можемо дати тхета (Θ) везану - наша функција ће се покретати за то време, без обзира на унос који смо јој дали.

Генерално, увек желимо дати тхета везану ако је могуће, јер је најтачнија и најтеснија веза. Ако не можемо дати тхета вез, следећа најбоља ствар је најчвршћа могућа О веза.

Узмимо, на пример, функцију која претражује низ вредности 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. Који је најбољи случај? Па, ако низ који му дајемо има као прву вредност 0, биће потребно константно време: Ω (1)
  2. Који је најгори случај? Ако низ не садржи 0, проћи ћемо кроз читав низ: О (н)

Дали смо му омега и О везу, па шта је са тхета? Не можемо му дати! У зависности од низа који му дајемо, време извођења ће бити негде између константног и линеарног.

Променимо мало свој код.

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

Можете ли смислити најбољи и најгори случај ?? Не могу! Без обзира који низ му дајемо, морамо прелистати сваку вредност у низу. Дакле, функција ће трајати БАРЕМ н времена (Ω (н)), али такође знамо да неће трајати дуже од н времена (О (н)). Шта ово значи? Наша функција ће трајати тачно н времена: Θ (н).

Ако су границе збуњујуће, размислите о томе овако. Имамо 2 броја, к и и. Добијамо да је к <= и, а да и <= к. Ако је к мање или једнако и, а и мање или једнако к, тада к мора бити једнако и!

Ако сте упознати са повезаним листама, тестирајте се и размислите о времену извођења сваке од ових функција!

  1. добити
  2. уклонити
  3. додати

Ствари постају још занимљивије када узмете у обзир двоструко повезану листу!

Асимптотска нотација

Како меримо вредност перформанси алгоритама?

Размислите како је време један од наших највреднијих ресурса. У рачунарству можемо мерити перформансе с временом потребно за завршетак процеса. Ако су подаци које обрађују два алгоритма исти, можемо да одлучимо о најбољој примени за решавање проблема.

То радимо дефинишући математичке границе алгоритма. То су биг-О, биг-омега и биг-тхета, или асимптотски записи алгоритма. На графикону би велико О било најдуже што би алгоритам могао узети за било који дати скуп података или за „горњу границу“. Биг-омега је као супротност великом-О, „доња граница“. Ту алгоритам достиже највећу брзину за било који скуп података. Велика тхета је или тачна вредност перформанси алгоритма, или корисни распон између уских горњих и доњих граница.

Неки примери:

  • „Достава ће бити тамо током вашег живота.“ (велика-О, горња граница)
  • „Могу да вам платим најмање један долар.“ (велика омега, доња граница)
  • "Највиша температура данас ће бити 25 ° Ц, а најнижа 19 ° Ц." (велика-тхета, уска)
  • „До плаже је километар хода.“ (велика тата, тачно)

Више информација:

//ввв.кханацадеми.орг/цомпутинг/цомпутер-сциенце/алгоритхмс/асимптотиц-нотатион/а/биг-биг-тхета-нотатион //стацковерфлов.цом/куестионс/10376740/вхат-екацтли-доес-биг-%Д3% А8-нотатион-представљају //ввв.геексфоргеекс.орг/аналисис-оф-алгоритхмс-сет-3асимптотиц-нотатионс/