Обяснена голяма тета и асимптотична нотация

Big Omega ни казва долната граница на времето на изпълнение на дадена функция, а Big O ни казва горната граница.

Често пъти те са различни и не можем да дадем гаранция за времето на работа - тя ще варира между двете граници и входовете. Но какво се случва, когато са еднакви? Тогава можем да дадем тета (Θ) обвързан - нашата функция ще работи в това време, без значение какъв вход го даваме.

Като цяло винаги искаме да дадем тета граница, ако е възможно, тъй като тя е най-точната и най-тясна граница. Ако не можем да дадем тита граница, следващото най-добро нещо е възможно най-тясната О граница.

Вземете например функция, която търси в масив стойността 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, ще имаме итерация през целия масив: O (n)

Дадохме му омега и О, обвързани, така че какво да кажем за тета? Не можем да го дадем! В зависимост от масива, който му даваме, времето на изпълнение ще бъде някъде между постоянното и линейното.

Нека променим малко нашия код.

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

Можете ли да измислите най-добрия и най-лошия случай ?? Не мога! Без значение какъв масив му даваме, трябва да прегледаме всяка стойност в масива. Така че функцията ще отнеме ПОНЕ n време (Ω (n)), но също така знаем, че няма да отнеме по-дълго от n време (O (n)). Какво означава това? Нашата функция ще отнеме точно n време: Θ (n).

Ако границите са объркващи, помислете за това така. Имаме 2 числа, x и y. Дадено ни е, че x <= y и че y <= x. Ако x е по-малко или равно на y и y е по-малко или равно на x, тогава x трябва да е равно на y!

Ако сте запознати със свързани списъци, тествайте се и помислете за времето за изпълнение на всяка от тези функции!

  1. вземете
  2. Премахване
  3. добавете

Нещата стават още по-интересни, когато обмислите двойно свързан списък!

Асимптотична нотация

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

Помислете как времето е един от най-ценните ни ресурси. При изчисленията можем да измерваме производителността с времето, необходимо на процеса да завърши. Ако данните, обработвани от два алгоритма, са еднакви, можем да вземем решение за най-доброто изпълнение за решаване на проблем.

Правим това, като определяме математическите граници на алгоритъма. Това са big-O, big-omega и big-theta, или асимптотичните обозначения на алгоритъм. На графика голямото O ще бъде най-дългото, което един алгоритъм може да вземе за даден набор от данни или „горната граница“. Биг-омега е като обратното на big-O, "долната граница". Това е мястото, където алгоритъмът достига максималната си скорост за всеки набор от данни. Голямата тета е или точната стойност на производителността на алгоритъма, или полезен диапазон между тесни горни и долни граници.

Няколко примера:

  • „Доставката ще бъде там през целия ви живот.“ (голяма-O, горна граница)
  • „Мога да ви платя поне един долар.“ (голяма омега, долна граница)
  • „Най-високата температура днес ще бъде 25ºC, а ниската ще бъде 19ºC.“ (голям тета, тесен)
  • "До плажа има километър пеша." (голям тета, точно)

Повече информация:

//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-представлява //www.geeksforgeeks.org/analysis-of-algorithms-set-3asymptotic-notations/