Умножение занимает единицу времени?
У меня следующая проблема
При каких обстоятельствах умножение может рассматриваться как операция с единичным временем?
Но я думал, что умножение всегда считается занимать единицу времени. Был ли я не прав?
3 ответа
Это зависит от того, что N является. Если N это число битов в произвольно большом числе, тогда, когда число битов увеличивается, вычисление произведения занимает больше времени. Однако в большинстве языков программирования и приложений размер чисел ограничен некоторым разумным количеством битов (обычно 32 или 64). В аппаратных средствах эти числа умножаются за один шаг, который не зависит от размера числа.
Когда число битов является фиксированным числом, таким как 32, тогда не имеет смысла говорить об асимптотической сложности, и вы можете рассматривать умножение как O(1) операция с точки зрения любого алгоритма вы смотрите. Когда может стать сколь угодно большим, как с Java BigInteger класс, то умножение зависит от размера этих чисел, так же как и память, необходимая для их хранения.
Только в тех случаях, когда вы выполняете операции с двумя числами, of numeric type (здесь акцент, не вдаваясь в двоичные детали), вам просто нужно предположить, что выполняемая операция имеет только постоянное время.
Он не определяется как единичное время, но, точнее, постоянный интервал времени, который не меняется, даже если мы увеличиваем размер числа, но на самом деле для вычисления больших чисел в действительности используется немного больше времени. Их обычно считают тривиальными, если только умножаемые числа не слишком велики, например BigIntegers in Java,так далее.
Но, как только мы переходим к выполнению умножения двоичных строк, наша сложность возрастает, и наивный метод дает сложность O(n^2).
Итак, для упрощения, мы выполняем умножение на основе разделения и завоевания, также известное как алгоритм умножения Карацубы, который имеет сложность O(n^1,59), которая уменьшает общее число умножений и сложений до некоторого меньшего числа умножений и некоторые из дополнений.
Надеюсь, я не ошибся в этом вопросе. Если так, пожалуйста, предупредите меня, чтобы я мог удалить этот ответ. Если я правильно понял вопрос, то другой ответ, размещенный здесь, кажется неполным.
Выражение единицы времени немного неоднозначно (и AFAIK мало используется).
Истинное единичное время достигается, когда умножение выполняется за один такт. Это редко происходит на современных процессорах.
Если время выполнения умножения не зависит от конкретных значений операндов, мы можем сказать, что оно выполняется за постоянное время.
Когда длина операнда ограничена, так что время никогда не превышает заданную продолжительность, мы также говорим, что операция выполняется в постоянное время.
Эта постоянная длительность может использоваться как единица измерения времени выполнения, так что вы учитываете "умножения" вместо секунд (ops, flops).
Наконец, вы можете оценить производительность алгоритма с точки зрения количества умножений, которые он выполняет, независимо от времени, которое он занимает.