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

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

2 голосов
/ 23 марта 2012

Для классического интервью на вопрос «Как выполнить целочисленное умножение без оператора умножения?», Самый простой ответ, конечно, следующий алгоритм линейного времени в 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)))) - это правильный способ выразить это, хотя (я думаю?) Это технически правильно. Кто-нибудь может дать некоторое представление об этом?

Ответы [ 3 ]

3 голосов
/ 23 марта 2012

mulitplier - nearest_power может быть равным половине multiplier, и поскольку она стремится к бесконечности, постоянная 0.5 не имеет значения (не говоря уже о том, что мы избавляемся от констант в Big O).Таким образом, цикл равен O(multiplier).Я не уверен насчет сдвига битов.

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

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

0 голосов
/ 23 марта 2012

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

За кулисами все "в степень 2" делается со сдвигом битов.

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

0 голосов
/ 23 марта 2012

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

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

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

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

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

Таким образом, цикл for равен O (множитель / 2), получается константа 1/2, поэтому это O (n)

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

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

Наша интуиция заключается в том, что мы можем умножить число на n цифр за n шагов

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

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

Это алгоритм 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;
}

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

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

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

...