Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



Многофазная сортировка.




Читайте также:
  1. Медицинская сортировка.
  2. Медицинская сортировка.

В основе данной сортировки лежит отказ от жесткого понятия прохода и разделения файлов на две категории. Рассмотрим этот метод сортировки на примере:

               
   
Если , то .   0, 1, 1, 2, 3, 5, 8, 13, 21, 34,…
     
 


f1   f2 f3   L S
13   L=6
5   L=5
0   L=4
3   L=3
1   L=2
0   L=1
L=0

 

Таким образом, необходимо, чтобы числа начальных серий в двух входных последовательностях были двумя соседними числами Фибоначчи.

 

f1   f2 f3 f4 f5 f6   L S
16   L=5
8   L=4
4   L=3
2   L=2
1   L=1
L=0

 

;

;

;

;

.

Подставляя вместо , получаем

(для i ³ 4);

Такие числа называются числами Фибоначчи четвертого порядка. В общем случае числа Фибоначчи порядка р определяются следующим образом:

(для i > p); .

Заметим, что обычные числа Фибоначчи – числа первого порядка.

Теперь уже ясно, что исходные числа серий для идеальной многофазной сортировки с N последовательностями (файлами) представляют собой последовательность чисел Фибоначчи порядка N – 2. Отсюда следует, что метод применим для лишь входов, сумма серий на которых есть сумма N – 1 таких чисел Фибоначчи. В том случае, когда сумма серий отличается от идеальной суммы, то вводим фиктивную серию.



 


Дата добавления: 2015-04-18; просмотров: 14; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2020 год. (0.005 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты