这段代码最糟糕的bigO时间复杂度是多少？

Question

我在班上有一次测验，成绩不太好。我想知道是否有人能向我解释我在这里做错了什么——我们搬到网上后，我们的教授办公时间太多了，所以我想我应该在这里发帖

def functionB(n):
  for i in range(1,6):
    for j in range(i,6):
      n = n // 2
  return n

我的回答如下：

The above function is O(n^2) because of the nested for-loops. Although the value of n is being cut in half upon each iteration, it does not have an impact on the actual run time of the code.

我得到了3/10的分数，但不幸的是没有任何解释，所以我不确定我错了什么，为什么。这里有人能向我解释正确答案吗

Answer 1

@Carcigenicate建议的方法是正确的。在这里，我将添加一些内容。 代码段的时间复杂度为O（1），即恒定时间。如果我把两个范围边界都包含在性质中，那么它将精确运行21次（6+5+4+3+2+1）。因此，该方法的返回值为n/2^21。所以在按位概念中，如果我们考虑余数，我们可以说给定的数字已经右移了21次，即n是十进制数

Answer 2

如果您认为n是传入的参数，请注意您是如何说的

it (n) does not have an impact on the actual run time of the code.

如果n对运行时没有影响，它就不会是O(n^2)，因为这表明运行时是以n为单位（二次）伸缩的

这个函数看起来像是O(1)。无论输入如何，函数都将始终完全相同地运行。它总是精确地运行15次，因为n与循环的运行次数无关。程序的运行时间完全由给range的硬编码参数决定，这些参数永远不会改变