Intereting Posts
Как передавать данные между несколькими состояниями Lua (multithreading)? Ошибка: выбор пользовательских типов данных в c Проверьте, содержит ли строка другой C Могу ли я искать каталог и подкаталоги для файлов заголовков? Does -fomit-frame-pointer * всегда * опустить fp? ошибка compilin: поля должны иметь постоянный размер: расширение переменной длины массива в структуре никогда не будет поддерживаться в исходном коде Android 2.3.4 Как проверить тип макроса C Разделить массив символов на два массива символов Создайте простой HTTP-сервер в C Не выставлять символы из используемой библиотеки в собственной статической библиотеке строковый массив с символом мусора в конце сохраняя более 2-х мощностей 31 на 32-битной системе Случайный float в C с использованием getrandom Двусторонняя связь между родительским и дочерним Является ли 0 восьмеричным или десятичным числом в C?

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

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

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

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

 #include  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)))) является правильным способом выразить это, хотя (я думаю?) Это технически правильно. Может ли кто-нибудь объяснить это?

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) .

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

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

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

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

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

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

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

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

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

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

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

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

В двоичном формате это использует 1-битный сдвиг, 1-битный тест и двоичный add, чтобы построить весь ответ. Каждая из этих операций – 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; } 

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

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

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