«ТЭИС» Великанова

После преобразований по формуле Стирлинга получаем С = М * (logМ -1,43), где М – общее число записей в массиве.
Поиском называется процедура выделения из некоторого мно-жества записей определенного подмножества, записи которого удовлетворяют некоторому зара-нее поставленному условию.
Простейшим вариантом ступен-чатого поиска (его можно назвать одноступенчатым) является после-довательный поиск. Поиск с одина-ковой вероятностью r(i)=1/M может окончиться на любой записи, по-этому С = 1/M?i = (М+1)/2 или C ~ М.
Рассмотрим двухступенчатый поиск в массиве, состоящем из М записей. Значение q последовательно сравнивается с рядом величин р(1), p(1+d1), р(1+2*d1), …, p(1+k*d1) до тех пор, пока будет впервые достигнуто неравенство p(1+m*d1)=>q. Здесь заканчивается первая ступень поиска. На второй ступени q последовательно сравнивается со всеми ключами, которые имеют номер 1+m*d1 и больше, до тех пор, пока в процессе сравнений будет достигнут ключ, больший, чем q. Извлеченные при этом записи с ключом q образуют результат поиска.
Эффективность поиска измеряется количеством произведенных сравнений. Для двухступенчатого поиска среднее число срав-нений примерно составит: С=M/(2*d1)+d1/2.
Параметр d1 выбираемый и естественно вы-брать его так, чтобы минимизировалось С. Будем считать d1 непрерывной переменной и вычислим производную:С’= -M/(2*d1^2)+1/2.
Из условия С’=0 получаем d1= . Вторая производная С» в точке x=d1 положительна, следовательно, достигнуто минимальное значение С.

При n -ступенчатом поиске заранее выби-раются константы n и S. На первом этапе ключевые атрибуты для сравнения с искомым ключом q выбираются из массива по закону арифметической прогрессии, начиная с р(1) с шагом d1= M/S (округление в меньшую сторону). Когда будет впервые достигнут ключ p(k)>q, выбирается шаг d2 = d1/S и организуются сравнения с этим шагом, начиная с p(k – d1). Описанные действия повторяются n раз, причем шаг на последней ступени поиска dn = 1. .
Минимальное число сравнений достигается при S = , и, кроме того, существует опти-мальное n = ln(М).
Ступенчатый поиск имеет важный частный вариант — бинарный поиск, когда S = 2.
Для бинарного поиска вводятся левая граница интервала поиска А и правая граница В. Первоначально интервал охватывает весь мас-сив, т.е. А=0, В=М+1. Вычисляется середина ин-тервала i по формуле i=(A+B)/2, с округлением в меньшую сторону. Ключ i-й записи p(i) срав-нивается с искомым значением q. Если p(i)=q, то поиск заканчивается. В случае p(i)>q записи с номрами i+1, i+2,…, М заведомо не содержат ключа q и надо сократить интервал поиска, приняв B=i. Аналогично при p(i)