Какова временная сложность этого алгоритма умножения?

Question

Для классических интервью вопроса «Как вы выполняете целочисленное умножение без оператора умножения?», Самый простой ответ, конечно, следующий алгоритм линейного времени в C:

int mult(int multiplicand, int multiplier) 
{ 
    for (int i = 1; i < multiplier; i++) 
    { 
     multiplicand += multiplicand; 
    } 

    return multiplicand; 
} 

Конечно, есть более быстрый алгоритм. Если мы воспользуемся свойством, что смещение бита влево эквивалентно умножению на 2 на мощность числа сдвинутых битов, мы можем смещать бит до ближайшей мощности 2 и использовать наш предыдущий алгоритм для добавления оттуда. Таким образом, наш код теперь будет выглядеть примерно так:

#include <math.h> 

int log2(double n) 
{ 
    return log(n)/log(2); 
} 

int mult(int multiplicand, int multiplier) 
{ 
    int nearest_power = 2^(floor(log2(multiplier))); 
    multiplicand << nearest_power; 
    for (int i = nearest_power; i < multiplier; i++) 
    { 
     multiplicand += multiplicand; 
    } 

    return multiplicand; 
} 

У меня возникли проблемы с определением сложной сложности этого алгоритма. Я не считаю, что O(n - 2^(floor(log2(n)))) - это правильный способ выразить это, хотя (я думаю?) Это технически правильно. Может ли кто-нибудь объяснить это?

Answer 1

mulitplier - nearest_power может быть столь же большой, как половина multiplier, и как она стремится к бесконечности постоянной 0.5 там не имеет значения (не говоря уже мы избавимся от постоянных в Big O).Поэтому петля O(multiplier). Я не уверен в смещении бит.

Редактировать: Я немного взглянул на бит-сдвиг. Как говорит gbulmer, это может быть O(n), где n - количество сдвинутых битов. Однако он может также быть O(1) на некоторых архитектурах. См.: Is bit shifting O(1) or O(n)?

Однако в этом случае это не имеет значения! n > log2(n) для всех действующих n. Таким образом, у нас есть O(n) + O(multiplier), который является подмножеством O(2*multiplier) из-за вышеупомянутого отношения, и, следовательно, весь алгоритм равен O(multiplier).

Answer 2

Редактировать

Давайте посмотрим на второй публикуемую алгоритма, начиная с:

int nearest_power = 2^(floor(log2(multiplier))); 

Я считаю вычисления log2, это, скорее приятно, O (log2 (множитель))

затем nearest_power доходит до интервала [множитель/2 до множителя], величина которого является множителем/2. Это то же самое, что найти самый высокий бит набора для положительного числа.

Таким образом, цикл for представляет собой О (множитель/2), константа 1/2 выходит, так что О (п)

В среднем это половина интервала прочь, который был бы вывода (множитель/4). Но это только постоянная 1/4 * n, поэтому она все еще O (n), константа меньше, но она все еще O (n).

Более быстрый алгоритм.

Наша intuitiion есть мы можем умножить на п значного числа в п шагов

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

Если мы используем O (1) операции по п, Х битное число, это O (log2 (п)) или О (х), где х представляет собой количество битов в числе

В этом является алгоритмом O (log2 (n)):

int mult(int multiplicand, int multiplier) { 
    int product = 0; 

    while (multiplier) { 
     if (multiplier & 1) product += multiplicand; 
     multiplicand <<= 1; 
     multiplier >>= 1; 
    } 

    return product; 
} 

По существу, мы делаем длинное умножение.

Конечно, мудрая вещь - использовать меньшее число как множитель. (Я оставлю это как упражнение для читателя :-)

Это работает только для положительных значений, но путем тестирования и запоминания знаков ввода, работающих на положительных значениях, а затем корректировки знака, оно работает для всех чисел.

Answer 3

Пункт поиска ближайшей мощности - это то, что время выполнения вашей функции может приблизиться к времени выполнения O (1). Это происходит, когда 2^ближайшая сила очень близка к результату вашего добавления.

За кулисами целая «сила 2» выполняется с битовым сдвигом.

Итак, чтобы ответить на ваш вопрос, вторая версия вашего кода по-прежнему хуже случайного времени: O (множитель).
Ваш ответ O (n - 2^(пол (log2 (n)))) также не является неправильным; это просто очень точно и может быть трудно сделать в вашей голове, чтобы найти границы.