看不懂CLRS问题4-2案例2
Cannot understand CLRS Problem 4-2 case 2
问题：
4-2 Parameter-passing costs
Throughout this book, we assume that parameter passing during procedure calls takes constant time, even if an N-element array is being passed. This assumption is valid in most systems because a pointer to the array is passed, not the array itself.
This problem examines the implications of three parameter-passing strategies:
- An array is passed by pointer. Time Theta(1)
2. An array is passed by copying. Time Theta(N), where N is the size of the array.
- An array is passed by copying only the subrange that might be accessed by the called procedure. Time Theta(q-p+1) if the subarray A[p..q] is passed.
a. Consider the recursive binary search algorithm for finding a number in a sorted array (see Exercise 2.3-5 ). Give recurrences for the worst-case running times of binary search when arrays are passed using each of the three methods above, and give good upper bounds on the solutions of the recurrences. Let N be the size of the original problem and n be the size of a subproblem.
b. Redo part (a) for the MERGE-SORT algorithm from Section 2.3.1.
我无法理解如何解决通过复制两种算法传递数组的情况 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) 表示呢？ N怎么变成Theta符号中的n？
N和n感觉有些联系。我无法理解它们之间的联系以及它们在解决方案中的应用方式。
似乎 N 代表整个数组长度，n 是当前块大小。
但是当您从全长 n=N 开始时，公式实际上只利用初始值 - 例如，查看 T(n/4) 得到 T(N/4)，所以到处都是 n===N。
在这种情况下，您可以将 n 替换为 N。
我的回答不会很理论化，但也许这种 "more empirical" 方法可以帮助您弄明白。还要检查 Master Theorem (analysis of algorithms) 以便更轻松地分析递归算法的复杂性
先解决二分查找：
通过指针
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
问题：
4-2 Parameter-passing costs
Throughout this book, we assume that parameter passing during procedure calls takes constant time, even if an N-element array is being passed. This assumption is valid in most systems because a pointer to the array is passed, not the array itself. This problem examines the implications of three parameter-passing strategies:
- An array is passed by pointer. Time Theta(1)
2. An array is passed by copying. Time Theta(N), where N is the size of the array.
- An array is passed by copying only the subrange that might be accessed by the called procedure. Time Theta(q-p+1) if the subarray A[p..q] is passed.
a. Consider the recursive binary search algorithm for finding a number in a sorted array (see Exercise 2.3-5 ). Give recurrences for the worst-case running times of binary search when arrays are passed using each of the three methods above, and give good upper bounds on the solutions of the recurrences. Let N be the size of the original problem and n be the size of a subproblem.
b. Redo part (a) for the MERGE-SORT algorithm from Section 2.3.1.
我无法理解如何解决通过复制两种算法传递数组的情况 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) 表示呢？ N怎么变成Theta符号中的n？
N和n感觉有些联系。我无法理解它们之间的联系以及它们在解决方案中的应用方式。
似乎 N 代表整个数组长度，n 是当前块大小。
但是当您从全长 n=N 开始时，公式实际上只利用初始值 - 例如，查看 T(n/4) 得到 T(N/4)，所以到处都是 n===N。
在这种情况下，您可以将 n 替换为 N。
我的回答不会很理论化，但也许这种 "more empirical" 方法可以帮助您弄明白。还要检查 Master Theorem (analysis of algorithms) 以便更轻松地分析递归算法的复杂性
先解决二分查找：
通过指针
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 相同