Операции над таблицей:

1. Операция инициализации (конструктор).

2. Операция включения элемента в таблицу (модификатор).

3. Операция исключения элемента из таблицы (модификатор).

4. Операции-предикаты:

а) таблица пуста / таблица не пуста (наблюдатель)

б) таблица переполнена / таблица не переполнена (наблюдатель).

5. Чтение элемента по ключу (наблюдатель).

Временная сложность алгоритмов.

Временная сложность (ВС) – зависимость времени выполнения алгоритма от количества обрабатываемых входных данных. Здесь представляет интерес среднее и худшее время выполнения алгоритма. ВС можно установить с различной точностью. Наиболее точной оценкой является аналитическое выражение для функции: t=t(N), где t – время, N – количество входных данных (размерность). Данная функция называется функцией временной сложности (ФВС).

Например: t = 5N² + 32N + 1. Такая оценка может быть сделана только для конкретной реализации алгоритма и на практике обычно не требуется. Часто бывает достаточно определить лишь порядок функции временной сложности t(N).

Две функции f₁(N) и f₂(N) — одного порядка, если

Иначе это записывается в виде: f₁(N)=О(f₂(N)) (Читается " О большое ").

Примеры определения порядка ВС для некоторых алгоритмов:

1. Алгоритм линейного поиска. Этот алгоритм может быть использован как для упорядоченного, так и для неупорядоченного массива ключей. Работа алгоритма заключается в том, что при просмотре всего массива, начиная с первого и до последнего элемента, ключ из массива сравнивается с искомым ключом. Если результат сравнения положительный – ключ найден. Если же ни одно сравнение не выполнилось с положительным результатом, то ключа в массиве нет.

ФВС для алгоритма линейного поиска: t _{л. п.} = k₁  N = O(N). Действительно, для отыскания ключа в худшем случае придется просмотреть все элементы массива. При этом время проверки каждого элемента одинаково и не зависит от конкретной вычислительной системы.

Оценим среднее время алгоритма, при этом будем исходить из следующего: пусть P_i – вероятность того, что будет осуществляться поиск элемента с ключом k_i; при этом предположим, что , т.е. ключ со значением k_i не будет отсутствовать (в таблице обязательно есть элемент, поиск которого осуществляется). Среднее время ( ), как следует из алгоритма, пропорционально среднему числу операций сравнения ( ) и равно ~ = . Если ключи имеют одинаковую вероятность P₁=P₂=...P_N=P, а также учитывая, что , NP=1, P=1/N, тогда ,

т.е. при линейном поиске в среднем необходимо просмотреть половину массива.

Рассмотрим упорядоченную таблицу, у которой элементы упорядочены по частоте обращений (по вероятности). Если имеем такую таблицу, то время – худшее: = О(N).

Распределение осуществляется по закону Зипфа: P_i = c / i, i = 1, 2, … , N, тогда ~ = ,

причем , (N  )

, ln N – постоянная Эйлера.

Исходя из этого получили: с = 1 / ln N.

2. Алгоритм бинарного (двоичного) поиска. В словесной форме алгоритм двоичного поиска можно записать следующим образом:

1. Определить середину массива.

2. Если ключ, находящийся в середине массива, совпадает с искомым, поиск завершен.

3. Если ключ из середины массива больше искомого, применить двоичный поиск к первой половине массива.

4. Если ключ из середины массива меньше искомого, двоичный поиск необходимо применить ко второй половине массива.

5. Пункт 1-4 повторять, пока размер области поиска не уменьшается до нуля. Если это произойдет, то ключа в массиве нет.

ФВС для алгоритма бинарного поиска: t _{б. п.} = O(log ₂ N). Это объясняется тем, что на каждом шаге поиска вдвое уменьшается область поиска. До того, как она станет равной одному элементу, произойдет не более log ₂ N таких уменьшений, т.е. выполняется не более log ₂ N шагов алгоритма.

Изобразим графически функции ВС для линейного и двоичного поиска. Из графика видно, что для малых N нужно использовать линейный поиск, а для больших N — двоичный поиск. N_кр находятся в пределах 10 .. 1000 в зависимости от характеристик используемого оборудования.