п – пункт 1. Определение О
«Нотация О большое – это математическая нотация, которая описывает ограничивающее поведение функции, когда *аргумент стремится к определенному значению или бесконечности. Он является членом семейства нотаций, изобретенных Полом Бахманом, Эдмундом Ландау и другими, которые в совокупности называются нотациями Бахмана-Ландау или асимптотическими нотациями ».
1 вопрос, что такое нотация. >> Нотация - система условных обозначений, принятая в какой-либо области знаний или деятельности, великолепно.
2 вопрос, *«…когда аргумент стремится…» зачем нам куда-то стремиться?: При сравнении различных алгоритмов важно знать, как их сложность зависит от объёма входных данных. Допустим, при сортировке одним методом обработка тысячи чисел занимает 1 с., а обработка миллиона чисел – 10 с., при использовании другого алгоритма может потребоваться 2 с. и 5 с. соответственно. В таких условиях нельзя однозначно сказать, какой алгоритм лучше. Для это мы юзаем входные данные, стремящиеся к биг значениям.
«Алгоритм — это программа, которая представляет из себя исключительно вычисление, без других часто выполняемых компьютером вещей — сетевых задач или пользовательского ввода-вывода. Анализ сложности позволяет нам узнать, насколько быстра эта программа, когда она совершает вычисления. Примерами чисто вычислительных операций могут послужить операции над числами с плавающей запятой (сложение и умножение), поиск заданного значения из находящейся в ОЗУ базы данных, определение игровым искусственным интеллектом (ИИ) движения своего персонажа»
3 вопрос, что за дичь написана в определении, я учился на врача и ничего не понимаю. >> нотация О большое описывает сложность вашего кода с использованием алгебраических терминов.
р – рубрика 2. Как высчитать это О.
Отступление: Многие алгоритмы предлагают выбор между объёмом памяти и скоростью. Задачу можно решить быстро, использую большой объём памяти, или медленнее, занимая меньший объём. Типичным примером в данном случае служит алгоритм поиска кратчайшего пути. Представив карту города в виде сети, можно написать алгоритм для определения кратчайшего расстояния между двумя любыми точками этой сети. Чтобы не вычислять эти расстояния всякий раз, когда они нам нужны, мы можем вывести кратчайшие расстояния между всеми точками и сохранить результаты в таблице. Когда нам понадобится узнать кратчайшее расстояние между двумя заданными точками, мы можем просто взять готовое расстояние из таблицы. Результат будет получен мгновенно, но это потребует огромного объёма памяти. Карта большого города может содержать десятки тысяч точек. В данном видеоматериале мы обращаем В только на временную сложность.
Возвращение. Начнём с того, что каждое наше действие напрягает нашу ЭВМ в кой-то мере. На рисунке представлен список основных операций, занимающих 1 вымышленную единичку сложности алгоритма.
Однако эти знания нам побоку не нужны, так как когда мы пытаемся выяснить О большое, мы заботимся только о доминирующем операторе (действии) функции.
Вопрос 1. Что такое доминирующий оператор: Это такой оператор (действие), который растёт быстрее всего.
Вопрос 2. Почему мы заботимся только о доминирующем операторе?. У нас есть функция = x^5 + x + 3. При «х» равном 20 получаем = 3200000 + 20 + 3. То есть константа «3» и «х». принимающее значение 20, практически не вносят никакой вклад в результат. Пояснение на рисунке:
Заодно на нём представлено, как обозначается О. То есть для нашего примера выше сложность алгоритма О- большое (BigO) – O(x^5).
данные скопированы с разных статей на хабре и ютуб видео, лучше смотреть оригинальные источники.