algorithm - 整个算法的时间复杂度是多少？

Question

我是渐近符号的新手，这里是算法。对于时间复杂度来说，最坏情况下的紧密结合是什么？为什么？

F(A,B) {  //A and B are positive
  while A>0 
    print(A mod B)
    A=A div B
}

Answer 1

这个的时间复杂度：

F(A,B) {  //A and B are positive
  while A>0 
    A=A/B
}

等于循环将执行的次数，我们称之为l并且等于 B 必须除以 A 的次数以使“A > 0”为假。

从这个问题，我们知道：

Knuth 的书“计算机编程的艺术”（第 2 卷）的 4.3.1 中的算法 D 以 O(m) 步执行任何长除法，其中m是 A 的位数，所以我们有一个上限。

因此时间复杂度是：*O(l * m)*

现在这个：

print(A mod B)

假设 IO 是恒定的（这在现实世界中当然是不正确的），您需要模本身的复杂性，从this中，我们知道它是：

O（日志 A 日志 B）

并将运行l时间。

结果，我们有：

O(l * (m + log A log B))

Answer 2

这不是一个很好的问题。首先，如果 B 是统一的，算法将永远不会完成。大概 B 必须是 2 或更大。所以我们有 O(log A) 个步骤。但现在的问题是，分工本身是不是“操作”。如果 A 和 B 是无界的，那么它本质上也必须是对数的。但通常代码将在以 32 位或 64 位实现所有除法的处理器上运行，并且不能将数字除以超出范围。所以通常我们说部门是“操作”。

如果我们说除法是对数且 B 很小，那么我们就是 O(log A)^2。