75
правок
Изменения
м
→Разделение на полосы: поправил слово
Таким образом, легко заметить, что значение <math>f(x_1, x_2, ..., x_n)</math> находится на пересечении строки <math>x_1, x_2, ..., x_k</math> и столбца <math>x_{k + 1}, x_{k + 2}, ..., x_n</math>.
== Разделение на полосы ==
Разделим таблицы таблицу на горизонтальные полосы шириной <math>s</math> (последняя полоса, возможно, будет короче остальных; её длину обозначим <math>s'</math>). Пронумеруем полосы сверху вниз от 1 до <math>p=\lceil\frac{2^k}{s}\rceil</math>.
Рассмотрим независимо некоторую полосу. Среди её столбцов при небольшом <math>s</math> будет много повторений, поэтому введём понятие '''''сорта''''' столбца.
}}
Число сортов столбцов <math>i</math>-й полосы обозначим как <math>t(i)</math>. Понятно, что для любой полосы <math>t(i) \leq 2^s</math> (для последней <math>t(i) \leq 2^{s'}</math>).
== Функция для одной полосы ==
Пусть для некоторого <math>i</math>
