Время Сложность сдвига и добавить Умножение

Question

Я пытаюсь выяснить временную сложность смены компьютера и добавить алгоритм умножения на основе изображения ниже:

Таким образом, если целое число является бит и каждый шаг операции принимает единицы времени B, и шаг добавления всегда выполняется, будет ли сложность времени для этого алгоритма O (n * n), который каждый сдвиг и добавляет O (n)?

Answer 1

Если вы подсчитываете битовые операции, вы получаете O (n * (n + m)), когда n - количество бит в наименьшем операнде, а m - количество бит в продукте. (сравните оба операнда и выберите наименьший как множитель, условие выхода цикла - сдвинутый множитель равен нулю). Так как m = n + k, где k - количество бит в мультипликаторе, вы получаете в сущности O (n^2).

Но это нереально на практике.

На большинстве процессоров инструкции по смене (особенно на единицу) и добавление инструкций принимают единицу времени. Поэтому, если вам нужна сложность в единицах машинных команд, сдвиг и добавление умножаются на O (n).