за время, пропорциональное
за время, пропорциональное суммарному числу их вершин.
Строим выпуклую оболочку множества точек. Метод «разделяй и властвуй» основан на принципе сбалансированности, суть которого в том, что вычислительная задача разбивается на подзадачи примерно одинаковой размерности. Они решаются, и затем результаты объединяются. Метод эффективен, если время, требуемое на объединение результатов, незначительно. Суть данного алгоритма построения выпуклой оболочки. Множество S разделяется на два подмножества S1 и S2, примерно равной мощности. Для каждого из подмножеств строится выпуклая оболочка. Из предыдущего пункта известно, что время объединения оболочек пропорционально количеству вершин в них, т. е. временная зависимость имеет вид: T(N)?2T(N/2)+O(N).
Procedure Sob(S);
begin
if ?S??k {k - некоторое небольшое целое число}
then <построить выпуклую оболочку одним из ранее рассмотренных методов>
else begin
<разбить исходное множество S на два подмножества S1 и S2, примерно равной
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
