Chap1 算法分析基础
1.4看上去也挺重要的，但是我第一遍做的时候没有做，总复习可以做一下
1.1
Let A[1..60] = 11, 12,…, 70. How many comparisons are performed by
Algorithm binarysearch when searching for the following values of x?
(a) 33. (b) 7. (c) 70. (d) 77.
(a) 搜索值33：
- 第一次比较：
- 中间位置：(1 + 60) / 2 = 30.5，向下取整为30
- 中间元素是A[30] = 40（因为A[1] = 11，每个元素递增1）
- 33 < 40，所以在左半部分继续搜索，新区间为A[1..29]
- 第二次比较：
- 中间位置：(1 + 29) / 2 = 15
- 中间元素是A[15] = 25
- 33 > 25，所以在右半部分继续搜索，新区间为A[16..29]
- 第三次比较：
- 中间位置：(16 + 29) / 2 = 22.5，向下取整为22
- 中间元素是A[22] = 32
- 33 > 32，所以在右半部分继续搜索，新区间为A[23..29]
- 第四次比较：
- 中间位置：(23 + 29) / 2 = 26
- 中间元素是A[26] = 36
- 33 < 36，所以在左半部分继续搜索，新区间为A[23..25]
- 第五次比较：
- 中间位置：(23 + 25) / 2 = 24
- 中间元素是A[24] = 34
- 33 < 34，所以在左半部分继续搜索，新区间为A[23..23]
- 第六次比较：
- 只剩一个元素，直接比较
- A[23] = 33
- 找到目标值
总共需要6次比较。
mid的计算是向下取整的
若 x!=A[mid]，要么low=mid+1，要么high=mid-1，一定要记住不是等于mid！
(b) 搜索值7：
由于数组最小值是11，7不在数组中。
需要执行⌊log₂60⌋+1 = 6次比较确定元素不存在。
1.5 选择排序的比较次数（套路题）
Illustrate the operation of Algorithm SELECTION_SORT on the array
[45 33 24 45 12 12 24 12] .
How many comparisons are performed by the algorithm?
算法执行了7+6+5+4+3+2+1=28次比较
1. 选择排序的比较操作固定为 n(n - 1)/2 次，即本体所求
2. 注意要区分“比较次数”和“交换次数”，后者并不固定，可以介于 0 和 (n - 1)次之间
3. 还可能求“赋值操作”的次数：选择排序的赋值操作介于 0 和 3(n - 1) 次之间
ps: 一次交换对应三次赋值
1.6 MOD_SELECTION_SORT
算法 1.16 MODSELECTIONSORT
1
2
3
4
5
6
7
for i ← 1 to n - 1
for j ← i + 1 to n
Copy if A[j] < A[i] then 交换 A[i] 和 A[j]
end for
end for
(a) 算法 MODSELECTIONSORT 执行的最小元素赋值次数是多少？这个最小值在什么情况下达到？
- 最小赋值数量的情况是当数组已经按照非递减顺序排序时。在这种情况下，因为对任何j，A[j] ≥ A[i]都成立，所以内层循环中的if条件永远不会为真，因此不会进行任何交换。
- 最小元素赋值数量：0次
(b) 算法 MODSELECTIONSORT 执行的最大元素赋值次数是多少？注意每次交换操作使用三次元素赋值来实现。这个最大值在什么情况下达到？
- 最坏情况发生在数组按照严格递减顺序排序时（如n, n-1, n-2, …, 2, 1）。在这种情况下：
当i=1时，j将从2到n，每次比较A[j]都小于A[i]，所以将进行(n-1)次交换
当i=2时，j将从3到n，进行(n-2)次交换
当i=3时，j将从4到n，进行(n-3)次交换
依此类推…
总交换次数 = (n-1) + (n-2) + (n-3) + … + 2 + 1 = n(n-1)/2
- 由于 每次交换需要3次元素赋值 ，所以：最大元素赋值数量 = 3 × n(n-1)/2 = 3n(n-1)/2
每次交换操作需要3次赋值操作
可以自己画个数组模拟一下
1.8 求插入排序的比较次数
初始数组: [4,3,12,5,6,7,2,9]
j=2: 比较3和4，交换 → [3,4,12,5,6,7,2,9]，1次比较
j=3: 比较12和4，不交换 → [3,4,12,5,6,7,2,9]，1次比较
j=4: 比较5和12，交换；与4比较，不交换 → [3,4,5,12,6,7,2,9]，2次比较
j=5: 比较6和12，交换；与5比较，不交换 → [3,4,5,6,12,7,2,9]，2次比较
j=6: 比较7和12，交换；与6比较，不交换 → [3,4,5,6,7,12,2,9]，2次比较
j=7: 比较2和12，交换；与7交换；与6交换；与5交换；与4交换；与3交换；与无比较，停止 → [2,3,4,5,6,7,12,9]，6次比较
j=8: 比较9和12，交换；与7比较，不交换 → [2,3,4,5,6,7,9,12]，2次比较
总比较次数：1+1+2+2+2+6+2 = 16次比较
1.10 插入排序vs.选择排序
1）时间复杂度：
两者最坏情况下都是O(n²)
插入排序对部分排序的数组有优势，最好情况可达O(n)
选择排序始终是O(n²)，无论输入如何
2）比较和移动次数：
插入排序：比较次数最坏为n(n-1)/2，移动次数最坏也为n(n-1)/2
选择排序：比较次数恒为n(n-1)/2，移动次数最多为3(n-1)
3）大型记录的影响：
插入排序需要多次移动记录，每次迭代可能涉及多次数据移动
选择排序只在确定位置后移动一次记录
4）结论
对于非常大的记录，选择排序通常更有效率，因为它最小化了记录移动次数。虽然两者比较次数相似，但插入排序的多次移动操作在大记录情况下成本高昂。
1.11. BOTTOMUPSORT算法在数组A[1..16]上的操作
对于数组A[1..16] = [11, 12, 1, 5, 15, 3, 4, 10, 7, 2, 16, 9, 8, 14, 13, 6]，自底向上归并排序的过程如下：
首先将数组分成大小为1的子数组，然后两两合并：
- 合并[11]和[12] -> [11, 12]（1次比较）
- 合并[1]和[5] -> [1, 5]（1次比较）
- 合并[15]和[3] -> [3, 15]（1次比较）
- 合并[4]和[10] -> [4, 10]（1次比较）
- 合并[7]和[2] -> [2, 7]（1次比较）
- 合并[16]和[9] -> [9, 16]（1次比较）
- 合并[8]和[14] -> [8, 14]（1次比较）
- 合并[13]和[6] -> [6, 13]（1次比较）
合并大小为2的子数组：
- 合并[11, 12]和[1, 5] -> [1, 5, 11, 12]（2次比较，比较11与1，11与5）
- 合并[3, 15]和[4, 10] -> [3, 4, 10, 15]（3次比较，比较3与4，15与4，15与10）
- 合并[2, 7]和[9, 16] -> [2, 7, 9, 16]（2次比较，比较2与9，7与9）
- 合并[8, 14]和[6, 13] -> [6, 8, 13, 14]（3次比较，比较8与6，8与13，14与13）
第二轮总计：8次比较
Q: 解释一下这一轮的比较次数
A: 让我们看一下归并过程的具体步骤：
- 比较11和1：1 < 11，所以取1（第1次比较）
- 比较11和5：5 < 11，所以取5（第2次比较）
- 此时第二个数组已经用完，只需检查一下数组2为空（这个判断空数组的步骤不是比较），即可确定将剩下的11和12直接放入结果数组
合并大小为4的子数组：
- 合并[1, 5, 11, 12]和[3, 4, 10, 15] -> [1, 3, 4, 5, 10, 11, 12, 15]（7次比较）
- 合并[2, 7, 9, 16]和[6, 8, 13, 14] -> [2, 6, 7, 8, 9, 13, 14, 16]（7次比较）
最后合并大小为8的子数组：
合并[1, 3, 4, 5, 10, 11, 12, 15]和[2, 6, 7, 8, 9, 13, 14, 16] -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]（15次比较）
总比较次数 = 8 + 10 + 14 + 15 = 47次比较。
从上面这道题可能会得出一个错误的 “规律” ：将一个元素个数为x的数组a和一个元素个数为y的数组b进行归并排序，那么需要的
"比较次数" = x+y-1但是这个想法是错误的！实际上比较次数是随着元素的大小关系而变化的：让我们来看另一个例子：
1.13. BOTTOMUPSORT的最小和最大比较次数
给出一个8个元素的整数数组，求BOTTOMUPSORT的最小和最大比较次数
(a) 最小比较次数：
当数组已经按升序排列时，BOTTOMUPSORT仍需执行所有合并操作。对于长度为8的数组，最小比较次数为：
第一轮（合并长度为1的子数组）：4次比较
第二轮（合并长度为2的子数组）：6次比较
第三轮（合并长度为4的子数组）：7次比较
总计：4 + 6 + 7 = 17次比较
一个实现最小比较次数的数组例子是：[1, 3, 5, 7, 2, 4, 6, 8]
(b) 最大比较次数：
当数组排列方式使得在每次合并操作中都需要最大比较次数时，会达到最大比较次数。对于长度为8的数组，最大比较次数为：
第一轮（合并长度为1的子数组）：4次比较
第二轮（合并长度为2的子数组）：8次比较
第三轮（合并长度为4的子数组）：8次比较
总计：4 + 8 + 8 = 20次比较
一个实现最大比较次数的数组例子是：[2, 4, 6, 8, 1, 3, 5, 7]
1.14
FTF,TTT,FTF,TFF,FTF
1.15
复习一下高数求极限的部分
1.17
从(b)(d)看出：1次交换操作需要3次赋值操作
计算复杂度时，不考虑循环条件中
i<=n-1这样的比较
在这个算法中有“比较、赋值”这两种基本操作，所以计算时间复杂度的时候，就计算这两种操作的执行次数之和：
最好情况(复杂度下限)：
当输入是一个非降序序列，元素比较次数为n-1，元素赋值操作的次数是0，所以总共的执行次数=n-1+0=n-1,即时间复杂度下限Omega(n)的由来最坏情况(复杂度上限)：
当输入是一个非升序序列，元素比较次数为n(n-1)/2，赋值次数为3n(n-1)/2，所以总共的执行次数 =n(n-1)/2+3n(n-1)/2 = 2n(n-1)，即时间复杂度上限O(n^2)的由来
1.18
找到两个递增函数f(n), g(n)，使得 f(n)!=O(g(n)) 且 g(n)!=O(f(n))
1.19
1.20
1.22
1.23
1.25
1.26
Carefully explain the difference between O(1) and Θ(1).
O(1)可以表示常数阶O(1)和低阶，而Θ(1)只能表示常数阶
相对于另一个函数B而言，一个函数A的增长速度较慢，那么就把A叫做 相对 于B低阶的
1.27
1.28
1.29
1.30
.png)
1.34
这种题做起来还是有点吃力，要多看书上的例题！
1.35
Write an algorithm to find the maximum and minimum of a sequence of n
integers stored in array A[1..n] such that its time complexity is
(a) O(n).
线性遍历数组即可
(b) Ω(n log n). 可以采用比较排序，其复杂度为Ω(n log n)，然后从排序后的数组中直接取max/min值
1.37
Consider the element uniqueness problem: Given a set of integers, determine whether two of them are equal. Give an efficient algorithm to solve
this problem. Assume that the integers are stored in array A[1..n]. What
is the time complexity of your algorithm?
答：有三种方法
- 暴力求解:O(n²)
- 先快排再检查：O(nlogn)
- 使用哈希集合（最高效）
1.39
Let S be a set of n positive integers, where n is even. Give an efficient
algorithm to partition S into two subsets S1 and S2 of n/2 elements each
with the property that the difference between the sum of the elements in
S1 and the sum of the elements in S2 is maximum. What is the time
complexity of your algorithm?
可以采取任意一种排序方法，直接将排序后的数组平均分割，复杂度就是排序算法的复杂度
重要的几个排序算法的时间复杂度一定要背下来