我在理解算法的时间复杂性时遇到问题。
让我们以第一个示例为例，采用此算法在二进制搜索树中进行搜索：
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时结束？
最后：
在二进制搜索树中查找值的最坏情况下的时间复杂度是多少？最坏的情况是当您必须下降到最深的叶子时。通常，n节点的二叉树可以具有depth O(n)。（考虑到每个右孩子都是叶子而左孩子向下下降的情况。）但是，如果维护平衡的二叉搜索树（例如红黑树），则可以保证高度为O(log n)。这是在红黑树中进行键查找操作的最坏情况下的运行时间。
您的函数f定义为：
f(a, b) = f(a − 1, b − 3) 如果 a > 0f(a, b) = b 否则我们可以通过归纳证明a，评估需要调用的f(a, b)任何非负值。在基本情况下，用，被称为一次。对于正数，假定称为时间。然后评估require =对的调用。（顺便说一句，我们可以观察到这一点，并实现一个恒定时间的实现。）aafa == 0faf(a - 1, b)a - 1f(a, b)a - 1 + 1aff(a, b) = b - 3*a
每个递归算法都可以转换为迭代算法，该算法模拟在其上执行递归函数调用的堆栈。观察计算机执行迭代以实现递归程序。更深刻地讲，图灵机是迭代的。计算机科学的一个公理是，可以使用图灵机来计算所有可以计算的东西。Lambda演算没有提供比Turing机更大的计算能力。
递归算法通常比迭代算法占用更多的时间和空间，因为它们需要为每个函数调用在堆栈上分配一个新的帧。
如果以每个函数调用都位于尾部位置的方式编写递归函数，这意味着该调用不会返回需要进一步计算的中间值，则它是尾部递归函数。递归计算不依赖于递归调用的参数以外的任何值。因此，对函数的最终调用会立即产生最终结果，而无需返回递归调用链。
编译器可以以重新使用当前帧的方式来实现尾递归，而不必在堆栈上分配新的帧。例如，需要方案编译器来执行此操作。所得的计算具有迭代的性能特征，但是代码具有递归的表达优势。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句