％运算符的C ++时间复杂度是什么？

Question

例如：

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

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

Answer 1

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

您可能还需要研究另外两个问题。第一个是与其他操作（如加法，减法等）相比，执行模数需要多长时间”？答案因平台而异，但通常模数比加法或减法慢得多。第二个是当两个整数可以任意大时，修改两个整数的大O成本是多少？这永远不会比做除法，乘法和减法的成本差，因为您可以总是计算a - b * (a / b)。这样做的成本通常为logarithmically slower than just doing a multiplication。

希望这会有所帮助！