|
6.2.2. Метод золотого
сечения Вычислительные характеристики метода дихотомии можно улучшить, используя несколько приемов. Прием 1. Делить файл на количество частей >2. Пример. Будем делить файл на три равные части В этом случае потребуется 2log3 n шагов (T~logn). При делении на 4 части - 3log4n. Таким образом, имеем проигрыш в производительности в сравнении с методом дихотомии. Прием 2. Делить файл на неравные части. Доказано, что наилучшие характеристики достигаются, если файл делится на три части, при этом две «точки деления» получают, откладывая соответственно с начала и конца файла золотое сечение. Примечание. Золотое сечение - предел отношения двух соседних элементов последователь - ности Фибоначчи, то есть последовательности элементов, где каждый следующий является суммой двух предыдущих: 0 1 1 2 3 5 8 13 21 34 55 86 .................................... Данные предел легко найти, исходя из определения последовательности Фибоначчи и свойств пределов. И так Ui+1=Ui-1+Ui Ui+1/Ui=1+Ui-1/Ui Пример lim(Ui+1/Ui)=D => lim(Ui/Ui-1)=a а=1/а+1 а2=1+а а2-а-1=0 D=5 Т.к. а>0 (все числа Фиббоначи) => а «1,618 Как видим а «1,618. Соответственно 1/а=а-1«0,618 Таким образом, «точки деления» находятся в пропорции ~ 0,382 и «0,618. Доказано, что в этом случае T» 0,89log2 n . Записать формальный алгоритм не составляет больших сложностей, поэтому этот шаг опускаем. Методы дихотомии и золотого сечения не лишены недостатков, главным из которых является невозможность одновременной организации поиска по двум полям в одном файле. В случае возникновения такой необходимости приходится дублировать весь файл. Значительные проблемы возникают и при модификации данных, в этом случае приходится выполнять пересортировку записей, что, как уже отмечалось, сопряжено со значительными расходами времени. Кроме того, необходима буферизация данных во внутренней памяти с целью организации прямого доступа. Из достоинств этих методов следует особо отметить несложность организации поиска по неключевым полям. |