Пояснення великої тета та асимптотичної нотації

Велика Омега повідомляє нам нижню межу часу виконання функції, а Велика О - верхню межу.

Часто вони бувають різними, і ми не можемо надати гарантію на час виконання - вона буде змінюватися між двома межами та вхідними даними. Але що відбувається, коли вони однакові? Тоді ми можемо дати тета (Θ) зв’язаним - наша функція буде працювати в цей час, незалежно від того, який вхід ми вводимо.

Загалом, ми завжди хочемо дати тета-межу, якщо це можливо, оскільки вона є найбільш точною і найтіснішою. Якщо ми не можемо дати мету тета, наступне найкраще - це максимально щільна межа О.

Візьмемо, наприклад, функцію, яка шукає в масиві значення 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)

Ми дали йому омегу та O зв’язок, то як щодо тети? Ми не можемо дати йому одного! Залежно від масиву, який ми йому надаємо, час виконання буде десь посередині між постійним та лінійним.

Давайте трохи змінимо наш код.

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. додати

Все стає ще цікавішим, якщо розглянути подвійно пов’язаний список!

Асимптотичне позначення

Як ми вимірюємо значення продуктивності алгоритмів?

Поміркуйте, як час є одним із наших найцінніших ресурсів. Під час обчислень ми можемо виміряти продуктивність за часом, який вимагає процес. Якщо дані, що обробляються двома алгоритмами, однакові, ми можемо прийняти рішення про найкращу реалізацію для вирішення проблеми.

Ми робимо це, визначаючи математичні межі алгоритму. Це великі O, великі омега та великі тета, або асимптотичні позначення алгоритму. На графіку велике O буде найдовшим, який може прийняти алгоритм для будь-якого даного набору даних, або “верхньої межі”. Біг-омега - це як протилежність великому О, "нижній межі". Ось де алгоритм досягає максимальної швидкості для будь-якого набору даних. Велика тета - це або точне значення продуктивності алгоритму, або корисний діапазон між вузькими верхніми та нижніми межами.

Кілька прикладів:

  • "Доставка буде протягом вашого життя". (велике-O, верхнє обмеження)
  • "Я можу заплатити вам принаймні один долар". (велика омега, нижня межа)
  • "Найвища температура сьогодні становитиме 25ºC, а найнижча - 19ºC". (великий тета, вузький)
  • "До пляжу кілометр пішки". (big-theta, точно)

Більше інформації:

//www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-big-theta-notation //stackoverflow.com/questions/10376740/what-exactly-does-big-%D3% A8-нотація-представляти //www.geeksforgeeks.org/analysis-of-algorithms-set-3asymptotic-notations/