Теория игр и исследование операций. Модели, алгоритмы, сложность: Конспект лекций, страница 3

В скобках до двоеточия стоит j - точка раздела зон, а после двоеточия - f_ij + F_jk.

Изменив критерий, упростим поиск одного центра: минимум функционала Sw_i× ||x_i-c||² достигается в точке z = Sw_i·x_i/ Sw_i - центре тяжести множества X.

Sw_i× ||x_i-c||² = Sw_i× ||x_i-z||² +Sw_i× ||z-c||² +2Sw_i× (x_i-z, z-c).

Но z-cне зависит от i, а Sw_i× (x_i-z) = Sw_i·x_i-Sw_i×Sw_i·x_i/ Sw_I =0 Þ слагаемое3 = 0. Если точки равномерно покрывают компактную область и веса примерно равны, то решения задач с обоими критериями очень близки. ???

Далее рекуррентное уравнение соответствует нерекуррентному алгоритму!!

Алгоритм сортировки с трудоемкостью O (nlogn)  в худшем случае.

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

Посчитаем трудоемкость: , где T_{склейки}=cn, c=const.

Пример:  Даны числа: 15 3 6 24 18 13 15 5 7 81 8. Упорядочим пары чисел и сольем пары в упорядоченные четверки: 3 15  6 24  13 18  5 15  7 81  8 и  3 6 15 24  5 13 15 18  7 8 81. Формируем упорядоченные восьмерки. Сравниваем первые числа четверок 3 и 5. Минимум слева Þ пишем его в восьмерку и сдвигаем указатель левой четверки. Далее сравниваем 6 и 5, минимум справа Þ в восьмерку пишем 5 и сдвигаем указатель правой четверки и т.д. Когда одна из четверок закончится, остаток другой запишем в хвост восьмерки. На выходе упорядоченные восьмерки:  3 5 6 13 15 15 18 24  7 8 81. Склеивая таким же образом восьмерки, в итоге получим упорядоченное множество:  3 5 6 7 8 13 15 15 18 24 81.

В частных случаях бывают более быстрые методы упорядочения. Например, для массива из 10⁹ элементов с целыми значениями из интервала [1,100] заведем 100 счетчиков и за линейное время посчитаем кратность каждого числа.

№2. ПОИСК k-ого элемента ЗА ЛИНЕЙНОЕ ВРЕМЯ. (Кнут, т.3, стр. 261)

1)  Будем считать, что n=7*(2q+1), где q – произвольное натуральное число. Если это не выполнено, то добавим нужное число максимальных элементов.

2)  Запишем данные по 7 чисел в строке и упорядочим строки по возрастанию.

3)  Найдем медиану Z в среднем столбце.

4)  Фильтруем строки по среднему столбцу относительно Z,
т.е. делим строки на две части: больше или меньше Z в столбце.

5)  Обозначим получившиеся зоны как показано на рисунке.
Очевидно, a £ Z £ d для всех aÎA и dÎD. Остались B и C.

6)  Фильтруем все xÎBÈC относительно Z: если x £ Z,то xÎA*, иначе xÎD*.

7)  Пусть r ¾ число элементов множества A+A^*. Если k=r, то искомое число равно Z. Если k<r, то ищем k-ое число в A+A^*, иначе ищем (k-r)-ое число в D+D^*. В обоих случаях остается не более ⁵ⁿ/₇ чисел.

Оценим трудоемкость этого рекурсивного алгоритма: T_n £ c·n + . У нас S a_i = ¹/₇ + ⁵/₇ = ⁶/₇ < 1, ÞT_n £ 7·c·n.    Если в строки записывать по 5 чисел, то
T_n £ c·n + и S a_i = ¹/₅ + ⁷/₁₀ = ⁹/₁₀ Þ  T_n £ 10·c·n .

Пример: Дан неупорядоченный массив чисел.

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

В среднем столбце найдем средний по значению элемент Z=6. Фильтруем строки относительно Z по среднему столбцу и выделяем множества A,B,C,D.