228
правок
Изменения
→Запрос
Ура
==Память==
Заметим, что количество трапецоидов как мы доказали раньше равно O(n), поэтому мы должны оценить количество узлов созданых на i-ой итерации.
А результирующее выражение для памяти тогда будет
Mem = O(n) + <tex>\sum^{n}_{i=1}</tex>количество узлов созданное на i-ой итерации
Обозначив за k_i количество узлов созданное на i-ой итерации
Mem = O(n) + <tex>\sum^{n}_{i=1}</tex>E[k_i]
Используя вывод из предыдущей части получаем, что E[k_i] <= O(i)/i = O(1)
А тогда Mem = O(n)
Из этих двух выводов очевидно следует, что время построения карты равно O(nlogn)
