Задачи про простые числа и группу

poojke

ness73

Про первую задачу. Рассматриваешь случай, когда n — степень двойки, рисуешь картинку (квадрат с диагональю делишь на 4 равных квадрата, произведение в левом нижнем и правом верхнем считается за ~n. Дальше по рекурсии и основной теореме о рекуррентных оценках (Ослы, 4.1) получаем ~n log n. Так?

Lokomotiv59

Вот решение:

1-1-1-1-1-1-1-1|1 1 1 1|1-1|1 1 0
1 1 1 1 1 1 1 1|1 1 1 1|1_1|1 0 1
1 1 1 1 1 1 1 1|1 1 1 1|1 1 0|1-1
1 1 1 1 1 1 1 1|1_1_1_1|1 0 1|1_1
1 1 1 1 1 1 1 1|1 1|1 1 0|1-1-1-1
1 1 1 1 1 1 1 1|1_1|1 0 1|1 1 1 1
1 1 1 1 1 1 1 1|1 1 0 1 1|1 1 1 1
1_1_1_1_1_1_1_1|1 0 1 1 1|1_1_1_1
1-1-1-1|1-1|1 1 0 1-1-1-1-1-1-1-1
1 1 1 1|1_1|1 0 1|1 1 1 1 1 1 1 1
1 1 1 1|1 1 0 1 1|1 1 1 1 1 1 1 1
1_1_1_1|1 0 1|1-1|1 1 1 1 1 1 1 1
1 1|1 1 0 1 1|1_1|1 1 1 1 1 1 1 1
1_1|1 0 1|1-1-1-1|1 1 1 1 1 1 1 1
1 1 0 1 1|1 1 1 1|1 1 1 1 1 1 1 1
1 0 1|1-1|1 1 1 1|1 1 1 1 1 1 1 1
0 1 1|1_1|1_1_1_1|1-1-1-1-1-1-1-1

poojke

Спасибо и FМХ. Но я не совсем понимаю идею
Можно подробно обьяснить: что в картине? Что за "произведение в левом нижнем и правом верхнем.." ? И "Ослы, 4.1" Это книга что ли? какая?

ness73

Можно подробно обьяснить: что в картине?
z_1 = 1 * x_2 * x_3 * x_4
z_2 = x_1 * 1 * x_3 * x_4
z_3 = x_1 * x_2 * 1 * x_4
z_4 = x_1 * x_2 * x_3 * 1
Что за "произведение в левом нижнем и правом верхнем.." ?
Левый нижний:
x_1 * x_2
x_1 * x_2
Правый верхний:
x_3 * x_4
x_3 * x_4
А дальше по рекурсии применяем к левому верхнему и к правому нижнему, размер задачи уменьшается в 2 раза.
И "Ослы, 4.1" Это книга что ли? какая?
Кормен, Лейзерсон, Ривест. Алгоритмы: построение и анализ. Соотвественно, 4.1 — номер теоремы, раздел, кажется, 4.3.

Lokomotiv59

В общем алгоритм такой:
дополняем группу до степени двойки единицами, если это нужно.
Далее считаем такие произведения:
1. A(1,1) = x(1)*...*x(n/2) и A(1,2) = x(n/2+1)*...*x(n) ~ n операций.
2. A(2,1) = x(1)*...*x(n/4 A(2,2) = x(n/4+1)*...*x(n/2 A(2,3) = x(n/2+1)*...*x(3n/4 A(2,4) = x(3n/4+1)*...*x(n) ~ n операций.
...
s. A(s,1)=x(1)*...*x(n/2^s ..., A(s,2^s)=... ~ n операций
s пробегает значения s=1, ..., k-1, где n = 2^k.
Далее, пусть i - произвольное число от 1 до n.
Надо найти z(i) = (x(1)*...*x(i-1*(x(i+1)*...*x(n = z0(i)*z1(i)
Раскладываем i-1 в виде суммы степеней двоек:
i-1 = 2^l(1) + 2^l(2) + ... + 2^l(m)
Тогда z0(i) = A(n - 2^l(1) - 1, 1) * A(n - 2^l(1) - 2^l(2) - 1, 2^{l(1)-l(2)}+1) * ...
z1(i) считается аналогично.
Возможно я где-то еще ошибся в индексах, но не в этом суть.
Для вычисления A(i,j) требуется n*k операций.
На вычисление каждого z(i) требуется k операций (не более k сомножителей)
В итоге: O(n*log n)

poojke

Понял. Спасибо.
У меня последний вопрос: как получить сложность n.log(n)?
Я только что прочитал теорему 4.1...: верно ли что f(n) = n, a = 1, b = 2 ?

ness73

a = 2. Но лучше посмотри, что написал =) Такие оценки гораздо проще доказывать без теоремы, если теорема не считается известной.

poojke

Вторая задача?Помогите мне пожалуйста

Lokomotiv59

Тут либо жоская теория чисел, либо тупой перебор, заведомо экспоненциальный. Для каких k (по величине) надо уметь решать задачу ?

poojke

Для k чем больше,тем лучше.

Lokomotiv59

Либо конкретизируй, либо я скажу, что эффективного (полиномиального) алгоритма я не знаю.

poojke

Мне только что подсказали ссылку http://hjem.get2net.dk/jka/math/aprecords.htm.
Оставить комментарий
Имя или ник:
Комментарий: