无法理解CLRS问题4-2例2
问题是：
4-2参数传递费用 在整本书中，我们假设在过程调用期间传递参数需要恒定的时间，即使传递N元素数组也是如此。这个假设在大多数系统中是有效的，因为指向数组的指针被传递，而不是数组本身。这个问题研究了三种参数传递策略的含义：
- 数组通过指针传递。时间Theta(1)
2.通过复制传递数组。时间Theta(N)，其中N是数组的大小.
- 数组仅通过复制被调用过程可能访问的子范围来传递。时间Theta(q-p+1)，如果子数组Ap.q被传递。
a.考虑在排序数组中查找数字的递归二进制搜索算法(见练习2.3-5 )。在使用上述三种方法中的每一种方法传递数组时，给出二进制搜索在最坏情况下的运行次数的递归，并给出递归解的良好上界。设N是原问题的大小，n是子问题的大小。
b.重做2.3.1节中的合并排序算法的(a)部分.
我很难理解如何解决案例2的重复问题，在这种情况下，数组是通过对两个算法的复制传递的。
以案例2的二进制搜索算法为例，给出的递推公式是T(n)=T(n / 2)+Theta(N)。我对此一点也不介意。
以下是我在网上找到的一个正确答案：
T(n) = T(n/2) + cN = 2cN + T(n/4) = 3cN + T(n/8) = Sigma(i =0 to LGN-1) (2^i cN / (2^i)) = cNlgn = Theta(nlgn)
我很难理解第二行是如何得到最后一行的答案的。为什么不代表它在Theta(Nlgn)？在Theta表示法中，N怎么能变成n？
N和n感觉有点联系。我很难理解它们之间的联系，以及如何在解决方案中应用它们。
回答 2
Stack Overflow用户
发布于 2019-08-14 04:33:51
看起来N代表完整的数组长度，n是当前的块大小。
但是，当您从全长n=N开始时，公式实际上只利用初始值--例如，查看T(n/4) for T(N/4)，所以n===N无处不在。
在这种情况下，可以用N代替n。
Stack Overflow用户
发布于 2019-08-14 13:39:37
我的答案不是很理论性的，但也许这种“更经验主义”的方法会帮助你找到答案。还检查主定理(算法分析)，以便更容易地分析递归算法的复杂性
让我们先解决二进制搜索：
- 指针式
O(logN)-就像迭代的二进制搜索一样，会有logN调用，每个调用都具有O(1)复杂性。 - 复制整个数组
O(NlogN)-因为对于函数的每个logN调用，我们都复制N元素 - 只复制已访问的子数组
O(N)--这个没有那么明显，但是可以很容易地看到复制的子数组的长度，N，N/2，N/4，N/8.所有这些条件之和将是2*N
现在是合并排序算法：
O(NlogN)-与a3相同的方法，迭代子数组的长度为N、(N/2, N/2)、(N/4, N/4, N/4, N/4).O(N^2)-我们对排序函数进行2*N调用，每个调用都具有复制整个数组的O(N)复杂性。O(NlogN)-我们将只复制我们将迭代的子数组，因此复杂性将与b1中的相同。
https://stackoverflow.com/questions/57487984
复制相似问题
腾讯云开发者
