Что вы пробовали? Какую машину и стоимость модели вы предполагаете?
Рафаэль
Ответы:
12
Используя быстрое преобразование Фурье, умножения на битные числа можно выполнить за время (где тильда означает, что мы игнорируем полилогарифмические факторы). Повторяя возведение в квадрат, мы можем вычислить с умножением , и каждое умножение включает в себя не большее число, чем , которое имеет примерно битов. Таким образом, общее количество требуемого времени равно .˜ O ( k )kO~(k) O ( журнал п ) п п 2 п 2 лог 2 п ~ О ( п 2 ( лог - п ) 2 ) = ~ O ( п 2 )nn2O(logn)nn2n2log2nO~(n2(logn)2)=O~(n2)
Отредактировано в ответ на комментарии
. Время для вычисления может быть разложено на время, необходимое для вычисления и то, которое требуется для выполнения . Я буду считать , что умножая разрядное число с помощью - битовое число занимает ровно раз по методу школы книги; дополнения и т. д. имеют постоянное время. В результате вычисление занимает времени. f 1 ( n ) = n 2 n f 1 ( n ) m n m n n 2 log 2 2 ( n )f(n)=nn2f1(n)=n2nf1(n)mnmnn2log22(n)
Предположим, что мы используем двоичное возведение в степень для вычисления . Двоичное возведение в степень выполняет два вида операций при вычислении : возводит в квадрат текущий продукт и умножает текущий продукт на зависимости от того, равен ли текущий бит в двоичном расширении 0 или 1. В худшем случае , является степенью двойки, так что двоичное возведение в степень многократно возводит в квадрат свой текущий продукт, пока не достигнет ответа. Обратите внимание, что имеет битов, так что число таких расквартирований . Это тот случай, который мы проанализируем ниже.f ( n ) n n 2 n 2 n 2 m ′ = ⌈ 2 log 2 ( n ) ⌉ m = m ′ - 1f(n)f(n)nn2n2n2m′=⌈2log2(n)⌉m=m′−1
Первый квадрат занимает время , в результате получается произведение -бит. Второе возведение в квадрат занимает два битных числа и выполняется за время , в результате чего получается произведение. Продолжая, шаг занимает времени и выводит -битное произведение. Этот процесс останавливается на шаге; в результате требуется времяo 1 = 2 log 2 ( n ) o 1 t 2 = o 2 1 o 2 = 2 o 1 i t i = 4 i - 1 log 2 2 n o i = 2 i log 2 ( н ) мt1=log22(n)o1=2log2(n)o1t2=o21o2=2o1iti=4i−1log22noi=2ilog2(n)m
Texp=∑[1..m]ti=log22(n)∑[1..m]4i=4m−13log22n .
Когда включена первоначальная стоимость возведения в квадрат, мы находим самое большее время
Texp+log22n
Запись
В вычислениях я опустил некоторые этажи и потолки, надеясь, что они не окажут существенного влияния на ответ.
Я намеренно пропустил анализ на основе в пользу точной верхней границы, чтобы быть точным.
O
Приведенные выше рассуждения также дают понять, почему мой предыдущий анализ был ошибочным. обозначение было использовано в быстром и рыхлом-пути, и это удобно опущены константы , так что, например, магическим образом стал .
O∑tiO(logn)
Умножения всегда можно ускорить с помощью БПФ и другими методами.
Я собираюсь сказать, что умножение двух битных чисел занимает время вместо времени , вы должны также учесть это в стоимости двоичного возведения в степень. O ( log n ) O ( 1 )nO(logn)O(1)
Марк Доминус
2
Обратите внимание, что конечный результат имеет битов. Очень сложно вычислить бит за . n 2 log 2 n O ( log n )n2log2nn2log2nO(logn)
Честно, я приму к сведению
PKG
1
@ThomasAndrews: Это зависит от модели машины и стоимости. Нет ничего необычного в том, чтобы предположить модель RAM с постоянной стоимостью для дополнений.
Ответы:
Используя быстрое преобразование Фурье, умножения на битные числа можно выполнить за время (где тильда означает, что мы игнорируем полилогарифмические факторы). Повторяя возведение в квадрат, мы можем вычислить с умножением , и каждое умножение включает в себя не большее число, чем , которое имеет примерно битов. Таким образом, общее количество требуемого времени равно .˜ O ( k )k O~(k) O ( журнал п ) п п 2 п 2 лог 2 п ~ О ( п 2 ( лог - п ) 2 ) = ~ O ( п 2 )nn2 O(logn) nn2 n2log2n O~(n2(logn)2)=O~(n2)
источник
Отредактировано в ответ на комментарии . Время для вычисления может быть разложено на время, необходимое для вычисления и то, которое требуется для выполнения . Я буду считать , что умножая разрядное число с помощью - битовое число занимает ровно раз по методу школы книги; дополнения и т. д. имеют постоянное время. В результате вычисление занимает времени. f 1 ( n ) = n 2 n f 1 ( n ) m n m n n 2 log 2 2 ( n )f(n)=nn2 f1(n)=n2 nf1(n) m n mn n2 log22(n)
Предположим, что мы используем двоичное возведение в степень для вычисления . Двоичное возведение в степень выполняет два вида операций при вычислении : возводит в квадрат текущий продукт и умножает текущий продукт на зависимости от того, равен ли текущий бит в двоичном расширении 0 или 1. В худшем случае , является степенью двойки, так что двоичное возведение в степень многократно возводит в квадрат свой текущий продукт, пока не достигнет ответа. Обратите внимание, что имеет битов, так что число таких расквартирований . Это тот случай, который мы проанализируем ниже.f ( n ) n n 2 n 2 n 2 m ′ = ⌈ 2 log 2 ( n ) ⌉ m = m ′ - 1f(n) f(n) n n2 n2 n2 m′=⌈2log2(n)⌉ m=m′−1
Первый квадрат занимает время , в результате получается произведение -бит. Второе возведение в квадрат занимает два битных числа и выполняется за время , в результате чего получается произведение. Продолжая, шаг занимает времени и выводит -битное произведение. Этот процесс останавливается на шаге; в результате требуется времяo 1 = 2 log 2 ( n ) o 1 t 2 = o 2 1 o 2 = 2 o 1 i t i = 4 i - 1 log 2 2 n o i = 2 i log 2 ( н ) мt1=log22(n) o1=2log2(n) o1 t2=o21 o2=2o1 i ti=4i−1log22n oi=2ilog2(n) m
Когда включена первоначальная стоимость возведения в квадрат, мы находим самое большее время
Запись
источник