ТЕОРЕТИЧЕСКИЙ АНАЛИЗ МЕТОДОВ ПОИСКА В ОБЪЕКТНОМ СЛОВАРЕ

Аннотация. Данная статья посвящена исследованию различных методов поиска

Ключевые слова: помехоэмиссия, электромагнитное поле, сопротивление изоляции, свойства электрической изоляции.

1. АНАЛИЗ МЕТОДОВ ПОИСКА ДАННЫХ

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

Проведём обзор наиболее популярных методов поиска.

1.1 Полный перебор

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

Определим, наиболее явные достоинства и недостатки разбираемого нами алгоритма.

Достоинства:

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

- Применимость: Этот метод не требует предварительной сортировки.

Недостатки:

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

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

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

1.2 Бинарный поиск

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

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

На каждом этапе происходит поиск середины отрезка с использованием следующей формулы.

Если значение, которое мы ищем, совпадает с элементом посередине (с индексом mid), то поиск завершается.

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

Достоинства:

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

- Бинарный поиск не требует дополнительной памяти.

Недостатки:

- Бинарный поиск работает только с отсортированными данными.

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

Средняя временная сложность алгоритма O(log n), не требует дополнительных затрат памяти.

1.3 Двоичное дерево поиска

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

Для такого дерева справедливы следующие условия:

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

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

Достоинства:

- Прост в реализации и понимании.

- Довольно просто вставлять данные.

Недостатки:

- Имеются дополнительные затраты памяти.

- Сложно удалять узлы.

Быстродействие алгоритма составляет – O(log(n)). Есть вариант реализации, который позволит оптимизировать производительность метода по сравнению с бинарным поиском, так как избавляется от необходимости постоянно вычислять средний элемент. Однако для такой оптимизации потребуется увеличить объем используемой памяти на величину , где ps - размер указателя, а n - количество элементов в массиве.

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

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

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

Где:

d – шаг первоначального сравнения

i – номер первого рассматриваемого элемента

j – номер последнего рассматриваемого элемента

K – отыскиваемый ключ значения ключей в i и j позициях

Ki, Kj - значения ключей в i и j позициях

Достоинства интерполяционного поиска:

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

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

Недостатки интерполяционного поиска:

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

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

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

Вычислительная сложность такого алгоритма в среднем случае log(log(n)), однако при неудачных входных данных составит O(n). Дополнительный расход памяти отсутствует.

1.5 Хеш – таблица

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

Перед выполнением операции в хеш – таблице к искомому значению применяется  хеш – функция. Полученное значение i = hash(key) определяет индекс в массиве H, над которым будет выполнена одна из операций (добавления, удаления или поиска).

Достоинства:

- Быстрый поиск: теоретическое быстродействия может достигать О(1).

Недостатки:

- Присутствие коллизий.

- Использование дополнительной памяти.

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

Заключение

Результаты предварительного анализа методов поиска представлены в таблице 1.1.

Таблица 1.1.

Предварительный анализ методов поиска

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

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