План лекции. Лекция 1. Международное публичное право как особая правовая система

Лекция 1. Международное публичное право как особая правовая система. Источники, основные принципы и субъекты международного права. Признание и правопреемство в международном праве. Территория и население в международном праве

End

End

Begin

Begin

Otherwise поменять ролями A и В in

Begin

1.А=In_Name[I];

2.B=In_Name[I];

3. wlg положить Size[A]£ Size[B]

5. Element=List[A];

6. while Element¹0 do

7. R[Element]=B;

8. Last=Element;

9. Element=Next[Element]

end;

10. Next[Last]=List[B];

11. List [В] = List[A];

J2. Size[B]=Size[A]+ Size[B];

13. In_Name[К]=В;

14. Out_Name[B]=K

В алгоритме используются обозначения:

wlg (without loss of generality) – без потери в общности;

otherwise – в противном случае;

in – в.

Пример 3.6. После выполнения операции Union (1,2,4) структура данных рис. 19 превратится в структуру данных, изображенную на рис. 20. ÿ

Теорема 13. С помощью алгоритма 16 можно выполнить n–1 (максимально возможное число) операций ОБЪЕДИНИТЬ за O (n ×log n) шагов.

Доказательство. За каждое выполнение операции ОБЪЕДИНИТЬ будем налагать на перемещаемые элементы одинаковые штрафы, в сумме равные сложности этого выполнения. Так как сложность пропорциональна числу перемещаемых элементов, то величина штрафа, налагаемого на один элемент, будет всегда одна и та же. Основное здесь – это заметить, что всякий раз, когда элемент перемещается из списка, он оказывается в списке, по крайней мере в два раза длиннее прежнего. Поэтому никакой элемент нельзя переместить более чем log п раз и, значит, суммарный штраф, налагаемый на один элемент, составляет О (log n).

Дата добавления: 2014-01-07