2018-5-23
1.4.3 # 解答 # 见代码，这里贴出绘图函数，窗体只是在得到测试结果之后简单调用以下这两个函数。
代码 # public static void PaintLinear(double[] testResult) { //新建一个绘图窗口 Form2 linear = new Form2(); linear.Show(); //新建画布 Graphics canvas = linear.CreateGraphics(); //获取窗口区域 Rectangle rect = linear.ClientRectangle; //计算单位长度（十等分） int unitY = rect.Height / 10; int unitX = rect.Width / 10; //获取中心区域（上下左右增加 10% 的内补） Rectangle center = new Rectangle(rect.X + unitX, rect.Y + unitY, unitX * 8, unitY * 8); //绘制坐标系 canvas.DrawLine(Pens.Black, center.X, center.Y, center.X, center.Y + center.
...
2018-5-23
1.4.4 # 解答 #
2018-5-23
1.4.5 # 解答 # 类似于取极限的做法。
a. $N$
b. $1$
c. $1$
d. $2N^3$
e. $1$
f. $2$
g. $\frac{N^{100}}{2^n}$
2018-5-23
1.4.6 # 解答 # a. N + N/2 + N/4 + … = ~2N，线性。
b. 1 + 2 + 4 + … = ~2N，线性。
c. NlogN，线性对数。
2018-5-23
1.4.7 # 解答 # 最外层循环进行了 N 次比较。
次外层循环进行了 N^2 次比较。
最里层循环进行了 N^3 次比较。
内部 if 语句进行了 N^3 次比较。
if 内部进行了 N(N-1) 次加法。
加起来，~2N^3。
2018-5-23
1.4.8 # 解答 # 平方级别：直接二层循环遍历一遍。
线性对数：
先对数组排序，然后遍历一遍数组，在遍历过程中计算重复元素的数量，
然后用公式 $1+2+\cdots+n-1=n(n-1)/2$ 计算重复整数对的数量。
代码 # /// <summary> /// 暴力查找数组中相等的整数对。 /// </summary> /// <param name="a">需要查找的数组。</param> /// <returns></returns> static int CountEqual(int[] a) { var n = a.Length; var count = 0; for (var i = 0; i < n; i++) { for (var j = i + 1; j < n; j++) { if (a[i] == a[j]) count++; } } return count; } /// <summary> /// 利用 Array.
...
2018-5-23
1.4.9 # 解答 # 由题意可得：
$$ T(2N_0)=2^bT\newline T(4N_0)=2^b(2^bT)=2^{2b}T\newline ……\newline T(2^rN_0)=2^{rb}T $$
设：
$$ N=2^rN_0 $$
则：
$$ r=log_2(\frac{N}{N_0}) $$
所以：
$$ T(N) = 2^{log_2(\frac{N}{N_0})b}T $$
2018-5-23
1.4.10 # 解答 # 修改二分查找的结束条件，找到后仍然向左侧寻找，如果还能找到更小的，则返回较小的下标；否则返回当前下标。
代码 # public static int Rank(int key, int[] a, int lo, int hi) { if (hi < lo) return -1; var mid = (hi - lo) / 2 + lo; if (a[mid] == key) { var mini = Rank(key, a, lo, mid - 1); if (mini != -1) return mini; return mid; } if (a[mid] < key) { return Rank(key, a, mid + 1, hi); } return Rank(key, a, lo, mid - 1); }
2018-5-23
1.4.11 # 解答 # 这里给出官网上的 Java 实现：StaticSETofInts.java。
howMany() 可以用二分查找实现，在找到一个值后继续向两侧查找，最后返回找到的次数。
代码 # /// <summary> /// 有序数组，能够快速查找并自动维护其中的顺序。 /// </summary> public class StaticSeTofInts { private readonly int[] _a; /// <summary> /// 用一个数组初始化有序数组。 /// </summary> /// <param name="keys">源数组。</param> public StaticSeTofInts(int[] keys) { _a = new int[keys.Length]; for (var i = 0; i < keys.Length; i++) { _a[i] = keys[i]; } Array.Sort(_a); } /// <summary> /// 检查数组中是否存在指定元素。 /// </summary> /// <param name="key">要查找的值。</param> /// <returns>存在则返回 <c>true</c>，否则返回 <c>false</c>。</returns> public bool Contains(int key) { return Rank(key, 0, _a.
...
2018-5-23
1.4.12 # 解答 # 由于两个数组都是有序的，可以同时进行比较。
设 i, j 分别为两个数组的下标。
如果 a[i] == a[j]，i 和 j 都向后移动一位。
如果 a[i] != a[j]，比较小的那个向后移动一位。
循环直到某个数组遍历完毕。
这样最后的时间复杂度 ~2N
代码 # var a = new[] { 2, 3, 4, 10 }; var b = new[] { 1, 3, 3, 5, 10, 11 }; // 2N 次数组访问，数组 a 和数组 b 各遍历一遍 for (int i = 0, j = 0; i < a.Length && j < b.Length;) { if (a[i] < b[j]) { i++; } else if (a[i] > b[j]) { j++; } else { Console.
...