Разбиения с ограничениями: кто быстрее?

[wrest]

wrest в сообщении #1405640 писал(а):

Кстати алгоритм очень хорош тем, что он эффективен как для малых $k$, так и для больших.

Вернее, он замедляется только до $k=n/2$ а потом время остается постоянным.

Но вот мне представляется, что если не подниматься снизу вверх, а спускаться сверху вниз, то для $k/n \approx 1$ должен быть свой быстрый алгоритм (который, по слухам зашифрован во второй шифрограмме на J под кодовым названием pnkd).

[mihaild]

wrest в сообщении #1405593 писал(а):

Эти числа равны

Вот что бывает при попытках думать в 2 часа ночи

Dmitriy40 в сообщении #1405578 писал(а):

Памяти очевидно всего $O(n)$

Памяти $O(n \sqrt n)$ - само по себе число разбиений требует порядка $O(\sqrt n)$ бит на хранение.

[wrest]

mihaild в сообщении #1405647 писал(а):

Вот что бывает при попытках думать в 2 часа ночи

Ваш ночной алгоритм очень крут! Можете подумать теперь днём? Вдруг еще на порядок ускорите?

[Dmitriy40]

mihaild в сообщении #1405647 писал(а):

Dmitriy40 в сообщении #1405578 писал(а):

Памяти очевидно всего $O(n)$

Памяти $O(n \sqrt n)$ - само по себе число разбиений требует порядка $O(\sqrt n)$ бит на хранение.

Ну не знаю, вижу вектор размера N+1 и всё, а уж сколько битов надо - дело чуть другое.

[mihaild]

Dmitriy40 в сообщении #1405750 писал(а):

вижу вектор размера N+1 и всё

Так там внутри структуры, которые занимают не константный размер. Так-то и в первом решении внешний вектор имеет $O(n)$ элементов.

[Dmitriy40]

mihaild в сообщении #1405783 писал(а):

Dmitriy40 в сообщении #1405750 писал(а):

вижу вектор размера N+1 и всё

Так там внутри структуры, которые занимают не константный размер.

Как минимум зависит от реализации, я вполне могу сделать и константный размер элементов вектора, скажем $2^{12}=4096$ битов, такого размера хватит для $k \le n \le 10^6$, благо что оперировать одинаковым размером больших чисел немного проще.

[wrest]

mihaild
Расскажите пож-ста, почему ваш алгоритм работает?

[mihaild]

Dmitriy40 в сообщении #1405815 писал(а):

я вполне могу сделать и константный размер элементов вектора, скажем $2^{12}=4096$ битов, такого размера хватит для $k \le n \le 10^6$,

Тогда можно сделать и константный размер вектора $10^6$, этого тоже хватит для $k \leqslant n \leqslant 10^6$. И получим что алгоритм требует $O(1)$ памяти.
В массовых задачах асимптотику времени и памяти нужно считать на бесконечности.

wrest в сообщении #1405851 писал(а):

почему ваш алгоритм работает?

Да собственно он считает по той же формуле, только немного в другом порядке. Перед выполнением очередного внутреннего шага, в cache[j] лежит $p(j, k)$ при $j < i + k$ и $p(j, k - 1)$ при $j \geqslant i + k$. После этого шага, соответственно, в cache[i + k] появляется $p(i + k, k - 1) + p(i, k) = p(i + k, k)$.
Ну и цикл идет не до $N - k$, а до $N - 2k$, т.к. остальные значения нам не нужны - добавление очередного слагаемого, не меньше $k$, уже даст число, большее $N$, которое нас не интересует.

[Dmitriy40]

mihaild
Ок, согласен с Вами, на бесконечности, $O(n \sqrt n)$ битов.