Временная сложность модульной арифметики

Question

Скажите, что я хотел вычислить (мод n).Какова временная сложность этого?Я использую Matlab, и я не уверен, как Matlab рассчитывает его.Делит ли он на n, вычитает ли целую часть, а затем умножает на n?

Имеет ли смысл спрашивать, «какова временная сложность этого»?

Answer 1

Имеет смысл спросить о сложности времени для длинных чисел a и / или n. Связанное поле называется Теория вычислительных чисел. Например, посмотрите эту книгу .

Обычная целочисленная арифметика, которая, скорее всего, используется Matlab, представляет собой операцию ALU (или несколько операций), выполняемую в постоянное время. В этом случае нужно помнить, что размер целого числа ограничен.

Answer 2

Согласно встроенной справке Matlab рассчитывает MOD (x, y) как:

MOD (x, y) = x - пол (x./y). * Y

где функция floor округляется до минус бесконечности (то есть убирает десятичную часть).

Время выполнения будет постоянным, пока вы не вычислите mod (X, y), где X - вектор, в этом случаеон будет линейно масштабироваться с количеством элементов в векторе