以下程序的时间复杂度是 O(1) 吗？

Question

这是判断数字是否稀疏的代码

def isSparse(n):
   if n & (n >> 1):
      return False
   return True

时间复杂度是O(1)?

Answer 1

不，复杂度不是O(1):

该函数使用简单的表达式和单个测试。对于 n 的小值，所有这些都在常数时间内运行，因此复杂度应该是 O(1)。这适用于 n 的相当小的值，通常为 32 位长。
python 支持 n 的任意大整数值，直至可用内存。对于非常大的数字，>> 1 和 & 操作所花费的时间与表示 n 所需的内存字数成正比。这意味着对于 n.
的极大值，时间复杂度为 O(log(n))

在python中，函数isSparse的复杂度是O(1)如果n是一个常规的 32 位 int 并增加到 O(log(n)) 对于非常大的 n.

这里有一个测试来证明这个结果：

import timeit

def isSparse(n):
   if n & (n >> 1):
      return False
   else:
      return True

def test():
   # measure timing overhead
   clock = timeit.default_timer
   overhead = 1e10
   for _ in range(100):
      t = clock()
      t = clock() - t
      if overhead > t: overhead = t

   for i in range(24):
      p = 2 ** i - 1
      x = 2 ** p
      rep = 10
      tt = 1e10
      for _ in range(rep):
         t = clock()
         for _ in range(100):
            v = isSparse(x)
         t = clock() - t
         if tt > t: tt = t
      t = (tt - overhead) / rep
      print("isSparse(2**%d): %s, %.3fus, t/log(n)=%.3fns" %
            (p, v, t * 1e6, t / (p|1) * 1e9))

test()

输出：

isSparse(2**0): True, 2.194us, t/log(n)=2194.406ns
isSparse(2**1): True, 3.953us, t/log(n)=3953.301ns
isSparse(2**3): True, 4.015us, t/log(n)=1338.334ns
isSparse(2**7): True, 4.319us, t/log(n)=617.015ns
isSparse(2**15): True, 4.275us, t/log(n)=285.000ns
isSparse(2**31): True, 4.757us, t/log(n)=153.455ns
isSparse(2**63): True, 3.864us, t/log(n)=61.341ns
isSparse(2**127): True, 4.112us, t/log(n)=32.378ns
isSparse(2**255): True, 4.069us, t/log(n)=15.956ns
isSparse(2**511): True, 5.492us, t/log(n)=10.747ns
isSparse(2**1023): True, 6.589us, t/log(n)=6.441ns
isSparse(2**2047): True, 7.442us, t/log(n)=3.635ns
isSparse(2**4095): True, 15.696us, t/log(n)=3.833ns
isSparse(2**8191): True, 16.141us, t/log(n)=1.971ns
isSparse(2**16383): True, 25.743us, t/log(n)=1.571ns
isSparse(2**32767): True, 35.646us, t/log(n)=1.088ns
isSparse(2**65535): True, 105.032us, t/log(n)=1.603ns
isSparse(2**131071): True, 142.656us, t/log(n)=1.088ns
isSparse(2**262143): True, 268.022us, t/log(n)=1.022ns
isSparse(2**524287): True, 623.609us, t/log(n)=1.189ns
isSparse(2**1048575): True, 1073.612us, t/log(n)=1.024ns
isSparse(2**2097151): True, 2112.068us, t/log(n)=1.007ns
isSparse(2**4194303): True, 4423.266us, t/log(n)=1.055ns
isSparse(2**8388607): True, 9155.862us, t/log(n)=1.091ns

Answer 2

不，不是。它与位数成线性比例。

这是 O(log N)

查看这个简单的代码

>>> import timeit
>>> def isSparse(n):
...    if n & (n >> 1):
...       return False
...    return True
... 
>>> x_1000="isSparse({})".format(10**1000)
>>> x_10000="isSparse({})".format(10**10000)
>>> x_100000="isSparse({})".format(10**100000)
>>> timeit.timeit(x_1000, globals=globals())
0.38640813998063095
>>> timeit.timeit(x_10000, globals=globals())
2.778634059999604
>>> timeit.timeit(x_100000, globals=globals())
26.778618280019145```

以下程序的时间复杂度是 O(1) 吗？

Is time complexity of following program is O(1)?

python

time-complexity

bit-manipulation

bitwise-operators