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