这个函数的 Big-O 复杂度是多少？

Question

def dividing(n):
    while n!=1:
          n=math.floor(n/2)
    return True

有那个代码，我最初的想法是它只有 n 的复杂度，因为它 n 只是输入，没有正方形什么都没有，但是在研究 n/2 时，我发现它很大- O复杂度是Log(m)，所以现在我很困惑，这是log(m)的big-o复杂度吗？如果是，为什么会这样？

Answer 1

假设我们将 while 循环范围内的所有内容都算作 基本操作。

while(invariant) { basic-operation }

然后，要找到 dividing 函数的基本操作次数的渐近上限，我们需要一个上限，给定函数的输入 n，多少次while 循环执行。

我们可以简单地反转循环，它会变得非常明显（忽略地板）：

// The value of 'n' until termination of
// the while loop, in reverse (n here == n_start)
  1   + 2   + 4   + ... + n
= 2^0 + 2^1 + 2^2 + ... + 2^(log2(n))
= sum_{i=0}^{i=log2(n_start)} 2^i

求和表达式运行 i，在我们的上下文中是循环变量，从 0 到 log2(n)，步长为 1，意思是 while 循环运行（忽略地板） log2(n) + 1 次，这意味着 O(log2(n)) 为函数的时间复杂度提供了渐近上限。

Answer 2

在这种情况下，输入是单个数字，我们不能假设算术运算需要常数时间。形式上，算法的“输入大小”应该以位来衡量，用更多的位来表示的数除以更多的时间。

您的代码实际上适用于浮点数，这意味着数字的实际大小与表示它所需的位数没有直接关系（我们将不得不忽略 real 浮点数有固定的位大小，否则“输入大小”和“时间复杂度”的概念就没有意义了）。分析适用于整数的类似算法更简单；让我们假设该算法采用整数并执行 n = n // 2 或 n = n >> 1 而不是 n = math.floor(n / 2)。整数 n 需要 O(log n) 位来表示。

实际时间取决于algorithm used to perform the division；我们可以说时间复杂度是 O(D(n) log n) 其中 D(n) 是除法算法的时间复杂度。除法算法有多种，时间复杂度也不同，这也取决于所使用的乘法算法的时间复杂度。另一方面，由于除以 2 相当于右移 1 位，如果我们将算法编写为使用位移位（或者如果除法算法在这种特殊情况下将其优化为位移位），我们将有 D(n) = O(log n) 因为位移位在位数上需要线性时间。在这种情况下，原始算法的时间复杂度将是 O(log^2 n).

这个函数的 Big-O 复杂度是多少？

What is the Big-O complexity of this function?

big-o