какая временная сложность поиска элемента по значению в обычном массиве

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

Авторизуйтесь

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

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

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

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

Примеры

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

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

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

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

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

25–26 ноября, Москва и онлайн, От 24 000 до 52 000 ₽

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

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

Наглядно

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

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

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

Хинт для программистов: если зарегистрируетесь на соревнования Huawei Cup, то бесплатно получите доступ к онлайн-школе для участников. Можно прокачаться по разным навыкам и выиграть призы в самом соревновании.

Перейти к регистрации

Источник

Что такое временная сложность алгоритма?

Когда в детстве меня учили умножать числа, мне говорили, что смысл умножения в том, чтобы короче записать сумму. Например, 4 * 3 это то же, что 4 + 4 + 4.

Сведение умножения к сумме — самый простой, наивный алгоритм умножения. А теперь я возьму мой рабочий ноут и попробую перемножить этим способом какие-нибудь большие числа, например, 4 * 10000000000:

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

Как понять, быстро ли работает алгоритм? Можно попробовать измерить время напрямую:

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

Чтобы уйти от физических свойств вычислителя, используют понятие сложности. Асимптотическая сложность алгоритма — это то, как изменяется время исполнения в зависимости от объема входных данных. В этом определении намеренно не учитывается то, на каком устройте выполняется алгоритм: это может быть компьютер, калькулятор или даже человек. Такой абстрактный вычислитель называют машиной Тьюринга.

При этом разделяют сложность алгоритма в худшем и лучшем случае. Представьте, что мы хотим проверить, есть ли в списке число 42. Мы проверяем первый элемент на равенство 42, второй, третий… В лучшем случае первый элемент окажется искомым. В худшем — последний. Поэтому обычно рассматривают сложность алгоритма в наилучшем, наихудшем случае, и в среднем. Как правило, пессимистическая оценка самая интересная из всех, потому что позволяет планировать объем ресурсов.

Временную сложность алгоритма в худшем случае выражают с использованием нотации «O» большое. В этом случае из рассмотрения исключают члены меньшего порядка и говорят об изменении используемых ресурсов при стремлении размера входа к бесконечности. Например, если время, которое нужно алгоритму для выполнения работы, для всех входов длины n не превосходит 5n^3 + 3n, то асимптотическая временная сложность равна O(n^3).

Рассмотрим несколько примеров

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

Алгоритм, в котором мы идём по списку, чтобы узнать, есть ли в нем значение 42, в худшем случае требует O(n) операций, где n — длина списка. Такую же сложность имеет сравнение строк, потому что по сути оно тоже требуют обхода всей строки.

O(log n)

Проверить, есть ли значение 42 в списке, можно быстрее, чем за O(n), если список отсортирован. Тогда можно проверить на равенство элемент из середины списка. Если он равен 42, то останавливаемся. Если больше — значит, слева можно не искать, там значения только меньше. Будем продолжать проверку, выбирая каждый раз элемент из середины оставшегося отрезка. Этот алгоритм называют бинарным поиском и он имеет логарифмическую сложность, потому что количество вариантов уменьшается каждый раз на 2, как функция, обратная степенной (она же логарифм).

O(n log n)

Можно показать, что большинство алгоритмов сортировки имеют сложность n log(n). За время n log(n) работают сортировка слиянием, кучей, и быстрая сортировка. Еще есть теорема, которая говорит, что если сортировка основана на сравнении элементов, то быстрее, чем за n log(n) отсортировать элементы не получится.

За время n^2 работает обход двумерного массива, это можно представить себе как обход таблицы n * n. И ещё за это же время работают некоторые не очень эффективные по времени алгоритмы сортировки, например, сортировка пузырьком.

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

Если вы хотите углубиться в теорию алгоритмов, то я советую специализацию Алгоритмы и структуры данных на Курсере. Теория здесь изложена доступно и в курсе есть задачи, чтобы набить руку. А еще есть Стенфордский учебник по теории сложности, он написан замечательным языком и в нем прекрасные примеры.

Источник

Понимание сложности времени на примерах Python

Дата публикации Mar 4, 2019

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

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

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

Давайте начнем понимать, что такое вычислительная сложность.

Вычислительная сложность

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

Сложность времени

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

При анализе временной сложности алгоритма мы можем найти три случая:лучший случай,в среднем случаеа такжехудший случай, Давайте разберемся, что это значит.

Предположим, у нас есть следующий несортированный список[1, 5, 3, 9, 2, 4, 6, 7, 8]и нам нужно найти индекс значения в этом списке, используялинейный поиск,

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

Хорошо, но как мы описываем временную сложность алгоритма?

Мы используем математическую запись под названием Big-O.

Биг-О нотация

Биг-О нотацияиногда называют «асимптотической нотацией»,это математическая запись, которая описывает ограничивающее поведение функциикогда аргумент стремится к определенному значению или бесконечности.

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

Давайте посмотрим некоторые общие временные сложности, описанные в нотации Big-O.

Таблица общих временных сложностей

Это наиболее распространенные временные сложности, выраженные с помощью нотации Big-O:

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

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

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

Сложности времени

Говорят, что алгоритм имеет постоянное время, когда он не зависит от входных данных (N). Независимо от размера входных данных, время выполнения всегда будет одинаковым. Например:

Теперь давайте посмотрим на функциюget_firstкоторый возвращает первый элемент списка:

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

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

Говорят, что алгоритм имеет сложность логарифмического времени, когда он уменьшает размер входных данных на каждом шаге (ему не нужно просматривать все значения входных данных), например:

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

Шаги бинарного поиска:

Важно понимать, что алгоритм, который должен обращаться ко всем элементам своих входных данных, не может занимать логарифмическое время, так как время, затрачиваемое на чтение входных данных размераNимеет порядокN,

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

Давайте посмотрим на примерлинейный поискгде нам нужно найти позицию элемента в несортированном списке:

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

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

Например: для каждого значения в data1 (На)) использовать бинарный поиск (O (log n)) искать то же значение в data2.

Следующее изображение иллюстрирует шаги, предпринятые алгоритмом сортировки слиянием.

Обратите внимание, что в этом примере сортировка выполняется на месте.

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

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

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

В качестве примера можно привести Вики Лай:

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

Другим примером экспоненциального алгоритма времени является рекурсивный расчетФибоначчиномера:

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

Это имеет больше смысла, когда мы смотрим на дерево рекурсии Следующее дерево рекурсии было сгенерировано алгоритмом Фибоначчи с использованиемn = 4:

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

Теперь посмотрите, как растет дерево рекурсии, просто увеличиваяNдо 6:

Вы можете найти более полное объяснение временной сложности рекурсивного алгоритма ФибоначчиВотна StackOverflow.

Говорят, что алгоритм имеет факторную сложность времени, когда он растет факториальным образом в зависимости от размера входных данных, например:

Как вы можете видеть, он очень быстро растет даже при небольшом входном размере.

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

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

Давайте посмотрим на пример:

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

Еще один замечательный примерЗадача коммивояжера,

Важные заметки

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

Даже если операции в «my_function» не имеют смысла, мы видим, что он имеет несколько временных сложностей: O (1) + O (n) + O (n²). Таким образом, при увеличении размера входных данных узким местом этого алгоритма будет операция, которая принимает O (n²). Исходя из этого, мы можем описать временную сложность этого алгоритма как O (n²).

Шпаргалка Big-O

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

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

Почему важно знать все это?

Если после прочтения всей этой истории у вас все еще есть сомнения относительно важности понимания сложности времени и обозначения Big-O, давайте уточним некоторые моменты.

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

Кроме того, если вы планируете подать заявку на должность инженера-программиста в такой крупной компании, как Google, Facebook, Twitter и Amazon, вам нужно быть готовым ответить на вопросы о сложности времени, используя нотацию Big-O.

Заключительные заметки

Спасибо за чтение этой истории. Я надеюсь, что вы узнали немного больше о сложности времени и нотации Big-O. Если вам понравилось, пожалуйста, хлопните в ладоши и поделитесь им. Если у вас есть какие-либо сомнения или предложения, не стесняйтесь комментировать или отправить мне письмо. Кроме того, не стесняйтесь следовать за мной нащебет,Linkedin, а такжеGithub,

Источник

6 алгоритмов поиска на Java: от простого к сложному

Поиск – распространённое действие, выполняемое в бизнес-приложениях. Под катом лежат реализации известных алгоритмов поиска на Java.

Программирование на Java – всегда интересный экспириенс. Но куда интереснее работать, применяя правильные для конкретных ситуаций алгоритмы.

Реализуем алгоритмы на Java и проанализируем производительность с помощью параметров временной и пространственной сложности.

Линейный поиск

Линейный или последовательный поиск – простейший алгоритм поиска. Он редко используется из-за своей неэффективности. По сути, это метод полного перебора, и он уступает другим алгоритмам.

У линейного поиска нет предварительных условий к состоянию структуры данных.

Объяснение

Алгоритм ищет элемент в заданной структуре данных, пока не достигнет конца структуры.

Реализация

Теперь посмотрим, как реализовать линейный поиск в Java:

Для проверки используем целочисленный массив:

Простой метод для вывода результата:

Временная сложность

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

В этом случае потребуется N итераций для нахождения элемента.

Следовательно, временная сложность линейного поиска равна O(N).

Пространственная сложность

Этот поиск требует всего одну единицу памяти для хранения искомого элемента. Это не относится к размеру входного массива.

Следовательно, пространственная сложность линейного поиска равна O(1).

Применение

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

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

Двоичный поиск

Двоичный или логарифмический поиск часто используется из-за быстрого времени поиска.

Объяснение

Этот вид поиска использует подход «Разделяй и властвуй», требует предварительной сортировки набора данных.

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

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

Поиск заканчивается, когда firstIndex (указатель) достигает lastIndex (последнего элемента). Значит мы проверили весь массив Java и не нашли элемента.

Есть два способа реализации этого алгоритма: итеративный и рекурсивный.

Временная и пространственная сложности одинаковы для обоих способов в реализации на Java.

Реализация

Итеративный подход

Рекурсивный подход

Теперь посмотрим на рекурсивную реализацию:

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

Другое отличие – рекурсивные вызовы помещаются в стек и занимают одну единицу пространства за вызов.

Используем алгоритм следующим способом:

Временная сложность

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

Пространственная сложность

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

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

Применение

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

Двоичный поиск реализован в методе Arrays.binarySearch Java API.

Алгоритм Кнута – Морриса – Пратта

Алгоритм КМП осуществляет поиск текста по заданному шаблону. Он разработан Дональдом Кнутом, Воном Праттом и Джеймсом Моррисом: отсюда и название.

Объяснение

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

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

КМП работает быстрее алгоритма перебора благодаря пропускам.

Реализация

Скомпилированный массив Java можно рассматривать как массив, хранящий шаблон символов. Цель – найти префикс и суффикс в шаблоне. Зная эти элементы, можно избежать сравнения с начала текста после несоответствия и приступать к сравнению следующего символа.

Скомпилированный массив сохраняет позицию предыдущего местонахождения текущего символа в массив шаблонов.

Давайте реализуем сам алгоритм:

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

Но! Есть один момент.

В текстовом шаблоне AAABAAA наблюдается и кодируется в массив шаблонов следующий шаблон:

В подтверждение наших расчётов:

Описанный выше шаблон ясно показан в скомпилированном массиве.

С помощью этого массива КМП ищет заданный шаблон в тексте, не возвращаясь в начало текстового массива.

Временная сложность

Для поиска шаблона алгоритму нужно сравнить все элементы в заданном тексте. Необходимое для этого время составляет O(N). Для составления строки шаблона нам нужно проверить каждый символ в шаблоне – это еще одна итерация O(M).

O (M + N) – общее время алгоритма.

Пространственная сложность

O(M) пространства необходимо для хранения скомпилированного шаблона для заданного шаблона размера M.

Применение

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

Поиск прыжками

От двоичного поиска этот алгоритм отличает движение исключительно вперёд. Имейте в виду, что такой поиск требует отсортированной коллекции.

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

Это уменьшает поле поиска и делает линейный поиск жизнеспособным вариантом.

Реализация

Мы начинаем с jumpstep размером с корень квадратный от длины массива и продолжаем прыгать вперёд с тем же размером, пока не найдём элемент, который будет таким же или больше искомого элемента.

Вот так используется алгоритм:

Временная сложность

Пространственная сложность

Искомый элемент занимает одну единицу пространства, поэтому пространственная сложность алгоритма составляет O(1).

Применение

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

С ограничением сталкиваются при работе с вращающейся средой. Когда при легком поиске по направлению вперёд многократные прыжки в разных направлениях становятся затратными.

Интерполяционный поиск

Интерполяционный поиск используется для поиска элементов в отсортированном массиве. Он полезен для равномерно распределенных в структуре данных.

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

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

Реализация

Используем алгоритм так:

Смотрите, как работают формулы интерполяции, чтобы найти 6 :

Теперь давайте применим эти значения к формулам для оценки индекса элемента поиска:

index=0+(7−0)/(8−1)∗(6−1)=5

Элемент integers[5] равен 6 — это элемент, который мы искали. Индекс для элемента рассчитывается за один шаг из-за равномерной распределенности данных.

Временная сложность

В лучшем случае временная сложность такого алгоритма – O(log log N). При неравномерном распределении элементов сложность сопоставима с временной сложностью линейного алгоритма, которая = O(N).

Пространственная сложность

Алгоритм требует одну единицу пространства для хранения элемента для поиска. Его пространственная сложность = O(1).

Применение

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

Экспоненциальный поиск

Экспоненциальный поиск используется для поиска элементов путём перехода в экспоненциальные позиции, то есть во вторую степень.

В этом поиске мы пытаемся найти сравнительно меньший диапазон и применяем на нем двоичный алгоритм для поиска элемента.

Для работы алгоритма коллекция должна быть отсортирована.

Реализация

Применяем алгоритм Java:

В нашем случае значение диапазона достигается в элементе 8, а элемент в integers[8] равен 95. Таким образом, диапазон, в котором выполняется бинарный поиск:

При этом вызываем бинарный поиск:

Временная сложность

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

Пространственная сложность

Итеративный алгоритм двоичного поиска требует O(1) места для хранения искомого элемента.

Для рекурсивного двоичного поиска пространственная сложность становится равной O(log (N)).

Применение

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

Заключение

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

В этой статье мы рассмотрели работу алгоритмов поиска Java и случаи их применения.

Источник