时间戳

首页 > 解决方案 > 按值传递会影响递归算法的渐近时间复杂度吗？

c++ - 按值传递会影响递归算法的渐近时间复杂度吗？

问题描述

在下面的程序中，递归调用一个辅助函数，以便从由数组表示的前序和后序遍历创建二叉树。运行时速度很快，并且 100% 击败了 Leetcode 上的所有提交。

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    unordered_map<int,int> m;
    for(int i=0; i<inorder.size();i++){
        m[inorder[i]]=i;    
    }
    return helper(preorder, inorder, 0,preorder.size()-1,0, inorder.size()-1, m);
}

TreeNode* helper(vector<int>& preorder, vector<int>& inorder, int pStart, int pEnd, int inStart, int inEnd,unordered_map<int,int>& m){
    if(pStart>pEnd || inStart>inEnd) return NULL;

    TreeNode* root= new TreeNode(preorder[pStart]);
    int pivLoc=m[root->val];
    int numsLeft=pivLoc-inStart;
    root->left=helper(preorder, inorder, pStart+1, pStart+numsLeft,inStart, pivLoc-1,m);
    root->right=helper(preorder, inorder, pStart+numsLeft+1, pEnd,pivLoc+1, inEnd,m);
    return root;
}

但是，如果我更改辅助函数以使最后一个参数（unordered_map）按值传递，则会出现运行时超出错误。我试图理解为什么。地图本身永远不会重新分配，它的值也不会重新分配。由于映射是按值传递的，这意味着每次调用函数时都会调用复制构造函数。这是否会使函数运行时间增加一个常数因子，还是实际上会改变渐近复杂度？我相信复制构造函数会导致大量增加，但只是一个常数因子，因为复制是相对于输入的常数时间操作。

标签： c++

解决方案

是的。

如果被复制的参数的大小（或元素数量）是N（而不是常数）的函数，那么它将对实现的渐近时间产生影响（即使它不是递归的。）例如，如果您只复制一次大小的数组O(N)，那么您应该在渐近分析中考虑这一点（如果您的订单已经O(N)或更高，它可能不会产生影响，但您仍然必须将其计算在内。）

在递归实现中，显然您将有诸如O(f(N))函数调用（O(log(N))用于搜索、O(N)排序等）之类的东西，并且复制成本会影响甚至支配您的时间。M显然，将大小参数传递给称为Ntimes的函数的成本是O(N * M)。如果每次调用时大小发生变化，您仍然可以计算总和（使用标准技术。）

即使所讨论的参数的大小是恒定的并且很小（但不可忽略），如果该函数被称为O(f(N))时间，那么您必须添加f(N)到您的渐近时间分析中。

复制本身的成本取决于很多因素，但对于一个N元素容器（除非它有一些引用计数/COW 优化等），我敢说复制的成本是O(N). 对于将元素保存在一个（或几个）连续内存块中的容器，复制操作的常数因素将主要取决于单个元素的复制成本，因为容器和内存管理的开销是小的。对于链表样式的容器（包括std::mapand std::set），除非您有自定义内存分配器和非常具体的策略，否则内存分配和遍历的成本将很大（很大程度上取决于元素总数和堆压力以及您的操作系统/标准库实现等）

根据容器中元素的类型，除了复制成本外，您可能还必须考虑销毁成本。

更新：在看到更多代码之后（虽然仍然不是一个工作示例，但可能已经足够了），我可以给你一个更详细的分析。（假设您输入的大小是N，）

该函数buildTree有两个主要部分：循环和对helper. “循环”部分的复杂性为O(N * log(N))(循环重复N多次，每次插入到std::map地图大小为对数的 a 中，因此O(N * log(N)).

要计算出调用的成本helper，我们需要知道它被调用了多少次，它的主体的成本是多少，以及它的输入在每次递归调用中收缩了多少。显然，该helper函数2 * N + 1总共被调用了几次（每个输入元素两次，一次在 中buildTree），这显然是O(N)，并且它的输入永远不会改变大小（它确实如此，但除了终止条件之外，它的主体的任何部分都不依赖于输入大小。 )

无论如何，在helper's body 中有趣的操作是new（通常认为O(1)这有点简单但在这里可以接受）在std::map（即,）中的查找O(log(N))和对helper. 这些调用的成本是O(N)如果我们复制任何vectorormap参数（再次假设内存分配和复制每个元素是O(1),），O(1)如果我们不复制。

因此，总时间是循环时间加上调用helper时间，调用时间是调用次数乘以每次调用的时间。循环时间为O(N * log(N))，调用次数为O(N)。

每次调用helper的时间是分配一个新节点的时间（O(1)）加上在我们的映射中查找值的时间（O(log(N))）加上再次调用的时间的两倍helper。

如果我们按值传递参数（即任何一个inorder，，preorder或m按值传递），那么每次调用的时间helper将是O(N)，如果我们通过引用传递所有参数，那么那个时间将是O(1)。所以，把它们放在一起，如果我们按值传递我们的大参数，我们会得到：

  O(N * log(N)) + O(N) * [O(1) + O(log(N)) + O(N)]
= O(N * log(N)) + O(N) * O(N)
= O(N * log(N)) + O(N^2)
= O(N^2)

如果我们只通过引用传递，我们将拥有：

  O(N * log(N)) + O(N) * [O(1) + O(log(N)) + O(1)]
= O(N * log(N)) + O(N) * O(log(N))
= O(N * log(N)) + O(N * log(N))
= O(N * log(N))

就是这样。

（附带说明，如果函数的参数不会更改，并且仅通过引用传递以避免复制，则将其作为常量引用传递或传递const &。）

推荐阅读