这段代码最坏情况下的 big-O 时间复杂度是多少？

Question

我在班上有一个测验，但做得并不好。我想知道是否有人可以向我解释我在这里做错了什么——我们的教授在我们上网时忙于办公时间，所以我想我会在这里发帖。

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

我给出了以下答案：

由于嵌套的 for 循环，上述函数为 O(n^2)。尽管每次迭代时 n 的值都会减半，但它不会对代码的实际运行时间产生影响。

我得到了 3/10，但不幸的是没有解释，所以我不确定我做错了什么以及为什么。这里有人可以向我解释正确答案吗？

Answer 1

如果您正在考虑n成为传入的参数，请注意您怎么说

it ( n) 对代码的实际运行时间没有影响。

如果n对运行时没有影响，它不会是O(n^2)，因为这表明运行时（平方）与n.

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