如果两个算法都具有O(1)的性能,为什么一个算法比另一个算法更快

Question

如果我有一个非常大的数字X, (978678567445456455878909099775523213255436445691200897623461676543789287 948754875435250392049320487584759329 454754875487589457244076477592458249)

我有两个算法可以计算输入数是否可被4整除(即n%4 == 0).由于模运算需要O(1),如果它们都是O(1),为什么一种算法会优于另一种算法.我怎么能证明只比较最后两位数(2)的那个实际上比另一个好？

算法1:

n:= Input 
if n divisible by 4, let output :=0 
else output :=1

算法2:

m:=last two digits of input n
if m divisible by 4, let output:=0 
else output:=1

Answer 1

1. 算法1不是O(1).它的运行时间与输入数字的位数成正比,因此它是O(log n).

2. 谈论具有恒定输入的函数的运行时间是没有意义的.运行时间是关于渐近的,而不是特定单个实例需要多长时间.

3. Big O表示法不区分常量.相反,只有两个运行时间在彼此的恒定倍数内时才是"相同的".换句话说,即使两个算法可能具有"相同"的大O符号(如果我们想要更精确,实际上是大的θ符号),在渐近情况下,实际上可能比另一个更快.