％运算符的C ++时间复杂度是多少？

Question

例如：

a = 10 ^ 12, b = 93 ^ 7
result = b % a

那么，以大O表示形式的'％'运算符的时间复杂度是多少，以及如何计算？

Answer 1

大O表示法可能是考虑%运算符时间复杂度的错误方法。从根本上讲，big-O表示衡量输入量越来越大时某些数量增长的速率。但是，内置%运算符仅适用于原始整数类型，并且这些类型在特定大小（例如64位）下最大可用。结果，通过说“ %规模成本作为输入大小的函数如何”来衡量复杂性？可能不是量化效果的正确方法。如果您确实想用这种方式量化事物，答案将是“ O（1）”，因为计算两个整数的模量需要一些最大的时间。

您可能还需要研究另外两个问题。首先是与其他操作（例如加法，减法等）相比，执行模数需要多长时间？答案因平台而异，但通常模数比加法或减法慢得多。其次，当两个整数可以任意大时，修改两个整数的big-O成本是多少？这绝不会比执行除法，乘法和减法的成本更糟糕，因为您始终可以进行计算a - b * (a / b)。通常，这样做的代价比仅进行乘法要对数慢。

希望这可以帮助！