Алгоритм и структура данных. 1 Базовый процедурноориентированный алгоритмический язык

• Название: 1 Базовый процедурноориентированный алгоритмический язык
• Анкор: Алгоритм и структура данных
• Дата: 03.11.2022
• Размер: 1.16 Mb.
• Имя файла: Алгоритм и структура данных.docx
• Тип: Документы; #768957
• страница: 7 из 11

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

https://techrocks.ru/2020/07/15/big-o-explanation-for-newbies/

В информатике временна́я сложность алгоритма определяется как функция от длины строки, представляющей входные данные, равная времени работы алгоритма на данном входе^[1]. Временная сложность алгоритма обычно выражается с использованием нотации «O» большое, которая учитывает только слагаемое самого высокого порядка, а также не учитывает константные множители, то есть коэффициенты. Если сложность выражена таким способом, говорят об асимптотическом описании временной сложности, то есть при стремлении размера входа к бесконечности. Например, если существует число {\displaystyle n_{0}} , такое, что время работы алгоритма для всех входов длины {\displaystyle n>n_{0}}  не превосходит {\displaystyle 5n^{3}+3n} , то временную сложность данного алгоритма можно асимптотически оценить как {\displaystyle O(n^{3})} .

O(1) -Большинство операций в программе выполняются только раз или только несколько раз. Алгоритмами константной сложности. Любой алгоритм, всегда требующий независимо от размера данных одного и того же времени, имеет константную сложность.

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

О(N²), О(N³), О(N^а) - Полиномиальная сложность.

О(N²)-квадратичная сложность, О(N³)- кубическая сложность

О(Log(N)) -Когда время работы программы логарифмическое, программа начинает работать намного медленнее с увеличением N. Такое время работы встречается обычно в программах, которые делят большую проблему в маленькие и решают их по отдельности.

O(N*log( N)) -Такое время работы имеют те алгоритмы, которые делят большую проблему в маленькие, а затем, решив их, соединяют их решения.

O(2^N) = Экспоненциальная сложность. Такие алгоритмы чаще всего возникают в результате подхода именуемого метод грубой силы.

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

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

Допустим, некоторому алгоритму нужно выполнить 4n³ + 7n условных операций, чтобы обработать n элементов входных данных. При увеличении n на итоговое время работы будет значительно больше влиять возведение n в куб, чем умножение его на 4 или же прибавление 7n. Тогда говорят, что временная сложность этого алгоритма равна О(n³), т. е. зависит от размера входных данных кубически.

Использование заглавной буквы О (или так называемая О-нотация) пришло из математики, где её применяют для сравнения асимптотического поведения функций. Формально O(f(n)) означает, что время работы алгоритма (или объём занимаемой памяти) растёт в зависимости от объёма входных данных не быстрее, чем некоторая константа, умноженная на f(n).

Примеры

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

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

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

Одной из известнейших задач в информатике является поиск значения в массиве. Мы уже решали её ранее для общего случая. Задача становится интереснее, если у нас есть отсортированный массив, в котором мы хотим найти заданное значение. Одним из способов сделать это является бинарный поиск. Мы берём средний элемент из нашего массива: если он совпадает с тем, что мы искали, то задача решена. В противном случае, если заданное значение больше этого элемента, то мы знаем, что оно должно лежать в правой части массива. А если меньше — то в левой. Мы будем разбивать эти подмассивы до тех пор, пока не получим искомое.

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

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

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

Константная сложность

Константный — O(1)

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

public int GetCount(int[] items)

{

return items.Length;

}

Линейно-логарифмическая сложность

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

В нашем примере мы взяли список из 20 элементов. Эти элементы сначала будут разбиты попарно, на 10 подсписков. И здесь вступает в игру «линейная» часть функции. Когда все элементы разбиты попарно, мы сортируем каждую отдельную пару, а затем последовательно объединяем отсортированные пары, продолжая сортировать получившийся результат. Пример алгоритма с линейно-логарифмической временной сложностью — сортировка слиянием.

Квадратичная сложность

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

Если, к примеру, в нашем наборе данных есть 2 элемента, за время работы алгоритма будет выполнено 4 операции. Если в наборе 4 элемента, то операций будет 16. При 6 элементах будет 36 операций, и так далее.

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

Вспоминаем алгоритм сортировки вставками. В классической реализации речь идёт о двух вложенных циклах. Первый нужен для прохождения по всему массиву, а второй — для нахождения места очередному элементу в отсортированной части. В результате, число операций зависит от размера массива как n * n, то есть n².

Экспоненциальная сложность

Экспоненциальная сложность или экспоненциальное время — в теории сложности алгоритмов, время решения задачи, ограниченное экспонентой от размерности задачи. Другими словами, если размерность задачи возрастает линейно, время её решения возрастает экспоненциально.

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

Хорошим примером может служить рекурсивный расчет чисел Фибоначчи — такой, как в коде, приведенном ниже.

Факториальная сложность

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

2! = 2 x 1 = 2;

3! = 3 X 2 X 1 = 6;

4! = 4 x 3 x 2 x 1 = 24;

…

8! = 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 40320;

Как видите, число операций ужасно растет при каждом добавлении элемента в набор.

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