Объяснение большой теты и асимптотической записи

Big Omega сообщает нам нижнюю границу времени выполнения функции, а Big O сообщает нам верхнюю границу.

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

В общем, мы всегда хотим по возможности давать тета-границу, потому что это наиболее точная и жесткая граница. Если мы не можем дать тета-границу, следующим лучшим вариантом будет максимально возможная 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-omega - это противоположность 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-нотация-представляют //www.geeksforgeeks.org/analysis-of-algorithms-set-3asymptotic-notations/