迭代和递归算法的时间复杂度
我在理解算法的时间复杂性方面有问题。
让我们举第一个例子，用这个算法在二叉搜索树中进行搜索：
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;
}
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)
-
null
共有1个答案
至于树搜索算法的复杂性--试着在每次迭代中考虑一些变化。提示：考虑current_node在树中的深度。
试着用归纳法来证明这种特殊情况下的线性复杂性。您知道T(0，x)将以一个调用结束，这将是您的基础。试着证明T(n，x)将执行n个递归调用。
- 存在一个定理，即每个迭代算法都可以转化为递归算法，反之亦然
- 如果在不进行任何优化的情况下递归和迭代地实现相同的算法，递归将会更慢，因为有函数调用--必须在堆栈上分配一个新的帧，然后必须弹出它
- 在大多数情况下用循环代替尾递归相对容易
-
所以我在理解为什么递归DFS和迭代DFS的时间复杂度相同时遇到了一些问题，也许有人能给我一个简单的解释？ 提前谢了。
-
我想澄清一下O（N）函数。我正在使用SICP。 考虑书中生成伪代码递归过程的阶乘函数： 我不知道如何测量步数。也就是说，我不知道“步骤”是如何定义的，所以我使用书中的语句来定义步骤： 因此，我们可以计算n！通过计算（n-1）！将结果乘以n。 我想这就是他们所说的一步。对于一个具体的例子，如果我们跟踪（阶乘5）， 阶乘（1）=1=1步（基本情况-恒定时间） 阶乘（2）=2*阶乘（1）=2步 阶乘（3
-
我有一个算法可以检查是否可以解决游戏行。游戏行是一个正整数数组，其中最后一个元素为 0。游戏标记从索引 0 开始，沿着数组移动它所在的整数指示的步数。 例如，[1，1，0]返回true，而[1，2，0]返回false。标记也可以向左或向右移动以解决游戏。也就是说，[3，3，2，2，0]是可解的。 我尝试了一些游戏行示例，并计算了最坏情况下的时间复杂度： 其他情况下给我的数字，我找不到与输入大小的关
-
我想用尽可能多的方法解决塔式料斗问题，并计算每种方法的时间复杂性（仅用于自我练习）。解决方案之一是： 我知道递归时间复杂度计算的一般想法，但我在分析注释行（在 for 循环内）时遇到了麻烦。通常我用 ）计算时间复杂度，并用一般表达式（例如 T（n-k））降低它，直到我达到基本情况并且可以用 n 表示 k，但是 for 循环的时间复杂度是多少？
-
这是一个使用两个递归调用对数组进行排序的算法。我试图粗略地计算其时间复杂度，但不确定。我知道两个for循环需要n次，但是递归调用怎么办，我如何计算它们呢？任何人都可以用简单的数学方法帮助计算。