时间戳

首页 > 解决方案 > PreOrder Traversal Iterativ vs Recursive Time Complexity

javascript - PreOrder Traversal Iterativ vs Recursive Time Complexity

问题描述

我正在为我的 Web 应用程序使用树。例如，创建一个个人资料网站，每个个人资料可以有 0..n 个朋友。另外，我想在最好的时间寻找朋友。为此，我使用了二叉搜索树和广度优先搜索 (BFS)。

我测量了我的两个函数在递归和迭代列表中搜索朋友的时间，令我惊讶的是递归函数更快。我认为迭代函数比迭代更快，我只在迭代函数中使用了一次 while 循环，时间复杂度为 O(n)。有人可以解释这里出了什么问题以及为什么递归函数更快：

时间递归：1.3000000035390258

 preorderRec(root){
    if(root === null) {
      return;
    }
    console.log(root.data);
    if(root.left) {
      this.preorderRec(root.left);
    }
    if(root.right) {
      this.preorderRec(root.right);
    }
    return root;

  }

时间迭代：0.997000001117587 

   preOrderIterativ(root) {
if(root === null) {
  return;
}
const stack = [root];
const stack2 = [];
while(stack.length) {
  //const node = stack.pop();
  const node = stack.pop();
  stack2.push(node)
  if(node.left) {
    stack.push(node.left)
  }
  if(node.right) {
    stack.push(node.right)
  }
}

return stack2;

} }

解决方案：问题出在while循环中的console.log。我使用 repl.it 作为编辑器，在我删除 console.log 后，性能得到了提升

标签： javascriptdata-structures

解决方案

在迭代解决方案中，您正在使用另一个数据结构 ( array)。最重要的是，您不断地执行插入push和删除pop操作。这些操作中的每一个都是O(n)时间复杂度。使用您正在使用的递归解决方案，call stack这就是javascript运行的方式。我不知道大O。

推荐阅读