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

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时递归就会结束？

最后：

• 我们真的可以把每一个递归算法转换成迭代算法吗？
• 递归算法的速度通常比迭代要快吗？
• 我们能用循环代替尾递归吗？

Answer 1

在二叉树中查找值的最坏情况时间复杂度是多少？最坏的情况是，你必须下降到最深的叶子。通常，二叉树的n节点可以有深度O(n)。(想象一下这样一种情况:每一个右孩子都是一片叶子，而左边的孩子却一直向下下降。)但是，如果您维护平衡的二进制搜索树(如红黑树 )，则可以保证O(log n)的高度。这是红黑树中查找密钥操作最坏的运行时间。

您的函数f定义为：

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

我们可以通过在a上的归纳来证明，对于任何非负值的a，计算f(a, b)都需要对f进行a调用。在基本情况下，使用a == 0时，只调用一次f。对于正的a，假设f(a - 1, b)称为a - 1时间。然后，评估f(a, b)需要a - 1 + 1 =对f的a调用。(顺便说一句，我们可以观察到f(a, b) = b - 3*a并达到一个固定时间的实现。)

每个递归算法都可以转换为一个迭代算法，该算法模拟执行递归函数调用的堆栈。注意到计算机执行迭代来实现递归程序。更深刻的是，图灵机器是迭代的。计算机科学的一个公理是，所有可以计算的东西都可以用图灵机来计算。lambda微积分没有比图灵机提供更大的计算能力。

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

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

编译器可以实现尾递归，这样就可以重用当前帧，而不必在堆栈上分配新帧。例如，方案编译器需要这样做。结果的计算具有迭代的性能特点，但代码具有递归的表达优势。

Answer 2

至于树搜索算法的复杂性，请尝试在每次迭代中考虑一些变化。提示:想想树中current_node的深度。

在这种特殊情况下，尝试使用归纳法来证明线性复杂性。您知道，T(0，x)将以单个调用结束，这将是您的基础。尝试证明T(n，x)将执行n个递归调用。

• 有一个定理，每一个迭代算法都可以转换成递归，反之亦然。
• 如果您在没有任何优化的情况下实现相同的算法，递归和迭代递归就会慢一些，因为有函数调用--必须在堆栈上分配一个新帧，然后必须弹出它。
• 在大多数情况下，用循环代替尾递归相对容易。

Answer 3

二叉树算法最多访问树中的每个节点一次，否则二叉树中存在一个循环，这是一个矛盾。此外，在最坏的情况下，它至少访问每个节点一次。因此，访问节点的次数是Theta(n)，而且由于每次访问都需要Theta(1)时间，最坏的运行时间是Theta(n)。

我们“知道”一个重复问题的解决办法是通过归纳证明。在你的例子中，基础是

T(0，b) =c对任何b

任何b的诱导催化反应为T(n，b) <= c(n+1)。

诱导步骤是

T(n，b) <= c+ T(n-1，b3) <= c+ cn = c(n+1)。

由此得出T(n) = O(n)。

不，递归算法不一定慢，是的，循环可以用尾递归代替。