§ 3. Асимптотические оценки (два примера)

25

8

а)

P

5

2

P

P

8

б)

P

5

2

P

P

P₁ P₁

Рис. 2. a) Точки, упорядоченные по величине угла АР₁ОР, £ = 1,2,..., п; б) вер­шина Р₄ — первая вдавленная вершина в последовательности Р₂,Р₃, ...,^8.

Вдавленные вершины можно обнаружить просмотром точек Р₂,Р₃, ...,Р_п,Р₁: переходя от вершины P_t к вершине P_i+1, i = 2,3, ... ...,п — 1, можно сразу проверять, принадлежит ли P_t треугольнику P_i_₁OP_i+1, а при переходе от Р_п к Р₁ проверять, принадлежит ли Р_п треугольнику Р_п_₁ОР₁. Если да, то P_t или соответственно Р_п, удаляет­ся, но после этого надо проверить, не окажется ли теперь вдавленной предыдущая из неудаленных вершин, — на рис. 2б видно, что после удаления Р₄ вершина Р₃ становится вдавленной. Возможно, что удале­ние одной вдавленной вершины повлечет удаление нескольких уже рассмотренных вершин, но вершина Р₁ никогда не будет удалена. При i < п — 1 после P_i+1 мы рассматриваем P_i+2

и вновь пытаемся

освободиться от вдавленных вершин с меньшими номерами и т.д. Последний шаг — переход от P_n к P₁ и завершающая попытка осво­бодиться от вдавленных вершин.

Затраты этапа построения точек P и O ограничены значением c₁n, где c₁ — некоторая константа.

Если используется сортировка, сложность которой по числу срав­нений есть r(n), то в алгоритме Грэхема может потребоваться не бо­лее c₂r(n) операций для сортировки точек по величине угла, констан­та c₂ отражает затраты на сравнение двух углов и сравнение рассто­яний от O до двух данных точек.

Покажем, что описанный процесс удаления вдавленных вершин потребует затрат, не превосходящих по величине c₃n, где c₃ —некото­рая константа (в частности, учитывающая затраты на проверку при­надлежности точки треугольнику). В самом деле, если переход от P_i к P_i+1 сопровождается проверкой вдавленности некоторого числа v_i

26 Глава 1. Сложности алгоритмов как функции числовых аргументов

вершин, то число удаленных при этом вершин равно v_i — 1. Но об-

ⁿ

щее число удаленных вершин меньше n. Поэтому ^(v_i - 1) <n, и, как следствие,

ⁿ J] v_i < 2n. (3.1)

Это означает, что сложность T_G(n) алгоритма Грэхема по общему числу арифметических операций и сравнений не превосходит c'r(n) + + c"n, где c' и c" суть некоторые положительные константы. Слож­ность любой сортировки массивов длины n по числу сравнений не может быть меньше n/2, так как каждый элемент должен пройти хо­тя бы одно сравнение и в каждом сравнении участвуют два элемента. Имеем

T_G(n) s= c'r{n) + c"n = r{n) c' + c"_r ⁿ_nт) «S r{n)(c' + 2c"),

откуда T_G(n) = O{r{n)). При этом у нас нет пока достаточных основа­ний для утверждения, что T_с{n) = 6(r(n)), потому что нет, например, оснований утверждать, что после выбора P и O может действитель­но потребоваться r{n) сравнений обсуждаемого типа (ведь мы можем еще выполнять арифметические операции; почему бы не предполо­жить, что, прибегая к ним, можно существенно снизить число срав­нений при сортировке), и мы пока можем утверждать только то, что T_G(n) = fi(n); эту тему мы отложим до § 29.

После того как точки упорядочены по величине угла, информа­цию об их координатах можно представить в виде двунаправленно­го списка, и тогда удаление вдавленных вершин не будет связано с какими-либо перемещениями координат точек, и, подходя формаль­но, можно было бы затраты на перемещения в процессе удаления вдавленных вершин считать равными нулю. При менее формальном подходе эти затраты можно считать ограниченными сверху значени­ем cn, где c—некоторая константа: переход от массива к двунаправ­ленному списку и, равным образом, в силу (3.1), работа со ссылками во время удаления вдавленных вершин потребуют затрат, ограничен­ных величинами такого вида. В свою очередь, сложность любой сор­тировки по числу перемещений элементов не может быть меньше чем n/2 (так как не исключено, например, что изначальный поря­док элементов является обратным к требуемому). Отсюда сложность алгоритма Грэхема по числу перемещений не превосходит произве­дения некоторой константы и сложности используемой сортировки по числу перемещений. Аналогично, для сложности по общему чис-