Поиск в структуре данных: объяснение различных методов поиска
Опубликовано: 2021-05-03Коммуникационная сеть расширяется, и поэтому люди пользуются Интернетом! Предприятия переходят на цифровые технологии для эффективного управления. Объем данных, генерируемых в Интернете, растет, и поэтому наборы данных становятся сложными. Очень важно тщательно и эффективно организовывать, управлять, получать доступ и анализировать данные, структура данных — самый полезный метод, и статья посвящена тому же!
Оглавление
Структура данных
В информатике структуры данных являются основой для абстрактных типов данных (АТД), где АТД являются логической формой типа данных. Физическая компоновка типа данных реализуется с помощью структуры данных. Различные типы структур данных используются для разных типов приложений; некоторые специализируются на конкретных задачах.
Структура данных представляет собой набор значений данных и взаимосвязей между ними, операций и функций, применимых к данным. Он помогает в организации, управлении и хранении данных в определенном формате. Таким образом, пользователи могут иметь легкий доступ и эффективно изменять данные.
Структуры данных помогают управлять большими объемами данных, например массивными базами данных. Эффективные алгоритмы строятся на основе эффективных структур данных. Помимо эффективного хранения, структуры данных также отвечают за эффективное извлечение информации из сохраненной памяти. Он включает в себя массив, связанный список, указатель, поиск, стек, график, очередь, структуру, программы, сортировку и так далее.
В статье рассматривается концепция поиска в структуре данных и его методы. Два примера алгоритмов подробно объясняются, чтобы ясно понять концепцию. Чтобы получить дополнительные знания, навыки и опыт, доступны онлайн-курсы по структуре данных, упомянутые в конце статьи.
Что такое поиск в структуре данных?
Процесс нахождения нужной информации из множества элементов, хранящихся в виде элементов в памяти компьютера, называется «поиском в структуре данных». Эти наборы элементов представлены в различных формах, таких как массив, дерево, график или связанный список. Другой способ определить поиск в структуре данных — найти нужный элемент с определенными характеристиками в наборе элементов.
Методы поиска
Поиск в структуре данных может быть выполнен путем реализации поисковых алгоритмов для проверки или извлечения элемента из любой формы сохраненной структуры данных. Эти алгоритмы классифицируются в зависимости от типа операции поиска, например:
- Последовательный поиск
Массив или список элементов обходят последовательно, проверяя каждый компонент набора.
Например, линейный поиск.
- Интервальный поиск
Алгоритмы, разработанные специально для поиска в отсортированных структурах данных, включены в интервальный поиск. Эффективность этих алгоритмов намного выше, чем у алгоритмов линейного поиска.
Например, двоичный поиск, логарифмический поиск.
Эти методы проверяются на основе времени, затрачиваемого алгоритмом на поиск элемента, соответствующего элементу поиска в наборах данных, и задаются следующим образом:
- Лучшее время
- Среднее время
- Время наихудшего случая
Основные проблемы связаны с временем наихудшего случая, которое приводит к гарантированным прогнозам производительности алгоритма, а также его легко вычислить по сравнению со средним временем.
Чтобы проиллюстрировать примеры и концепции в этой статье, рассматриваются n элементов в сборе данных в любом формате данных. Доминантные операции используются для упрощения анализа и сравнения алгоритмов. Для поиска в структуре данных доминирующей операцией является сравнение, которое обозначается O() и произносится как «большой-О» или «О».
Существует множество алгоритмов поиска в структуре данных, таких как линейный поиск, двоичный поиск, поиск с интерполяцией, поиск с переходом, экспоненциальный поиск, поиск Фибоначчи, поиск по списку, вездесущий двоичный поиск, неограниченный двоичный поиск, рекурсивная функция для поиска подстроки и рекурсивная программа. для линейного поиска элемента в заданном массиве. Статья ограничена алгоритмами линейного и бинарного поиска и принципами их работы.
Давайте подробно рассмотрим линейный поиск и бинарный поиск в структуре данных.
Линейный поиск
Алгоритм линейного поиска ищет все элементы в массиве последовательно. Его лучшее время выполнения равно единице, тогда как наихудшее время выполнения равно n, где n — общее количество элементов в массиве поиска.
Это самый простой алгоритм поиска в структуре данных, который проверяет каждый элемент в наборе элементов до тех пор, пока он не совпадет с элементом поиска до конца сбора данных. Когда данные не отсортированы, предпочтительным является линейный алгоритм поиска.
Линейный поиск имеет некоторые сложности, как указано ниже:
- Космическая сложность
Сложность пространства для линейного поиска составляет O (n), поскольку он не использует дополнительное пространство, где n — количество элементов в массиве.
- Сложность времени
*Сложность в лучшем случае = O(1) возникает, когда элемент поиска присутствует в первом элементе массива поиска.
*Сложность в наихудшем случае = O(n) возникает, когда искомый элемент отсутствует в наборе элементов или массиве.
*Средняя сложность = O(n) упоминается, когда элемент присутствует где-то в массиве поиска.
Пример,
Давайте возьмем массив элементов, как показано ниже:
45, 78, 12, 67, 08, 51, 39, 26
Чтобы найти «51» в массиве из 8 элементов, указанном выше, алгоритм линейного поиска будет последовательно проверять каждый элемент, пока его указатель не укажет на 51 в пространстве памяти. Требуется O(6) времени, чтобы найти 51 в массиве. Чтобы найти 12 в приведенном выше массиве, требуется O (3), тогда как для 26 требуется O (8) времени.
Бинарный поиск
Этот алгоритм находит определенные элементы, сравнивая самые средние элементы в наборе данных. Когда происходит совпадение, он возвращает индекс элемента. Когда средний элемент больше, чем элемент, он ищет центральный элемент левого подмассива. Напротив, если средний элемент меньше элемента поиска, он исследует середину элемента в правом подмассиве. Он продолжает поиск элемента, пока не найдет его или пока размер подмассивов не станет равным нулю.
Двоичный поиск требует отсортированного порядка элементов. Это быстрее, чем алгоритм линейного поиска. Работает по принципу разделяй и властвуй.
Сложность во время выполнения = O (log n)
Алгоритм бинарного поиска имеет сложности, указанные ниже:
- Сложность в наихудшем случае = O (n log n)
- Средняя сложность = O (n log n)
- Сложность в лучшем случае = O (1)
Пример,
Возьмем отсортированный алгоритм из 08 элементов:
08, 12, 26, 39, 45, 51, 67, 78
Чтобы найти 51 в массиве вышеуказанных элементов,
Алгоритм разделит массив на два массива: 08, 12, 26, 39 и 45, 51, 67, 78.
Поскольку 51 больше 39, он начнет поиск элементов в правой части массива.
Далее он разделит число на два, например 45, 51 и 67, 78.
Поскольку 51 меньше 67, он начнет поиск слева от этого подмассива.
Этот подмассив снова делится на две части: 45 и 51.
Поскольку 51 — это число, соответствующее элементу поиска, он вернет его порядковый номер этого элемента в массиве.
Он сделает вывод, что элемент 51 поиска расположен на 6-й позиции в массиве.
Бинарный поиск сокращает время вдвое, так как количество сравнений значительно меньше, чем алгоритм линейного поиска.
Читайте: Типы структур данных в Python
Интерполяционный поиск
Это улучшенный вариант алгоритма бинарного поиска, который работает с проверкой позиции элемента поиска. Подобно алгоритмам бинарного поиска, он эффективно работает только при сборе отсортированных данных.
Худшее время выполнения = O(n)
Когда местоположение целевого элемента известно в наборе данных, используется интерполяционный поиск. Чтобы найти номер в телефонном справочнике, если кто-то хочет найти номер телефона Моники, вместо использования линейного или двоичного поиска можно напрямую обратиться к хранилищу памяти, где имена начинаются с «М».
Заключение
Поиск в структурах данных относится к поиску заданного элемента в массиве из «n» элементов. Есть две категории, т. Последовательный поиск и интервальный поиск в поиске. Почти все алгоритмы поиска основаны на одной из этих двух категорий. Линейный и бинарный поиск — это два простых и удобных в реализации алгоритма, в которых бинарный поиск работает быстрее, чем линейный алгоритм.
Хотя линейный поиск наиболее прост, он проверяет каждый элемент до тех пор, пока не найдет совпадение с элементом поиска, что эффективно, когда набор данных не отсортирован должным образом. Но, если набор данных отсортирован и длина массива значительна, то бинарный поиск выполняется быстрее.
Структура данных является неотъемлемой частью компьютерного программирования при работе с наборами данных. Программистам и разработчикам необходимо постоянно обновлять и повышать свою квалификацию с помощью основ и обновлений методов компьютерного программирования. Программисты, имеющие дело со структурой данных, должны часто выбирать курсы.
Если вам интересно узнать больше о науке о данных, ознакомьтесь с программой IIIT-B & upGrad Executive PG по науке о данных, которая создана для работающих профессионалов и предлагает более 10 тематических исследований и проектов, практические практические семинары, наставничество с отраслевыми экспертами, Индивидуальные встречи с отраслевыми наставниками, более 400 часов обучения и помощь в трудоустройстве в ведущих фирмах.
