Обозначение Big-O, вероятно, является неправильным подходом к пониманию временной сложности оператора %. По сути, обозначение big-O измеряет скорость, с которой растет некоторое количество по мере того, как ввод становится все больше и больше. Однако встроенный оператор % работает только с примитивными целочисленными типами, и эти типы имеют максимальный размер при определенном размере (например, 64 бита). В результате мы измеряем сложность, говоря «как масштабируется стоимость % как функция размера входа?»не может быть правильным способом количественной оценки производительности. Если вы действительно хотите дать количественную оценку таким образом, ответом будет «O (1)», поскольку для вычисления модуля двух целых чисел требуется некоторое максимальное время.
Есть два других вопроса, которые вы могли бы задатьхочу посмотреть в. Во-первых, сколько времени занимает выполнение модуля по сравнению с другими операциями, такими как сложение, вычитание и т. Д. ? Этот ответ варьируется от платформы к платформе, но обычно модуль намного медленнее, чем сложение или вычитание. Второе: какова стоимость больших двух модификаций, когда эти целые числа могут быть сколь угодно большими? Это никогда не будет хуже стоимости деления, умножения и вычитания, посколькуВы всегда можете вычислить a - b * (a / b). Обычно это стоит логарифмически медленнее, чем просто умножение .
Надеюсь, это поможет!