Как оценить вычислительную сложность алгоритма

Оценка сложности алгоритмов

Введение

Для любого программиста важно знать основы теории алгоритмов, так как именно эта наука изучает общие характеристики алгоритмов и формальные модели их представления. Ещё с уроков информатики нас учат составлять блок-схемы, что, в последствии, помогает при написании более сложных задач, чем в школе. Также не секрет, что практически всегда существует несколько способов решения той или иной задачи: одни предполагают затратить много времени, другие ресурсов, а третьи помогают лишь приближённо найти решение.

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

Предлагаю в этой статье описать основные критерии оценки и привести пример оценки простейшего алгоритма. На Хабрахабре уже есть статья про методы оценки алгоритмов, но она ориентирована, в основном, на учащихся лицеев. Данную публикацию можно считать углублением той статьи.

Определения

Основным показателем сложности алгоритма является время, необходимое для решения задачи и объём требуемой памяти.
Также при анализе сложности для класса задач определяется некоторое число, характеризующее некоторый объём данных – размер входа.
Итак, можем сделать вывод, что сложность алгоритма – функция размера входа.
Сложность алгоритма может быть различной при одном и том же размере входа, но различных входных данных.

Существуют понятия сложности в худшем, среднем или лучшем случае. Обычно, оценивают сложность в худшем случае.

Временная сложность в худшем случае – функция размера входа, равная максимальному количеству операций, выполненных в ходе работы алгоритма при решении задачи данного размера.
Ёмкостная сложность в худшем случае – функция размера входа, равная максимальному количеству ячеек памяти, к которым было обращение при решении задач данного размера.

Порядок роста сложности алгоритмов

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

Шаг алгоритма – совокупность последовательно-расположенных элементарных операций, время выполнения которых не зависит от размера входа, то есть ограничена сверху некоторой константой.

Виды асимптотических оценок

O – оценка для худшего случая

Рассмотрим сложность f(n) > 0, функцию того же порядка g(n) > 0, размер входа n > 0.
Если f(n) = O(g(n)) и существуют константы c > 0, n₀ > 0, то
0 n₀.

Функция g(n) в данном случае асимптотически-точная оценка f(n). Если f(n) – функция сложности алгоритма, то порядок сложности определяется как f(n) – O(g(n)).

Данное выражение определяет класс функций, которые растут не быстрее, чем g(n) с точностью до константного множителя.

Примеры асимптотических функций

Ω – оценка для лучшего случая

Критерии оценки сложности алгоритмов

Равномерный весовой критерий (РВК) предполагает, что каждый шаг алгоритма выполняется за одну единицу времени, а ячейка памяти за одну единицу объёма (с точностью до константы).
Логарифмический весовой критерий (ЛВК) учитывает размер операнда, который обрабатывается той или иной операцией и значения, хранимого в ячейке памяти.

Временная сложность при ЛВК определяется значением l(O_p), где O_p – величина операнда.
Ёмкостная сложность при ЛВК определяется значением l(M), где M – величина ячейки памяти.

Пример оценки сложности при вычислении факториала

Необходимо проанализировать сложность алгоритма вычисление факториала. Для этого напишем на псевдокоде языка С данную задачу:

Временная сложность при равномерном весовом критерии

Достаточно просто определить, что размер входа данной задачи – n.
Количество шагов – (n — 1).

Таким образом, временная сложность при РВК равна O(n).

Временная сложность при логарифмическом весовом критерии

В данном пункте следует выделить операции, которые необходимо оценить. Во-первых, это операции сравнения. Во-вторых, операции изменения переменных (сложение, умножение). Операции присваивания не учитываются, так как предполагается, что она происходят мгновенно.

Итак, в данной задаче выделяется три операции:

Источник

Оценка сложности алгоритмов, или Что такое О(log n)

Наверняка вы не раз сталкивались с обозначениями вроде O(log n) или слышали фразы типа «логарифмическая вычислительная сложность» в адрес каких-либо алгоритмов. И если вы хотите стать хорошим программистом, но так и не понимаете, что это значит, — данная статья для вас.

Оценка сложности

Сложность алгоритмов обычно оценивают по времени выполнения или по используемой памяти. В обоих случаях сложность зависит от размеров входных данных: массив из 100 элементов будет обработан быстрее, чем аналогичный из 1000. При этом точное время мало кого интересует: оно зависит от процессора, типа данных, языка программирования и множества других параметров. Важна лишь асимптотическая сложность, т. е. сложность при стремлении размера входных данных к бесконечности.

Примеры

O(n) — линейная сложность

Такой сложностью обладает, например, алгоритм поиска наибольшего элемента в не отсортированном массиве. Нам придётся пройтись по всем n элементам массива, чтобы понять, какой из них максимальный.

O(log n) — логарифмическая сложность

Простейший пример — бинарный поиск. Если массив отсортирован, мы можем проверить, есть ли в нём какое-то конкретное значение, методом деления пополам. Проверим средний элемент, если он больше искомого, то отбросим вторую половину массива — там его точно нет. Если же меньше, то наоборот — отбросим начальную половину. И так будем продолжать делить пополам, в итоге проверим log n элементов.

O(n 2 ) — квадратичная сложность

27–29 декабря, Онлайн, Беcплатно

Бывают и другие оценки по сложности, но все они основаны на том же принципе.

Аналогично проводят оценку и по памяти, когда это важно. Однако алгоритмы могут использовать значительно больше памяти при увеличении размера входных данных, чем другие, но зато работать быстрее. И наоборот. Это помогает выбирать оптимальные пути решения задач исходя из текущих условий и требований.

Наглядно

Время выполнения алгоритма с определённой сложностью в зависимости от размера входных данных при скорости 10 6 операций в секунду:

Тут можно посмотреть сложность основных алгоритмов сортировки и работы с данными.

Если хочется подробнее и сложнее, заглядывайте в нашу статью из серии «Алгоритмы и структуры данных для начинающих».

Источник

Сложность алгоритмов. Big O. Основы.

Развитие технологий привело к тому, что память перестала быть критическим ресурсом. Поэтому когда говорят об анализе сложности алгоритма, обычно подразумевают то, насколько быстро он работает.

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

Big O показывает верхнюю границу зависимости между входными параметрами функции и количеством операций, которые выполнит процессор.

Распространённые сложности алгоритмов

Здесь рассмотрены именно распространённые виды, так как рассмотреть все варианты врядли возможно. Всё зависит от алгоритма, который вы оцениваете. Всегда может появится какая-то дополнительная переменная (не константа), которую необходимо будет учесть в функции Big O.

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

Пример № 1.

У нас есть массив из 5 чисел и нам надо получить первый элемент.

Насколько возрастет количество операций при увеличении размера входных параметров?
Нинасколько. Даже если массив будет состоять из 100, 1000 или 10 000 элементов нам всеравно потребуется одна операция.

Пример № 2.

Сложение двух чисел. Функция всегда выполняет константное количество операций.

Пример № 3.

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

Означает, что сложность алгоритма линейно растёт с увеличением входных данных. Другими словами, удвоение размера входных данных удвоит и необходимое время для выполнения алгоритма.

Такие алгоритмы легко узнать по наличию цикла по каждому элементу массива.

Пример № 3.

Означает, что сложность алгоритма растёт логарифмически с увеличением входных данных. Другими словами это такой алгоритм, где на каждой итерации берётся половина элементов.

К алгоритмам с такой сложностью относятся алгоритмы типа “Разделяй и Властвуй” (Divide and Conquer), например бинарный поиск.

Означает, что удвоение размера входных данных увеличит время выполнения чуть более, чем вдвое.

Примеры алгоритмов с такой сложностью: Сортировка слиянием или множеством n элементов.

Означает, что удвоение размера входных данных увеличивает время выполнения в 4 раза. Например, при увеличении данных в 10 раз, количество операций (и время выполнения) увеличится примерно в 100 раз. Если алгоритм имеет квадратичную сложность, то это повод пересмотреть необходимость использования данного алгоритма. Но иногда этого не избежать.

Такие алгоритмы легко узнать по вложенным циклам.

Пример № 1.

В функции есть цикл в цикле, каждый из них проходит массив длиной n, следовательно сложность будет: O(n * n) = O(n 2 )

Зачем изучать Big O

Шпаргалка

Небольшие подсказки, которые помогут определить сложность алгоритма.

Полезные ссылки

Источник

Анализ сложности алгоритмов. Примеры

Алгоритм — это точное предписание, однозначно определяющее вычислительный процесс, ведущий от варьируемых начальных данных к искомому результату [1].

При разработке алгоритмов очень важно иметь возможность оценить ресурсы, необходимые для проведения вычислений, результатом оценки является функция сложности (трудоемкости). Оцениваемым ресурсом чаще всего является процессорное время (вычислительная сложность) и память (сложность алгоритма по памяти). Оценка позволяет предсказать время выполнения и сравнивать эффективность алгоритмов.

Содержание:

Модель RAM (Random Access Machine)

Каждое вычислительное устройство имеет свои особенности, которые могут влиять на длительность вычисления. Обычно при разработке алгоритма не берутся во внимание такие детали, как размер кэша процессора или тип многозадачности, реализуемый операционной системой. Анализ алгоритмов проводят на модели абстрактного вычислителя, называемого машиной с произвольным доступом к памяти (RAM).

Модель состоит из памяти и процессора, которые работают следующим образом:

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

Подсчет операций. Классы входных данных

Одним из способов оценки трудоемкости (\(T_n\)) является подсчет количества выполняемых операций. Рассмотрим в качестве примера алгоритм поиска минимального элемента массива.

При выполнении этого алгоритма будет выполнена:

Точное количество операций будет зависеть от обрабатываемых данных, поэтому имеет смысл говорить о наилучшем, наихудшем и среднем случаях. При этом худшему случаю всегда уделяется особое внимание, в том числе потому, что «плохие» данные могут быть намеренно поданы на вход злоумышленником.

Понятие среднего случая используется для оценки поведения алгоритма с расчетом на то, что наборы данных равновероятны. Однако, такая оценка достаточно сложна:

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

Подсчет количества операций позволяет сравнить эффективность алгоритмов. Однако, аналогичный результат можно получить более простым путем. Анализ проводят с расчетом на достаточно большой объем обрабатываемых данных (\( n \to \infty \)), поэтому ключевое значение имеет скорость роста функции сложности, а не точное количество операций.

При анализе скорости роста игнорируются постоянные члены и множители в выражении, т.е. функции \(f_x = 10 \cdot x^2 + 20 \) и \( g_x = x^2\) эквивалентны с точки зрения скорости роста. Незначащие члены лишь добавляют «волнистости», которая затрудняет анализ.

В оценке алгоритмов используются специальные асимптотические обозначения, задающие следующие классы функций:

Запись \(f_n = \mathcal(g_n)\) означает принадлежность функции f классу \(\mathcal(g)\), т.е. функция f ограничена сверху функцией g для достаточно больших значений аргумента. \(\exists n_0 > 0, c > 0 : \forall n > n_0, f_n \leq c \cdot g_n\).

Ограниченность функции g снизу функцией f записывается следующим образом: \(g_n =\Omega(f_n)\). Нотации \(\Omega\) и \(\mathcal\) взаимозаменяемы: \(f_n = \mathcal(g_n) \Leftrightarrow g_n =\Omega(f_n)\).

Асимптотические обозначения «О большое» и «Омега большое»

Если функции f и g имеют одинаковую скорость роста (\(f_n = \Theta(g_n)\)), то существуют положительные константы \(c_1\) и \(c_2\) такие, что \(\exists n_0 > 0 : \forall n > n_0, f_n \leq c_1 \cdot g_n, f_n \geq c_2 \cdot g_n\). При этом \(f_n = \Theta(g_n) \Leftrightarrow g_n = \Theta(f_n)\).

Асимптотическое обозначение «Тета большое»

Примеры анализа алгоритмов

Алгоритм поиска минимального элемента массива, приведенный выше, выполнит N итераций цикла. Трудоемкость каждой итерации не зависит от количества элементов массива, поэтому имеет сложность \(T^ = \mathcal(1)\). В связи с этим, верхняя оценка всего алгоритма \(T^_n = \mathcal(n) \cdot \mathcal(1) = \mathcal(n \cdot 1) = \mathcal(n)\). Аналогично вычисляется нижняя оценка сложности, а в силу того, что она совпадает с верхней — можно утверждать \(T^_n = \Theta(n) \).

Алгоритм пузырьковой сортировки (bubble sort) использует два вложенных цикла. Во внутреннем последовательно сравниваются пары элементов и если оказывается, что элементы стоят в неправильном порядке — выполняется перестановка. Внешний цикл выполняется до тех пор, пока в массиве найдется хоть одна пара элементов, нарушающих требуемый порядок [2].

Трудоемкость функции swap не зависит от количества элементов в массиве, поэтому оценивается как \(T^ = \Theta(1) \). В результате выполнения внутреннего цикла, наибольший элемент смещается в конец массива неупорядоченной части, поэтому через N таких вызовов массив в любом случае окажется отсортирован. Если же массив отсортирован, то внутренний цикл будет выполнен лишь один раз.

В алгоритме сортировки выбором массив мысленно разделяется на упорядоченную и необработанную части. На каждом шаге из неупорядоченной части массива выбирается минимальный элемент и добавляется в отсортированную часть [2].

Для поиска наименьшего элемента неупорядоченной части массива используется функция indMin, принимающая массив, размер массива и номер позиции, начиная с которой нужно производить поиск. Анализ сложности этой функции можно выполнить аналогично тому, как это сделано для функции min — количество операций линейно зависит от количества обрабатываемых элементов: \( T^_ = \Theta(n — i)\).

У сортировки выбором нет ветвлений, которые могут внести различия в оценку наилучшего и наихудшего случаев, ее трудоемкость: \(T^_n = \Theta(\sum\limits_^ (T^_ + T^)) =\Theta(\sum\limits_^ (n-i)) = \Theta(\frac <2>\cdot n) = \Theta(n^2) \).

Математический аппарат анализа алгоритмов

Выше были рассмотрены асимптотические обозначения, используемые при анализе скорости роста. Они позволяют существенно упростить задачу отбросив значительную часть выражения. Однако, в математическом анализе имеется целый ворох таких приемов.

Формулы суммирования

В примерах, рассмотренных выше, мы уже сталкивались с нетривиальными формулами суммирования. Чтобы дать оценку суммы можно использовать ряд известных тождеств:

Первые из этих тождеств достаточно просты, их можно вывести используя метод математической индукции. Если под знаком суммы стоит более сложная формула, как в двух последних тождествах — суммирование можно заменить интегрированием (взять интеграл функции гораздо проще, ведь для этого существует широкий спектр приемов).

Суммирование и интегрирование

Известно, что интеграл можно понимать как площадь фигуры, размещенной под графиком функции. Существует ряд методов аппроксимации (приближенного вычисления) интеграла, к ним относится, в частности, метод прямоугольников. Площадь под графиком делится на множество прямоугольников и приближенно вычисляется как сумма их площадей. Следовательно, возможен переход от интеграла к сумме и наоборот.

аппроксимация интеграла левыми прямоугольниками

аппроксимация интеграла правыми прямоугольниками

На рисунках приведен пример аппроксимации функции \(f_x = \log x\) левыми и правыми прямоугольниками. Очевидно, они дадут верхнюю и нижнюю оценку площади под графиком:

В частности, такой метод позволяет оценить алгоритмы, имеющие логарифмическую сложность (две последние формулы суммирования).

Сравнение сложности алгоритмов. Пределы

Сложность алгоритмов определяется для больших объемов обрабатываемых данных, т.е. при \(n\to\infty\). В связи с этим, при сравнении трудоемкости двух алгоритмов можно рассмотреть предел отношения функций их сложности: \(\lim\limits_ \frac \). В зависимости от значения предела возможно сделать вывод относительно скоростей роста функций:

Если функции достаточно сложны, то такой прием значительно упрощает задачу, т.к. вместо предела отношения функций можно анализировать предел отношения их производных (согласно правилу Лопиталя): \(\lim\limits_ \frac = \lim\limits_ \frac \). Правило Лопиталя можно использовать если функции обладают следующими свойствами:

Допустим, требуется сравнить эффективность двух алгоритмов с оценками сложности \(\mathcal(a^n)\) и \(\mathcal(n^b)\), где a и b — константы. Известно, что \((c^x)’ =c^x \cdot ln(c)\), но \((x^c)’ = c \cdot x^ \). Применим правило Лопиталя к пределу отношения наших функций b раз, получим: \(\lim\limits_ \frac <\mathcal(a^n)><\mathcal(n^b)> = \lim\limits_ \frac <\mathcal(a^n * ln^b (a))><\mathcal(b!)> = \infty\). Значит функция \(a^n\) имеет более высокую скорость роста. Без использования пределов и правила Лопиталя такой вывод может казаться не очевидным.

Логарифмы и сложность алгоритмов. Пример

По определению \(\log_a = b \Leftrightarrow x = a^b\). Необходимо знать, что \(x \to \infty \Rightarrow \log_a \to \infty\), однако, логарифм — это очень медленно растущая функция. Существует ряд формул, позволяющих упрощать выражения с логарифмами:

При анализе алгоритмов обычно встречаются логарифмы по основанию 2, однако основание не играет большой роли, поэтому зачастую не указывается. Последняя формула позволяет заменить основание логарифма, домножив его на константу, но константы отбрасываются при асимптотическом анализе.

Логарифмической сложностью обладают алгоритмы, для которых не требуется обрабатывать все исходные данные, они используют принцип «разделяй и властвуй». На каждом шаге часть данных (обычно половина) отбрасывается. Примером может быть функция поиска элемента в отсортированном массиве (двоичного поиска):

Очевидно, что на каждом шаге алгоритма количество рассматриваемых элементов сокращается в 2 раза. Количество элементов, среди которых может находиться искомый, на k-том шаге определяется формулой \(\frac<2^k>\). В худшем случае поиск будет продолжаться пока в массиве не останется один элемент, т.е. чтобы определить количество итераций для верхней оценки, достаточно решить уравнение \(1 = \frac <2^k>\Rightarrow 2^i = n \Rightarrow i = \log_2 n\). Следовательно, алгоритм имеет логарифмическую сложность: \(T^_n = \mathcal(\log n)\).

Результаты анализа. Замечания. Литература

Оценка сложности — замечательный способ не только сравнения алгоритмов, но и прогнозирования времени их работы. Никакие тесты производительности не дадут такой информации, т.к. зависят от особенностей конкретного компьютера и обрабатывают конкретные данные (не обязательно худший случай).

Анализ алгоритмов позволяет определить минимально возможную трудоемкость, например:

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

Источник

Алгоритмы (теория/практика): Часть 3. Сложность алгоритмов

Ни для кого не секрет, что одни и те же задачи можно решить разными способами. Вот, например, задача поиска какого-то значения в массиве. Что приходит на ум в первую очередь? Ну, например, можно перебирать каждое значение и сравнивать его с искомым. Если оно есть, но мы возвращаем позицию этого элемента или сообщаем о том, что такого элемента нет. Подобный способ часто называют линейным поиском. Не самый лучший вариант, особенно, если учитывать, что искомое значение преспокойно может существовать себе в конце массива. Если массив небольшой, то особых проблем не будет. Но что, если его длина исчисляется сотнями, тысячами, миллионами?

Можно поступить мудрее. Вы наверняка слышали о чем-то, что называют двоичным или бинарным поиском. Название отражает его основную суть – поиск выполняется путем разбиения массива на два подмассива за каждый шаг. Давайте рассмотрим на примере.

Примечание: массив — структура данных в виде набора компонентов (элементов массива), расположенных в памяти непосредственно друг за другом (Википедия). Время обращения к конкретному элементу в массиве является константой. Количество элементов в массиве определяют его размер (не путать с размерностью). Мы подробно будем изучать структуры данных, а пока достаточно будет этого определения.

Предположим, что мы имеем массив чисел от 0 до 7. Также предположим, что наш массив отсортирован – это условие очень важно, в противном случае двоичный поиск будет нереализуем.

Искомое значение: 6. Поехали.

При помощи алгоритма линейного поиска мы будем сравнивать каждое число с искомым и найдем его позицию в массиве через 7 шагов. Ну что же, неплохо. Но чем нас порадует двоичный поиск?

Как я уже упомянул, его суть сводится к разбиению основного массива на две части на каждом шаге. Давайте подробно его разберем.

Итого, 4 шага мы сделали для того, чтобы отыскать значение при помощи алгоритма двоичного поиска.

4 против 7. Прогресс налицо. Кто-то заметит, что время выполнения алгоритма линейного поиска неоднозначно. Ведь искомое значение может находиться и на первом месте, верно? Тогда двоичный поиск будет в роли догоняющего.

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

Для того, чтобы сравнить эффективность двух разных алгоритмов, введём определение вычислительной сложности алгоритма. Вычислительная сложность – это функция зависимости объема работы, которое нужно сделать исполнителю, от размера входных данных.

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

Например, если у нас есть массив из 8 элементов, то количество сравнений будет равно 4. Массиву из 16 элементов уже потребуется 5 сравнений. И эта зависимость как раз и выражается функцией, что носит название «вычислительная сложность». В дальнейшем будет обозначать её как \(f\left( n \right)\), где \(n\)-размер входных данных.

Модель RAM (Random Access Memory)

Для простоты и однозначности определения такой «элементарной операции» будем использовать модель RAM. То есть, как известно, время исполнения одних и тех же алгоритмов на разных машинах может очень сильно разниться, что совсем нам не подходит. Поэтому мы будем работать с абстрактной RAM-машиной (машина с произвольным доступом к памяти), которая обладает бесконечной памятью, состоящей из ячеек, имеющих свой уникальный адрес, и работает следующим образом:

В результате анализа мы получим значение, которое является суммой всех элементарных операций, проделанных алгоритмом, затем опишем его с помощью обозначений.

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

Давайте сначала рассмотрим именно их, а уже потом будем сравнивать на примере реальных алгоритмов. Согласны? Ну а куда же вы денетесь.

\(\Theta\)-обозначения

Буква читается как «тета». При помощи данного обозначения можно охарактеризовать асимптотически точную оценку сложности алгоритма. Что я имею в виду? Запись \(f\left( n \right)=\Theta (g\left( n \right))\) означает, что существуют положительные константы \(< c >_< 1 >\), \(< c >_< 2 >\) и \(< n >_< 0 >\) такие, что

Самое время немного снизить скорость и разобрать всё, что мы сейчас узнали. Запись выше означает, что мы можем найти такую функцию \(g\left( n \right)\), которая бы ограничивала нашу функцию \(f\left( n \right)\) сверху и снизу для всех \(n\ge < n >_< 0 >\).

Допустим, некоторый алгоритм работает с вычислительной сложностью \(< n >^< 2 >-3\). Предположим, что асимптотической оценкой может служить функция \(< n >^< 2 >\) (пока просто предполагаем, я научу находить правильную оценку). Есть ли такие константы? Ну, \(< c >_< 2 >\), очевидно есть:

Запись \(n>2\) означает, что константа \(< n >_< 0 >=3\). \(< n >_< 0 >\) – целое число, справа от которого на графике \(f\left( n \right)\) всегда лежит между \(< c >_< 1 >g\left( n \right)\) и \(< c >_< 2 >g\left( n \right)\).

Так вот, если такое условие выполняется, то мы можем с полной уверенностью заявить, что \(g\left( n \right)\) является асимптотически точной оценкой функции \(f\left( n \right)\). В нашем случае \(< n >^< 2 >\) является асимптотически точной оценкой \(< n >^< 2 >-3\), или это можно записать так:

Справедливый вопрос – а почему нельзя за \(g\left( n \right)\) взять просто \(< n >^< 2 >-3\)? На самом деле можно, но не имеет смысла. И об этом я тоже расскажу. Всё по порядку.

Примечание: \(\Theta (g\left( n \right))\) обозначает множество функций, поэтому можно также писать \(f\left( n \right)\in\Theta (g\left( n \right))\). В какой-то степени это даже правильнее, но мы при работе будем использовать знак равенства.

\(O\)-обозначения и \(\Omega\)-обозначения

«О» большое и «Омега» большое.

Теперь, после того, как мы познакомились с \(\Theta\)-обозначения, добавим к нему еще два. Итак,
Запись \(f\left( n \right)=O (g\left( n \right))\) означает, что существуют положительные константы \(c\) и \(< n >_< 0 >\) такие, что

Вы могли догадаться, что при помощи \(O\)-обозначения мы можем описать асимптотически верхнюю границу сложности алгоритма. То есть при помощи данного обозначение можно охарактеризовать максимальную сложность алгоритма, максимальное время работы. Вкладывайте в это любой смысл, суть же, я думаю, ясна. Довольно полезно, не так ли? Это еще не все.

Теперь дальше. Запись \(f\left( n \right)=\Omega (g\left( n \right))\) означает, что существуют положительные константы \(c\) и \(< n >_< 0 >\) такие, что

Догадались? Ну точно, \(\Omega\)-обозначение помогает нам описать асимптотически нижнюю границу. Минимальная вычислительная сложность, минимальное время, которое алгоритм гарантированно затратит на выполнение.

Давайте визуализируем всё то, что я написал до этого. На графиках я изобразил функции \(< n >^< 2 >-3\) и \(< n >^< 2 >\) (с соответствующими константами) для всех \(n>0\) (размер входных данных не может быть отрицательным числом).

» data-medium-file=»https://i2.wp.com/blog.underpowered.net/wp-content/uploads/2017/12/TETA.png?fit=300%2C159&ssl=1″ data-large-file=»https://i2.wp.com/blog.underpowered.net/wp-content/uploads/2017/12/TETA.png?fit=640%2C340&ssl=1″ src=»https://i2.wp.com/blog.underpowered.net/wp-content/uploads/2017/12/TETA.png?resize=640%2C340&ssl=1″ alt=»TETA» width=»640″ height=»340″ srcset=»https://i2.wp.com/blog.underpowered.net/wp-content/uploads/2017/12/TETA.png?w=1718&ssl=1 1718w, https://i2.wp.com/blog.underpowered.net/wp-content/uploads/2017/12/TETA.png?resize=300%2C159&ssl=1 300w, https://i2.wp.com/blog.underpowered.net/wp-content/uploads/2017/12/TETA.png?resize=768%2C408&ssl=1 768w, https://i2.wp.com/blog.underpowered.net/wp-content/uploads/2017/12/TETA.png?resize=1024%2C544&ssl=1 1024w, https://i2.wp.com/blog.underpowered.net/wp-content/uploads/2017/12/TETA.png?w=1280&ssl=1 1280w» sizes=»(max-width: 640px) 100vw, 640px» data-recalc-dims=»1″ />

» data-medium-file=»https://i0.wp.com/blog.underpowered.net/wp-content/uploads/2017/12/OBIG.png?fit=300%2C159&ssl=1″ data-large-file=»https://i0.wp.com/blog.underpowered.net/wp-content/uploads/2017/12/OBIG.png?fit=640%2C340&ssl=1″ src=»https://i0.wp.com/blog.underpowered.net/wp-content/uploads/2017/12/OBIG.png?resize=640%2C340&ssl=1″ alt=»OBIG» width=»640″ height=»340″ srcset=»https://i0.wp.com/blog.underpowered.net/wp-content/uploads/2017/12/OBIG.png?w=1718&ssl=1 1718w, https://i0.wp.com/blog.underpowered.net/wp-content/uploads/2017/12/OBIG.png?resize=300%2C159&ssl=1 300w, https://i0.wp.com/blog.underpowered.net/wp-content/uploads/2017/12/OBIG.png?resize=768%2C408&ssl=1 768w, https://i0.wp.com/blog.underpowered.net/wp-content/uploads/2017/12/OBIG.png?resize=1024%2C544&ssl=1 1024w, https://i0.wp.com/blog.underpowered.net/wp-content/uploads/2017/12/OBIG.png?w=1280&ssl=1 1280w» sizes=»(max-width: 640px) 100vw, 640px» data-recalc-dims=»1″ />

» data-medium-file=»https://i2.wp.com/blog.underpowered.net/wp-content/uploads/2017/12/OMEGABIG.png?fit=300%2C159&ssl=1″ data-large-file=»https://i2.wp.com/blog.underpowered.net/wp-content/uploads/2017/12/OMEGABIG.png?fit=640%2C340&ssl=1″ src=»https://i2.wp.com/blog.underpowered.net/wp-content/uploads/2017/12/OMEGABIG.png?resize=640%2C340&ssl=1″ alt=»OMEGABIG» width=»640″ height=»340″ srcset=»https://i2.wp.com/blog.underpowered.net/wp-content/uploads/2017/12/OMEGABIG.png?w=1718&ssl=1 1718w, https://i2.wp.com/blog.underpowered.net/wp-content/uploads/2017/12/OMEGABIG.png?resize=300%2C159&ssl=1 300w, https://i2.wp.com/blog.underpowered.net/wp-content/uploads/2017/12/OMEGABIG.png?resize=768%2C408&ssl=1 768w, https://i2.wp.com/blog.underpowered.net/wp-content/uploads/2017/12/OMEGABIG.png?resize=1024%2C544&ssl=1 1024w, https://i2.wp.com/blog.underpowered.net/wp-content/uploads/2017/12/OMEGABIG.png?w=1280&ssl=1 1280w» sizes=»(max-width: 640px) 100vw, 640px» data-recalc-dims=»1″ />

Внимательность: Описанные выше обозначения можно связать с помощью следующего утверждения:

Два последних обозначения, что мы рассмотрели, имеют определенные проблемы. Например, утверждение, что \(< n >^< 2 >=O (< n >^< 8 >)\) верное, исходя из определения O-обозначения, проверьте сами. Тем не менее, это не является точной оценкой верхней границы. Так вот, для того, чтобы показать, что данная оценка является неточной, существуют еще два обозначения.

\(o\)-обозначения и \(\omega\)-обозначения

«О» малое и «Омега» малое.

Как уже было сказано, o-обозначения используют для неточной оценки. Давайте рассмотрим чуть более формально:

Запись \(f\left( n \right)=o (g\left( n \right))\) означает, что для любой константы \(c>0\) существует константа \(< n >_< 0 >>0\) такая,что

Главное различие \(O\)-обозначения и \(o\)-обозначения заключается в том, что в первом случае неравенство справедливо лишь для некоторой константы \(c\), во втором же – для всех \(c>0\).

Не теряем ни секунды. Запись \(f\left( n \right)=\omega (g\left( n \right))\) означает, что для любой константы \(c>0\) существует константа \(< n >_< 0 >>0\) такая,что

То же самое, неравенство в этом случае справедливо для всех \(c>0\).

Как вы поняли, \(o\)-обозначения и \(\omega\)-обозначения характеризуют неточные верхнюю и нижнюю оценку. Ситуации, в которых нужно применять именно их, мы рассмотрим позже.

Порядок роста

Теперь давайте предположим, что есть некоторый алгоритм, который выполняется за количество шагов, описываемое следующей функцией:

При описании сложности алгоритма, нас интересует лишь то, как именно растёт время работы алгоритма при увеличении его сложности. Конечно, можно было бы взять и написать, что \(f\left( n \right) =\Theta (< n >^< 2 >+n)\) и по определению это было бы абсолютно верно. Тем не менее, при выборе функции, используется лишь тот член, который оказывает наибольшее влияние на рост, остальные же члены отбрасываются. Также отбрасываются и множители, которые на зависят от входных данных. Например, в записи \(2< n >^< 2 >\) мы с чистой совестью можем избавиться от множителя 2.

Еще раз внимательно взглянем на функцию. Можно показать, что при n, стремящимся к бесконечности:

При бесконечно больших \(n\), функция \(f\left( n \right)=n\) будет пренебрежимо мала по сравнению с \(f\left( n \right) =< n >^< 2 >\).

Давайте рассмотрим более доступный пример. Допустим, \(n=65536\) (с такими числами получается убедительнее). Время выполнения алгоритма в этом случае составит \(< 65536 >^< 2 >+65536=4295032832\). Число внушительное, но если мы посмотрим, то увидим, что член \(< n >^< 2 >\) оказывает наибольшее влияние на рост значения:

Вклад члена \(n\) в общее время выполнения алгоритма составляет примерно две стотысячные, что является слишком незначительным числом для того, чтобы учитывать его.

В свою же очередь, \(< n >^< 2 >\) имеет наибольший порядок роста в многочлене \(< n >^< 2 >+n\), поэтому именно его мы берём в качестве описания вычислительной сложности алгоритма.

Всё еще сомневаетесь? Хорошо, предположим, что время выполнения алгоритма задается следующей функцией:

У второго слагаемого появился серьезный шанс на победу.

Что же, выходит, всё то, что я написал, не имеет смысла? На самом деле, имеет. Увеличим \(n\) еще в 65536 раз. Дабы не утомлять вас большими числами, приведу просто соотношение:

При достаточно большом \(n\), слагаемое \(< n >^< 2 >\) всё равно имеет больший вклад в общее время.

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

Источник

• ← Как оценить время на тестирование
• Как оценить вязаное вручную изделие →

Вам также понравится

как синхронизировать телефон с айфоном

12.01.202313.01.2023 admin 0

Морфологическая верификация легких как проводится

13.01.202319.01.2023 admin 0

Как выделить персонажа на фоне

11.12.202213.12.2022 admin 0

Добавить комментарий Отменить ответ

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Комментарий *

Имя *

Email *

Сохранить моё имя, email и адрес сайта в этом браузере для последующих моих комментариев.