Время выполнения вычисления x^y

Question

Как мне найти время работы (в примечании Big-O) основного алгоритма, который выполняет умножения на (y − 1) на x, чтобы найти x^y?

Edit: Также нужно иметь в виду, время выполнения каждого умножения: «при условии, что время Умножая n-bit номер с помощью m-bit числа является O(mn)».

Answer 1

Нужно просто учитывать количество бит для каждой операции и суммировать их. Конечно, мы сделаем небольшое округление, чтобы просто вещи, так как это не повлияет на ответ на ноту большой буквы O.

Таким образом, количество бит в x является потолком (log2 (x)) (т. Е. Следующее целое число выше логарифмической базы 2 x). Мы будем называть это число b для простоты. Это означает, что x больше 2^(b-1) и меньше 2^b. Итак, x^2 больше 2^(2 (b-1)) и меньше 2^(2b). Таким образом, мы будем предполагать, что x^2 имеет размер приблизительно 2b и что в общем случае x^n имеет размер nb. Это довольно близко к правильному, поскольку оно лежит между n (b-1) и nb.

Наше первое умножение займет время b * b = b^2. Наше второе умножение будет принимать 2b * b (так как x^2 имеет размер 2b, а x - размер b). Наше третье будет 3b * b (так как x^3 имеет размер 3b, а x - размер b). Итак, в общем случае наше n-е умножение будет nb * b.

Итак, наша сумма выглядит как b^2 + 2b^2 + 3b^2 + ... + (y-1) b^2. Мы можем разложить b^2, давая нам (b^2) (1 + 2 + 3 + ... + (y-1)). Для второго слагаемого 1 + 2 + 3 + ... + (y-1) мы можем использовать общую формулу: 1 + 2 + 3 + ... + n = n (n + 1)/2. Итак, мы получаем (b^2) (y-1) (y)/2.

На этом этапе мы очень близки к ответу, но мы хотим сделать две вещи: мы хотим выразить все в терминах x и y (а не b), и мы хотим уменьшить количество вещей, используя big-O обозначение для простоты. (y-1) (y)/2 можно упростить до O (y^2). b = потолок (log2 (x)), который можно упростить до O (log (x)). Подставляя назад, получаем O ((log (x))^2 * y^2).

Все это, конечно, при условии, что мы используем алгоритм, который выглядит следующим образом:

product = 1 
for i = 1 to y 
    product = product * x 
return product 

Если мы делаем что-то более сложным и странным, как это одна:

xs = empty list 
for i = 1 to y 
    xs.addItem(x) 
while xs is not empty 
    num1 = xs.removeRandomItem 
    num2 = xs.removeRandomItem 
    xs.addItem(num1*num2) 
return head(xs) 

, тогда анализ времени становится более сложным. (Обратите внимание, что этот алгоритм также делает Y-1 умножения и получает правильный результат.)

Другой общий алгоритм для нахождения х^у является неоднократным алгоритм возведения в квадрате, который работает следующим образом:

result = 1 
temp = x 
while y>0 
    if y mod 2 = 1 
    result = result * temp 
    y = y - 1 
    temp = temp * temp 
    y = y/2 
return result 

Для этого мы делаем два умножения в каждом раунде, в которых участвуют два числа, каждый из которых имеет размер b (2^n), где n - число раундов, отсчитываемое от 0 (т. е. количество раз, которое мы прошли через цикл while). Таким образом, в круге n каждое умножение будет стоить b (2^n) * b (2^n) = (b^2) (2^(2n)). Но он касается только потолочных (log2 (y)) раундов. Таким образом, его время пробега было бы суммой (b^2) (2^0) + (b^2) (2^2) + (b^2) (2^4) + ... + (b^2) (2^(2 * потолок (log2 (у)))). Итак, снова мы можем разложить b^2, оставляя (b^2) (2^0 + 2^2 + 2^4 + ... + 2^(2 * потолок (log2 (y)))). Несмотря на сложность, весь второй член на самом деле равен O (y^2). Как только мы снова заменим b, получим, что это тоже O ((log (x))^2 * y^2). Таким образом, хотя этот алгоритм быстрее, когда умножения являются постоянными операциями времени, это не обязательно быстрее, когда мы работаем с BigIntegers или другими произвольными типами точности. Вот почему он чаще всего используется в ситуациях, таких как матричное умножение, где стоимость выполнения умножения является постоянной, но большой.

Answer 2

O (логия) или O (у) в зависимости от метода, который вы выбрали, вы должны начать читать эту http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.4

В вашем случае для (у-1) умножений O (у) число шагов, предполагая умножение - одна операция, поскольку удвоение размера y приведет к удвоению количества необходимых операций, которое называется линейным процессом.

LE: в этом случае у вас будет 1 * n^2 + 2 * n^2 + ... + y * n^2. Впервые вы умножаете число само по себе, поэтому n * n = n^2 во второй раз результат n * n (размер 2n) на число n => 2n^2 и т. Д.

п^2 (1 + 2 + ... у) = п^2 * у * (у + 1)/2

Так что ответ O (N^2 * у^2), где n = число бит в x (или n = ceil (log (x))).

Answer 3

Если каждое умножение подсчитывается как одна операция, то алгоритм, требующий шагов y - 1, - это просто , что является наиболее распространенным ответом, который вы найдете по этому вопросу. В действительности, умножение не может быть сделано в постоянное время, поэтому вам нужно будет умножить скорость любого multiplication algorithm, который вы используете.

Обратите внимание, что с помощью exponentiation by squaring вы можете сделать меньше, чем y - 1 операций, и ваш алгоритм возведения в степень может быть O(log y).