32
правки
Изменения
→Псевдокод
<tex>W_1(t_u, t_v, 1) = w_1</tex>
'''for''' <tex>k = 12</tex> '''to''' <tex>n</tex>
'''for''' <tex>m = 1</tex> '''to''' <tex>n</tex>
'''foreach''' <tex>t_u, t_v \in \Theta, m \in [1, n] \mid t_u \leqslant t_v</tex>
'''if''' <tex>r_k \not\in [t_u, t_v)</tex>
<tex>W_k (t_u, t_v, m) \leftarrow W_{k - 1} (t_u, t_v, m)</tex>
<tex>W_k (t_u, t_v, m) \leftarrow \max(W_{k - 1} (t_u, t_v, m), W'_k\})</tex>
'''return''' <tex>\max\limits_{i \in [1, \dots, n]}(W_n(\min\limits_{t \in \Theta} (t - p), \max\limits_{t \in \Theta} (t), i))</tex> === Оценка алгоритма ===Заметим, что множество <tex>\Theta</tex> содержит не более <tex>n^2</tex> элементов. Следовательно, цикл по <tex>t_u, t_v</tex> итерируется <tex>O(n^4)</tex> раз. Внутри этого цикла мы тратим <tex>O(n^4)</tex> времени на подсчет <tex>W'_k</tex>, так как зная <tex>t_x, m_1</tex> и <tex>m_2</tex> мы можем посчитать <tex>t_y</tex> и <tex>m_3</tex>. Также алгоритм использует шестимерный массив для хранения <tex>W_k (t_u, t_v, m)</tex>. Таким образом, учитывая итерации алгоритма по <tex>k</tex> и <tex>m</tex>, нам потребуется <tex>O(n^{10})</tex> времени и <tex>O(n^6)</tex>памяти для работы алгоритма.
== См. также ==
