Асимптотические обозначения 101: Большое О, Большое Омега и Тета (Учебный лагерь по асимптотическ...

Бесплатный 5-дневный мини-курс: https://backtobackswe.com
Попробуйте нашу полную платформу: https://backtobackswe.com/pricing
📹 Интуитивно понятные видеообъяснения
🏃 Запускайте код по мере обучения
💾 Сохраняйте прогресс
❓Новые, ранее не виденные вопросы
🔎 Получите все решения

Отличный ресурс: https://cathyatseneca.gitbooks.io/dat...

Шпаргалка по «Большому О»: http://bigocheatsheet.com

Сегодня мы начнём обсуждение того, о чём я долго вам врал. Всё будет максимально просто.

Мы рассмотрим не только неформальное определение, но и математические объяснения, лежащие в основе названия асимптотических «границ».

Опять же, нас это волнует, потому что истинный смысл алгоритма можно увидеть только в асимптотической природе времени выполнения и памяти.

Итак, представьте себе, у нас есть следующие компоненты:

Функция T(n), которая представляет собой фактическое количество сравнений, перестановок... просто... ресурсов, необходимых алгоритму с точки зрения времени или памяти. Это функция от n. При изменении n изменяется и T(n).

Наша задача — классифицировать поведение.

Граница O(f(n)) — это функция, которую мы выбираем для конкретного ограничения.

Определения, например:
«T(n) имеет O(f(n))» тогда и только тогда, когда для некоторых констант c и n0, T(n) меньше или равно c * f(n) для всех n, больших или равных n0.

На английском это означает, что f(n) — это фундаментальная функция, которая может ограничить сверху значение T(n) для всех n, и так до бесконечности.

У нас есть бесконечный выбор для c.

Наша константа не меняет поведение, она меняет «крутизну» графика.

Мы говорим, что... если я объявлю f(n) верхней границей, то я смогу найти константу c, на которую нужно умножить f(n), чтобы ВСЕГДА всегда поддерживать T(n) ниже моего c * f(n)... T(n) никогда не превзойдет c * f(n) для бесконечных значений n... следовательно, асимптотическое ограничение.

Если мы не можем найти эту c, то f(n) не может быть верхней границей, поскольку не удовлетворяет асимптотическому требованию.

Так почему же константы отбрасываются?

Ну... подумайте о том, что мы только что сделали. Введение произвольного c в качестве множителя в базовую функцию устраняет необходимость в константе. Это не добавляет никакого смысла границе, поскольку концептуально уже является частью определения того, что такое граница.

Большие границы

Большое O: Верхняя граница времени выполнения алгоритма

Тета (Θ): Это «жесткая» или «точная» граница. Она представляет собой комбинацию больших

Например:
Алгоритм, требующий Ω(n log n), занимает не менее n log n времени, но не имеет верхнего предела.

Алгоритм, требующий Θ(n log n), гораздо предпочтительнее, поскольку он занимает не менее n log n (Ω(n log n)) и не более n log n (O(n log n)).

Большая Омега (Ω): Нижняя граница времени выполнения алгоритма.

Малые границы

Малая O: Верхняя граница времени выполнения алгоритма, но асимптотическое время выполнения не может быть равно верхней границе.

Малой теты (θ) не существует.

Малой Омеги (ω): Нижняя граница времени выполнения алгоритма, но асимптотическое время выполнения не может быть равно нижней границе.

Если вам не удаётся получить точную верхнюю границу, попробуйте нижнюю (хотя, честно говоря, это менее полезно).

++++++++++++++++++++++++++++++++++++++++++++++++++++

HackerRank:    / @hackerrankofficial  

Тушар Рой:    / tusharroy2525  

GeeksForGeeks:    / @geeksforgeeksvideos  

Джарвис Джонсон:    / vsympathyv  

Успех в технологиях:    / @successintech  

#асимптотическиеотнотации