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

Объяснение временной сложности итерационных алгоритмов от нуля до героя.

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

• Скорость компьютера (аппаратная).
• Используемый язык программирования (Java, C++, Python).
• Компилятор, который переводит наш код в машинный код (Clang, GCC, Min GW).

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

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

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

В приведенном выше определении «время» не означает время настенных часов, а в основном означает, как количество операций, выполняемых алгоритмом, растет по мере увеличения размера входных данных. Операции — это шаги, выполняемые алгоритмом для данного входа.

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

• Присвоение значений переменным.
• Сравнивать.
• Выполнение арифметических действий.
• Доступ к объектам из памяти.

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

Вычисление временной сложности линейного поиска

Линейный поиск — простейший алгоритм поиска элемента x в array. Он проверяет каждый value в массиве и сравнивает его с element, который нужно искать, пока не найдет совпадение, начиная с самого начала. Поиск завершается и прекращается, когда целевой элемент находится.

В приведенном выше примере массив имеет 8 значений 1,2,3,4,5,6,7,8. Предположим, мы хотим найти элемент 8, алгоритм сравнивает 8 с каждым элементом array, пока не найдет совпадение. Как только он находит совпадение, возвращается индекс 8, который равен 7, иначе предположим, что если 9 не было в array, тогда будет возвращен -1.

Реализация кода линейного поиска

Приведенный выше фрагмент кода представляет собой функцию линейного поиска, которая принимает array, size массива и искомый элемент x.

Анализ временной сложности

При выполнении алгоритма линейного поиска вы столкнетесь с тремя различными сложностями.

Они есть:

1. Лучший случай
2. Худший случай
3. Средний случай

В лучшем случае

Если искомый элемент находится в первой позиции массива, то в этом случае поиск завершится одним успешным сравнением. В лучшем случае алгоритм выполняет O(1) операций. O (Big-Oh — это обозначение, используемое для представления временной сложности).

Худший случай

Если искомый элемент находится в последней позиции массива или вообще не найден. Затем выполняется поиск n сравнений. Таким образом, в худшем случае алгоритм выполняет O(n) операций.

Средний случай

Если искомый элемент находится в середине массива, среднее количество сравнений равно n/2. Таким образом, в среднем сценарии он выполняет O(n). Мы игнорируем константу 1/2, мы поймем, почему мы игнорируем константы при изучении асимптотической записи.

Вычисление временной сложности бинарного поиска

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

Например, если в массиве 10 элементов, то неверное предположение сократит массив до 5 элементов.

В приведенном выше примере у нас есть массив с восемью значениями1,2,3,4,5,6,7,8 и искомым элементом является 8.

• На первом этапе средний элемент массива вычисляется с помощью (0+7)/2=3,, затем он сравнивает средний элемент 4 с 8.
• Если элемент поиска 8 больше среднего элемента 4. Затем ищется правая половина.
• Если элемент поиска 8 меньше среднего элемента 4. Затем обыскивается левая половина.
• Эти шаги повторяются до тех пор, пока не будет найден элемент поиска 8 или не будет выполнено условие L>H, указывающее, что элемент не найден, и возвращается -1.

Кодовая реализация бинарного поиска

Приведенный выше фрагмент кода представляет собой функцию бинарного поиска, которая принимает array, size массива и искомый элемент x.

Примечание. Чтобы предотвратить целочисленное переполнение, мы используем формулу M=L+(H-L)/2 для вычисления среднего элемента вместо M=(H+L)/2.

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

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

Анализ временной сложности бинарного поиска

В лучшем случае

Наилучшая временная сложность бинарного поиска — это когда элемент поиска находится в середине массива. Тогда количество сравнений будет O(1).

Средний случай

Средняя временная сложность определяется, когда элемент поиска находится в массиве, а временная сложность будет равна O(logN).

Худший случай

В худшем случае элемент поиска не находится в массиве или найден на последней итерации бинарного поиска. Временная сложность будет O(logN).

Сравнение бинарного поиска и линейного поиска

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

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

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

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

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

Предположим, что алгоритмы, работающие на входе размера n, требуют 3 n²+100 n+300 машинных инструкций. Затем член 3 n² становится значительно больше, когда значение n становится достаточно большим. Мы можем игнорировать члены 100 n + 300 из уравнения.

Далее мы можем отбросить коэффициент 3 из 3 n² и сказать, что время работы алгоритма равно n² вместо точных 3 n²+100 n+300. На самом деле не имеет значения, какие менее значимые термины и какой коэффициент мы используем. Можно сказать, что после отбрасывания всех ненужных терминов временная сложность равна n². Асимптотическая запись - это метод отбрасывания всех менее значимых и постоянных коэффициентов.

Асимптотическая запись имеет три формы: большая тета, большая омега и большая нотация.

Краткое определение асимптотической записи

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

Существует три формы асимптотических обозначений

1. Большой О (Большой О)
2. Большой Ω (Большой Омега)
3. Большой Θ (Большой тета)

Обозначение Big-Oh

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

Математическое определение Big-Oh

f(n) ∈ O(g(n)) тогда и только тогда, когда существуют некоторая положительная константа c и некоторое неотрицательное целое число n₀ такие, что f(n) ⩽ c g(n) для всех n ≥ n₀, n₀ ≥ 1 и с›0.

В приведенном выше определении говорится, что в наихудшем случае пусть функция f(n) будет средой выполнения вашего алгоритма, а g(n) будет произвольной временной сложностью, которую вы пытаетесь связать со своим алгоритмом. Затем O(g(n)) говорит, что функция f(n) никогда не растет быстрее, чем g(n), то есть f(n)<=g(n), а g(n) — это максимальное число шагов, которое может достичь алгоритм.

На приведенном выше графике c.g(n) — это функция, которая дает максимальное время выполнения (верхняя граница), а f(n) — это время выполнения алгоритма.

Примеры нотации Big-O

Обозначение большой омеги

Большая омега — это асимптотическая запись для наилучшего случая сценария. Что является минимальным роста для данной функции. Он дает нам так называемую асимптотическую нижнюю границу скорости роста алгоритма.

Математическое определение большой омеги

f(n) ∈ Ω(g(n)) тогда и только тогда, когда существуют некоторая положительная константа c и некоторое неотрицательное целое число n₀ такие, что f(n) ≥ c g(n) для всех n ≥ n₀, n₀ ≥ 1 и с›0.

В приведенном выше определении говорится, что в наилучшем случае пусть функция f(n)будет средой выполнения вашего алгоритма, а g(n) будет произвольной временной сложностью, которую вы пытаетесь связать со своим алгоритмом. Тогда Ω(g(n)) говорит о том, что функция g(n)никогда не растет больше, чем f(n)т.е. f(n)>=g(n), g(n)указывает минимальное количество шагов, которое будет выполнять алгоритм.

На приведенном выше графике c.g(n)это функция, которая дает минимальное время выполнения (нижняя граница), а f(n)это время выполнения алгоритма.

Примеры записи Big-Ω

Обозначение Big-Theta

Big Theta – это асимптотическая запись для среднего случая, которая дает средний рост для данной функции. Тета-нотация всегда между нижней и верхней границей. Он дает нам то, что называется асимптотической средней границей скорости роста алгоритма. Если верхняя и нижняя границы функции дают одинаковый результат, то запись Θ также будет иметь одинаковую скорость роста.

Математическое определение Big-Theta

f (n) ∈ Θ (g (n)) тогда и только тогда, когда существуют некоторая положительная константа c₁ и c₂ некоторое неотрицательное целое число n₀ такое, что c₁ g (n) ≤ f (n) ≤ c₂ g (n) для все n ≥ n₀, n₀ ≥ 1 и c›0.

В приведенном выше определении говорится, что в среднем случае пусть функция f(n)будет временем выполнения вашего алгоритма, а g(n)будет произвольной временной сложностью, которую вы пытаетесь связать со своим алгоритмом. Затем Θ(g(n)) говорит, что функция g(n)закрывает функцию f(n)сверху и снизу, используя c1.g(n) и c2.g(n).

На приведенном выше графике c1.g(n)и c2.g(n)заключают функцию f(n). Это обозначение Θ определяет реальную временную сложность алгоритма.

Примеры записи Big-Θ

Расчет временной сложности для следующих алгоритмов

Мы будем определять различную временную сложность алгоритмов с точки зрения нотации big O, мы будем использовать Big-O, потому что это так что мы должны быть обеспокоены. Алгоритмы в основном тестируются для наихудшего случая сценария.

Пример 1: Циклы

Время выполнения цикла кратно операторам внутри цикла на количество итераций.

Общее время = константа c × n = c n = O(n)

Пример 2: вложенные циклы

Общее время работы этого алгоритма равно произведению размеров всех циклов.

Общее время = c × n × n = cn² = O(n²)

Пример 3: последовательные операторы

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

Общее время = c₀ + c₁n + c₂n² = O(n²)

Пример 4: Логарифмическая сложность

Если мы наблюдаем, что значение iit удваивается на каждой итерации i=1,2,4,8.. , а исходная задача сокращается на долю (1/2)на каждой итерации, сложность такого рода составляет log времени.

Общее время = O(logn)

Создавайте компонуемые веб-приложения

Не создавайте веб-монолиты. Используйте Bit для создания и компоновки несвязанных программных компонентов — в ваших любимых средах, таких как React или Node. Создавайте масштабируемые и модульные приложения с мощными и приятными возможностями разработки.

Перенесите свою команду в Bit Cloud, чтобы вместе размещать компоненты и совместно работать над ними, а также ускорять, масштабировать и стандартизировать разработку в команде. Попробуйте компонуемые внешние интерфейсы с помощью Design System или Микроинтерфейсы или изучите компонуемые внутренние интерфейсы с серверными компонентами. .

Попробуйте →

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

→ Микро-интерфейсы

→ Система дизайна

→ Совместное использование кода и повторное использование

→ Монорепо

Узнать больше: