在下面的程序中，递归调用一个助手函数，以便从由数组表示的预序和后序遍历创建一个二进制树。运行时间很快，超过了Leetcode上所有提交的100%。
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;
}
但是，如果我更改helper函数，使最后一个参数(unordered_map)按值传递，则会出现运行时超时错误。我正在努力理解为什么。贴图本身永远不会重新分配，其值也不会重新分配。由于映射是通过值传递的，这意味着每次调用函数时都会调用复制构造函数。这是将函数运行时间增加一个常数因子，还是实际上会改变渐近复杂性？我相信复制构造函数导致了很大的增长，但只是一个常数，因为复制是一个相对于输入的常数时间操作。
是。
如果被复制的参数的大小(或元素数量)是N的函数(而不是常数)，那么它将对实现的渐近时间产生影响(即使它不是递归的。)例如，如果只复制一次O(N)大小的数组，那么你应该在渐近分析中考虑这一点(如果你的阶数已经是O(N)或更高，它可能不会产生影响，但你必须将其计入。)
在递归实现中，显然会有类似O(f(N))的函数调用(O(log(N))用于搜索，O(N)用于排序等)，复制成本会影响甚至支配您的时间。显然，将大小为M的参数传递给被调用N次的函数的成本是O(N * M)。如果大小随每次调用而变化，您仍然可以计算总和(使用标准技术)
即使所讨论的参数的大小是恒定的并且很小(但不能忽略不计)，如果函数被调用O(f(N))次，那么你必须将f(N)添加到渐近时间分析中。
复制本身的成本取决于许多因素，但对于N元素的容器(除非它有一些引用计数/COW优化等)，我敢说复制的成本是O(N)。对于将元素保存在一个(或几个)连续内存块中的容器，复制操作的常量因素将主要取决于单个元素的复制成本，因为容器和内存管理的开销很小。对于链表样式的容器(包括std::map和std::set)，除非您有自定义的内存分配器和非常具体的策略，否则内存分配和遍历的成本将是巨大的(在很大程度上取决于元素总数、堆压力和您的OS/标准库实现等)
根据容器中元素的类型，除了复制成本外，您可能还需要考虑销毁成本。
更新：在看到更多的代码之后(虽然仍然不是一个工作示例，但可能已经足够了)，我可以给你一个更详细的分析。(假设您的输入大小为N，)
函数buildTree有两个主要部分：循环和对helper的递归调用。"循环"部分的复杂性为O(N * log(N))(循环重复N次，每次插入映射大小为对数的std::map，因此为O(N * log(N))
要计算调用helper的成本，我们需要知道它被调用了多少次，它的主体有多贵，以及在每次递归调用中它的输入减少了多少。显然，helper函数总共被调用2 * N + 1次(每个输入元素两次，buildTree中一次)，这显然是O(N)，并且它的输入从未改变大小(它确实改变了，但除了终止条件之外，它的身体的任何部分都不依赖于输入大小。)
无论如何，helper的内部有趣的操作是new(通常被认为是O(1)，这有点简单，但这里可以接受)、std::map(即O(log(N)))中的查找和对helper的调用。如果我们复制vector或map参数中的任何一个(同样，假设每个元素的内存分配和复制是O(1))，则这些调用的代价是O(N)，如果我们不复制，则代价是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 &传递。)