algorithm - 迭代和递归算法的时间复杂度

Question

我无法理解算法的时间复杂度。

让我们以这个算法在二叉搜索树中进行搜索作为第一个例子:

def search_iteratively(key, node): 
     current_node = node
     while current_node is not None:
         if key == current_node.key:
             return current_node
         elif key < current_node.key:
             current_node = current_node.left
         else:  # key > current_node.key:
             current_node = current_node.right
     return None

那么，这个时间复杂度怎么计算呢？

让我们以这个递归算法为例:

int f(int a, int b) 
{ 
    if (a > 0)
        return f(a − 1, b − 3); 
    else 
        return b;
}

因此，我假设该算法的时间复杂度为 O(a)，因为结束条件仅取决于 a 参数。

如果我写下来:

T(a, b) = O(1) where a <= 0
T(a, b) = T(a-1, b-3) where a > 0

T(a, b) = 
T(a-1, b-3) = 
T(a-1, b-3) + T(a-2, b-6) = 
T(a-1, b-3) + T(a-2, b-6) + T(a-3, b-9)

那么，我怎么知道这是线性时间复杂度呢？就因为递归会在a小于1时结束？

最后:

• 是否可以将每个递归算法转换为迭代？
• 递归算法的速度通常是 slover比迭代？
• 我们可以用循环代替尾递归吗？

Answer 1

在二叉搜索树中查找值的最坏情况时间复杂度是多少？最坏的情况是你必须下降到最深的叶子。一般来说，n 个节点的二叉树的深度可以是 O(n)。 (想想每个右 child 都是叶子而左 child 一直向下下降的情况。)但是，如果您维护一个平衡的二叉搜索树，例如 red-black tree。 ，您的高度保证为 O(log n)。这是红黑树中 key-find 操作最坏情况下的运行时间。

您的函数 f 定义为:

• f(a, b) = f(a − 1, b − 3) 如果 a > 0
• f(a, b) = b 否则

我们可以通过对 a 的归纳来证明，对于 a 的任何非负值，评估 f(a, b) 需要 a 调用 f。在基本情况下，a == 0，f 仅被调用一次。对于正 a，假设 f(a - 1, b) 被调用 a - 1 次。然后评估 f(a, b) 需要 a - 1 + 1 = a 调用 f。 (顺便说一下，我们可以观察到 f(a, b) = b - 3*a 并得出一个恒定时间的实现。)

每个递归算法都可以转换为迭代算法，该算法模拟执行递归函数调用的堆栈。观察计算机执行迭代来实现你的递归程序。更深刻地说，图灵机是迭代的。计算机科学的公理是，所有可以计算的东西都可以用图灵机计算。 lambda 演算提供的计算能力并不比图灵机强。

递归算法通常比迭代算法占用更多的时间和空间，因为它们需要为每个函数调用在堆栈上分配一个新的帧。

如果递归函数的编写方式使得每个函数调用都处于尾部位置，这意味着调用不会返回需要进一步计算的中间值，则它是尾递归函数。递归计算不依赖于递归调用的参数以外的任何值。因此，对函数的最终调用会立即产生最终结果，无需返回递归调用链。

编译器可以通过重用当前帧而不是在堆栈上分配新帧的方式实现尾递归。例如，需要 Scheme 编译器来执行此操作。计算结果具有迭代的性能特点，但代码具有递归的表达优势。