Ну, вам просто нужно учитывать количество бит для каждой операции и суммировать их.Конечно, мы сделаем небольшое округление для упрощения вещей, так как это не повлияет на ответ обозначения big-O.
Таким образом, число бит в x является потолком (log2 (x)) (то есть следующее целое число выше логарифма основания 2 х).Мы будем называть это число б, для простоты.Это означает, что 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 и получает правильный результат.)
Другим распространенным алгоритмом нахождения x ^ y является алгоритм повторного возведения в квадрат, который работает следующим образом:
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 (то есть, сколько раз мы проходили черезпока цикл).Таким образом, в раунде 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 или другими типами произвольной точности.Вот почему он чаще всего используется в ситуациях, таких как матричное умножение, где стоимость умножения постоянна, но велика.