# за время, пропорциональное

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

Индекс
Элементарные функции Линейные уравнения Нелинейные уравнения Случайные числа