整个项目都托管在了 Github 上：https://github.com/ikesnowy/Algorithms-4th-Edition-in-Csharp
这一节内容可能会用到的库文件有 Measurement 和 TestCase，同样在 Github 上可以找到。
善用 Ctrl + F 查找题目。
即为证明组合计算公式：
C(N, 3)
= N! / [(N - 3)! × 3!]= [(N - 2) * (N - 1) * N] / 3!= N(N - 1)(N - 2) / 6
显然 N 必须大于等于 3。N = 3 时公式正确，只有一种组合。N = 4 时公式正确，只有四种组合。
扩展到 N+1 个数，将 N = N + 1 代入，可得：(N + 1)N(N - 1) / 6N + 1 个数能组成的三位数组合可以这样理解前 N 个数中取三个数的所有组合 +多出的一个数和前 N 个数中的任意取两个数的所有组合即为 N(N-1)(N - 2) / 6 + C(N, 2)变形后即为(N + 1)N(N - 1) / 6
得证。
将 a[i] + a[j] + a[k] 改为 (long)a[i] + a[j] + a[k] 即可。
此时整个式子将按照精度最高（也就是 long）的标准计算。
long.MaxValue = 9223372036854775807 > int.MaxValue * 3 = 6442450941
见代码，这里贴出绘图函数，窗体只是在得到测试结果之后简单调用以下这两个函数。
代码分块↑
时间分析↓
类似于取极限的做法。
a. N
b. 1
c. 1
d. 2N3
e. 1
f. 2
g. N100
a. N + N/2 + N/4 + … = ~2N，线性。
b. 1 + 2 + 4 + … = ~2N，线性。
c. logN * N，线性对数。
最外层循环进行了 N 次比较。
次外层循环进行了 N^2 次比较。
最里层循环进行了 N^3 次比较。
内部 if 语句进行了 N^3 次比较。
if 内部进行了 N(N-1) 次加法。
加起来，~2N^3。
平方级别：直接二层循环遍历一遍。
线性对数：只遍历一遍数组，在遍历过程中用二分查找确认在剩余数组中是否有相等的整数。
二分查找算法↓
/// <summary> /// 利用 Array.Sort 进行优化的查找相等整数对算法。 /// </summary> /// <param name="a">需要查找的数组。</param> /// <returns></returns> static int CountEqualLog(int[] a) { int n = a.Length; int count = 0; Array.Sort(a); int dup = 0; // dup = 重复元素数量-1 for (int i = 1; i < n; i++) { while (a[i - 1] == a[i]) { dup++; i++; } count += dup * (dup + 1) / 2; dup = 0; } return count; }
修改二分查找的结束条件，找到后仍然向左侧寻找，如果还能找到更小的，则返回较小的下标；否则返回当前下标。
这里给出官网上的 Java 实现：StaticSETofInts.java。
howMany() 可以用二分查找实现，在找到一个值后继续向两侧查找，最后返回找到的次数。
由于两个数组都是有序的，可以同时进行比较。
设 i, j 分别为两个数组的下标。如果 a[i] == a[j]，i 和 j 都向后移动一位。如果 a[i] != a[j]，比较小的那个向后移动一位。循环直到某个数组遍历完毕。
这样最后的时间复杂度 ~2N
对象的固定开销用 Object 表示。
a. Accumulator
使用 1.2.4.3 节给出的实现。= int * 1 + double + Object * 1
= 4 * 1 + 8 + 16 * 1 = 32
b. Transaction
= string * 1 + Date * 1 + double * 1 + Object * 1
= (40 + 16 + 4 + 4 + 2N) * 1 + (8 + 32) * 1 + 8 * 1 + 16 * 1
= 128 + 2N
c. FixedCapacityStackOfStrings
= string[] * 1 + string * N + int * 1 + Object * 1
= 24 * 1 + N * (64 + 2C) + 4 * 1 + 16 * 1
= N * (64 + 2C) + 44
= N * (64 + 2C) + 48（填充）
d.Point2D
= double * 2 + Object * 1
= 8 * 2 + 16 * 1
= 32
e.Interval1D
= double * 2 + Object * 1
= 8 * 2 + 16 * 1
= 32
f.Interval2D
= Interval1D * 2 + Object * 1
= (8 + 24) * 2 + 16 * 1
= 80
g.Double
= double * 1 + Object * 1
= 8 * 1 + 16 * 1
= 24
这里给出暴力方法，将最内侧循环换成二分查找即为优化版本。
由于数组已经排序（从小到大），负数在左侧，正数在右侧。 TwoSumFaster 设最左侧下标为 lo，最右侧下标为 hi。 如果 a[lo] + a[hi] > 0, 说明正数太大，hi--。 如果 a[lo] + a[hi] < 0，说明负数太小，lo++。 否则就找到了一对和为零的整数对，lo++, hi--。
ThreeSumFaster 对于数组中的每一个数 a，ThreeSum 问题就等于求剩余数组中所有和为 -a 的 TwoSum 问题。 只要在 TwoSumFaster 外层再套一个循环即可。
先将数组从小到大排序，再遍历一遍即可得到差距最小的两个数。
排序算法需要消耗 NlogN，具体见 MSDN：Array.Sort 方法 (Array)。
遍历找到最小值和最大值即可。
和二分查找的方式类似，先确认中间的值是否是局部最小，如果不是，则向较小的一侧二分查找。
在三个数中比较得到最小值需要两次比较，因此最坏情况下为 ~2lgN 次比较。
算法过程类似于 “滑雪”，从数值较高的一侧向周围数值较小的一侧移动，直到到达“山谷”（局部最小）。
首先在中间行搜索最小值，再将最小值与其上下两个元素比较，如果不满足题意，则“滑向”较小的一侧，矩阵被分为了两半（上下两侧）。
在较小的一侧，找到中间列的最小值，再将最小值与其左右两个元素比较，如果不满足题意，类似的移动到较小的一侧（左右两侧）。
现在查找范围缩小到了原来矩阵的四分之一，递归的进行上述操作，最后可以得到答案。
每次查找最小值都是对行/列进行遍历，遍历耗时和 N 成正比。
首先给出 BitMax 类的官方 Java 实现：BitonicMax.java。
我们使用这个类生成双调数组，并使用其中的 Max() 方法找到双调数组的最大值。
找到最大值之后分别对左右两侧进行二分查找，注意对于升序和降序的数组二分查找的实现有所不同。
BitonicMax 类
using System; namespace _1._4._20 { /// <summary> /// 双调查找类。 /// </summary> public class BitonicMax { /// <summary> /// 生成双调数组。 /// </summary> /// <param name="N">数组的大小。</param> /// <returns></returns> public static int[] Bitonic(int N) { Random random = new Random(); int mid = random.Next(N); int[] a = new int[N]; for (int i = 1; i < mid; ++i) { a[i] = a[i - 1] + 1 + random.Next(9); } if (mid > 0) { a[mid] = a[mid - 1] + random.Next(10) - 5; } for (int i = mid + 1; i < N; ++i) { a[i] = a[i - 1] - 1 - random.Next(9); } return a; } /// <summary> /// 寻找数组中的最大值。 /// </summary> /// <param name="a">查找范围。</param> /// <param name="lo">查找起始下标。</param> /// <param name="hi">查找结束下标。</param> /// <returns>返回数组中最大值的下标。</returns> public static int Max(int[] a, int lo, int hi) { if (lo == hi) { return hi; } int mid = lo + (hi - lo) / 2; if (a[mid] < a[mid + 1]) { return Max(a, mid + 1, hi); } if (a[mid] > a[mid + 1]) { return Max(a, lo, mid); } return mid; } } }主程序
using System; namespace _1._4._20 { /* * 1.4.20 * * 双调查找。 * 如果一个数组中的所有元素是先递增后递减的，则称这个数组为双调的。 * 编写一个程序，给定一个含有 N 个不同 int 值的双调数组，判断它是否含有给定的整数。 * 程序在最坏情况下所需的比较次数为 ~3lgN * */ class Program { static void Main(string[] args) { int[] a = BitonicMax.Bitonic(100); int max = BitonicMax.Max(a, 0, a.Length - 1); int key = a[50]; int leftside = BinarySearchAscending(a, key, 0, max); int rightside = BinarySearchDescending(a, key, max, a.Length - 1); if (leftside != -1) { Console.WriteLine(leftside); } else if (rightside != -1) { Console.WriteLine(rightside); } else { Console.WriteLine("No Result"); } } /// <summary> /// 对升序数组的二分查找。 /// </summary> /// <param name="a">升序数组。</param> /// <param name="key">关键值。</param> /// <param name="lo">查找的左边界。</param> /// <param name="hi">查找的右边界。</param> /// <returns>返回找到关键值的下标，如果没有找到则返回 -1。</returns> static int BinarySearchAscending(int[] a, int key, int lo, int hi) { while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (a[mid] < key) { lo = mid + 1; } else if (a[mid] > key) { hi = mid - 1; } else { return mid; } } return -1; } /// <summary> /// 对降序数组的二分查找。 /// </summary> /// <param name="a">升序数组。</param> /// <param name="key">关键值。</param> /// <param name="lo">查找的左边界。</param> /// <param name="hi">查找的右边界。</param> /// <returns>返回找到关键值的下标，如果没有找到则返回 -1。</returns> static int BinarySearchDescending(int[] a, int key, int lo, int hi) { while (lo < hi) { int mid = lo + (hi - lo) / 2; if (a[mid] > key) { lo = mid + 1; } else if (a[mid] < key) { hi = mid - 1; } else { return mid; } } return -1; } } }
直接将 Contains() 实现为二分查找即可。
普通二分查找是通过除法不断减半缩小搜索范围。
这里我们用斐波那契数列来缩小范围。
举个例子，例如数组大小是 100，比它大的最小斐波那契数是 144。
斐波那契数列如下：0 1 1 2 3 5 8 13 21 34 55 89 144
我们记 F(n) = 144,F(n-1) = 89, F(n-2) = 55。
我们先查看第 0 + F(n-2) 个数，如果比关键值小则直接将范围缩小到 [55, 100]；否则则在[0, 55]之间查找。
之后我们令 n = n-1。
递归上述过程即可完成查找。
根据书中的提示，将二分查找中判断相等的条件改为两个数的差小于等于 1/N2。
第一问：二分查找即可。
第二问：
按照第 1, 2, 4, 8,..., 2^k 层顺序查找，一直到 2^k > F，随后在 [2^(k - 1), 2^k] 范围中二分查找。
这里建立了一个结构体用于返回测试结果：
struct testResult { public int F;// 找到的 F 值。 public int BrokenEggs;// 打碎的鸡蛋数。 }用于测试的方法：
/// <summary> /// 扔鸡蛋，没碎返回 true，碎了返回 false。 /// </summary> /// <param name="floor">扔鸡蛋的高度。</param> /// <returns></returns> static bool ThrowEgg(int floor) { return floor <= F; } /// <summary> /// 第一种方案。 /// </summary> /// <param name="a">大楼。</param> /// <returns></returns> static testResult PlanA(int[] a) { int lo = 0; int hi = a.Length - 1; int mid = 0; int eggs = 0; testResult result = new testResult(); while (lo <= hi) { mid = lo + (hi - lo) / 2; if (ThrowEgg(mid)) { lo = mid + 1; } else { eggs++; hi = mid - 1; } } result.BrokenEggs = eggs; result.F = hi; return result; } /// <summary> /// 第二种方案。 /// </summary> /// <param name="a">大楼。</param> /// <returns></returns> static testResult PlanB(int[] a) { int lo = 0; int hi = 1; int mid = 0; int eggs = 0; testResult result = new testResult(); while (ThrowEgg(hi)) { lo = hi; hi *= 2; } eggs++; if (hi > a.Length - 1) { hi = a.Length - 1; } while (lo <= hi) { mid = lo + (hi - lo) / 2; if (ThrowEgg(mid)) { lo = mid + 1; } else { eggs++; hi = mid - 1; } } result.BrokenEggs = eggs; result.F = hi; return result; }第一问：
第一个蛋按照 √(N), 2√(N), 3√(N), 4√(N),..., √(N) * √(N) 顺序查找直至碎掉。这里扔了 k 次，k <= √(N)。k-1√(N) ~ k√(N) 顺序查找直至碎掉，F 值就找到了。这里最多扔 √(N) 次。
第二问：
按照第 1, 3, 6, 10,..., 1/2k^2 层顺序查找，一直到 1/2k^2 > F，随后在 [1/2k^2 - k, 1/2k^2] 范围中顺序查找。
这里我们同样定义了一个结构体：
struct testResult { public int F;// 测试得出的 F 值 public int BrokenEggs;// 碎掉的鸡蛋数。 public int ThrowTimes;// 扔鸡蛋的次数。 }之后是测试用的方法：
/// <summary> /// 扔鸡蛋，没碎返回 true，碎了返回 false。 /// </summary> /// <param name="floor">扔鸡蛋的高度。</param> /// <returns></returns> static bool ThrowEgg(int floor) { return floor <= F; } /// <summary> /// 第一种方案。 /// </summary> /// <param name="a">大楼。</param> /// <returns></returns> static testResult PlanA(int[] a) { int lo = 0; int hi = 0; int eggs = 0; int throwTimes = 0; testResult result = new testResult(); while (ThrowEgg(hi)) { throwTimes++; lo = hi; hi += (int)Math.Sqrt(a.Length); } eggs++; if (hi > a.Length - 1) { hi = a.Length - 1; } while (lo <= hi) { if (!ThrowEgg(lo)) { eggs++; break; } throwTimes++; lo++; } result.BrokenEggs = eggs; result.F = lo - 1; result.ThrowTimes = throwTimes; return result; } /// <summary> /// 第二种方案。 /// </summary> /// <param name="a">大楼。</param> /// <returns></returns> static testResult PlanB(int[] a) { int lo = 0; int hi = 0; int eggs = 0; int throwTimes = 0; testResult result = new testResult(); for (int i = 0; ThrowEgg(hi); ++i) { throwTimes++; lo = hi; hi += i; } eggs++; if (hi > a.Length - 1) { hi = a.Length - 1; } while (lo <= hi) { if (!ThrowEgg(lo)) { eggs++; break; } lo++; throwTimes++; } result.BrokenEggs = eggs; result.F = lo - 1; result.ThrowTimes = throwTimes; return result; }
实现比较简单，想象两个栈背靠背接在一起，左侧栈负责出队，右侧栈负责入队。
当左侧栈为空时就把右侧栈中的元素倒到左侧栈，这个过程是 O(n) 的。
但在这个过程之前必然有 n 个元素入栈，均摊后即为 O(1)。
每次入队的时候将队列倒转，这样入队的元素就是第一个了。
和用两个栈实现队列的方法类似。
push 的时候把右侧栈内容倒到左侧栈，之后再入栈。
pop 的时候也做相同操作，右侧栈内容进左侧栈，之后再出栈。
enqueue 的时候则将左侧栈内容倒到右侧栈，之后再入队。
steque 作为队列的头部，stack 作为队列的尾部。
pushLeft：直接 push 到 steque 中即可。
pushRight：如果 stack 为空，则直接 enqueue 到 steque 中，否则就 push 到 stack 中。
popLeft：如果 steque 为空，则将 stack 中的元素倒到 steque 中去（steque.push(stack.pop())），然后再从 steque 中 pop。
popRight：如果 stack 为空，则将 steque 中的元素倒到 stack 中去，然后再从 stack 中 pop。
三个栈分别命名为左中右。
左侧栈和右侧栈负责模拟队列，和用两个栈模拟队列的方法类似。
由于是双向队列，左栈和右栈会频繁的倒来倒去，因此每次都只倒一半的元素可以有效减少开销。
有一侧栈为空时，另一侧栈中上半部分先移动到中间栈中，下半部分倒到另一侧栈里，再从中间栈拿回上半部分元素。
这样可以确保接下来的 pop 操作一定是常数级别的。
首先，不需要扩容数组的的操作都只需访问数组一次，M 次操作就是 M 次访问。随后我们有性质， M 次栈操作后额外复制访问数组的次数小于 2M。这里简单证明，设 M 次操作之后栈的大小为 n，那么额外访问数组的次数为：S = n/2 + n/4 + n/8 +...+ 2 < n为了能使栈大小达到 n，M 必须大于等于 n/2因此 2M >= n > S，得证。
因此我们可以得到 M 次操作后访问数组次数的总和 S' = S + M < 3M
Integer = 4(int) + 8(对象开销) = 12
Date = 3 * 4(int * 3) + 8(对象开销) = 20
Counter = 4(String 的引用) + 4(int) + 8(对象开销) = 16
int[] = 8(对象开销) + 4(数组长度) + 4N = 12 + 4N
double[] = 8(对象开销) + 4(数组长度) + 8N = 12 + 8N
double[][] = 8(对象开销) + 4(数组长度) + 4M(引用) + M(12 + 8N)(M 个一维数组) = 12 + 16M + 8MN
String = 8(对象开销) + 3*4(int * 3) + 4(字符数组的引用) = 24
Node = 8(对象开销) + 4*2(引用*2) = 16
Stack = 8(对象开销) + 4(引用) + 4(int) = 16
1. 第一种方案，类似于二分查找，先猜测左边界(lo)，再猜测右边界(hi)，如果边界值猜中的话直接返回，否则：
如果右边界比较热，那么左边界向右边界靠，lo=mid；否则，右边界向左边界靠，hi=mid。其中，mid = lo + (hi – lo)/2。
每次二分查找都要猜测两次，~2lgN。
2. 第二种方案，假设上次猜测值为 lastGuess，本次即将要猜测的值为 nowGuess，通过方程：
(lastGuess + nowGuess)/2 = (lo + hi)/2
可以求得 nowGuess，具体可以查看示意图：
数字是猜测顺序，黑色范围是猜测值的范围（lastGuess 和 nowGuess），绿色的是实际查找的范围（lo 和 hi）。
首先是 Game 类
using System; namespace _1._4._34 { /// <summary> /// 某次猜测的结果。 /// </summary> enum GuessResult { Hot = 1, // 比上次猜测更接近目标。 Equal = 0, // 猜中目标。 Cold = -1, // 比上次猜测更远离目标。 FirstGuess = -2 // 第一次猜测。 } /// <summary> /// 游戏类。 /// </summary> class Game { public int N { get; } // 目标值的最大范围。 public int SecretNumber { get; } // 目标值。 public int LastGuess { get; private set; } // 上次猜测的值 /// <summary> /// 构造函数，新开一局游戏。 /// </summary> /// <param name="N">目标值的最大范围。</param> public Game(int N) { Random random = new Random(); this.N = N; this.SecretNumber = random.Next(N - 1) + 1; this.LastGuess = -1; } /// <summary> /// 猜测，根据与上次相比更为接近还是远离目标值返回结果。 /// </summary> /// <param name="guess">本次的猜测值</param> /// <returns>接近或不变返回 Hot，远离则返回 Cold，猜中返回 Equal。</returns> public GuessResult Guess(int guess) { if (guess == this.SecretNumber) { return GuessResult.Equal; } if (this.LastGuess == -1) { this.LastGuess = guess; return GuessResult.FirstGuess; } int lastDiff = Math.Abs(this.LastGuess - this.SecretNumber); this.LastGuess = guess; int nowDiff = Math.Abs(guess - this.SecretNumber); if (nowDiff > lastDiff) { return GuessResult.Cold; } else { return GuessResult.Hot; } } /// <summary> /// 重置游戏，清空上次猜测的记录。目标值和最大值都不变。 /// </summary> public void Restart() { this.LastGuess = -1; } } }之后是实际测试的方法：
using System; namespace _1._4._34 { /* * 1.4.34 * * 热还是冷。 * 你的目标是猜出 1 到 N 之间的一个秘密的整数。 * 每次猜完一个整数后，你会直到你的猜测距离该秘密整数是否相等（如果是则游戏结束）。 * 如果不相等，你会知道你的猜测相比上一次猜测距离秘密整数是比较热（接近），还是比较冷（远离）。 * 设计一个算法在 ~2lgN 之内找到这个秘密整数，然后设计一个算法在 ~1lgN 之内找到这个秘密整数。 * */ class Program { /// <summary> /// 某种方案的测试结果，包含猜测结果和尝试次数。 /// </summary> struct TestResult { public int SecretNumber;// 猜测到的数字。 public int TryTimes;// 尝试次数。 } static void Main(string[] args) { Game game = new Game(1000); TestResult A = PlayGameA(game); game.Restart(); TestResult B = PlayGameB(game); Console.WriteLine($"SecretNumber:{game.SecretNumber}"); Console.WriteLine("TestResultA:"); Console.WriteLine($"SecretNumber:{A.SecretNumber}, TryTimes:{A.TryTimes}"); Console.WriteLine(); Console.WriteLine("TestResultB:"); Console.WriteLine($"SecretNumber:{B.SecretNumber}, TryTimes:{B.TryTimes}"); } /// <summary> /// 方案一，用二分查找实现，需要猜测 2lgN 次。 /// </summary> /// <param name="game">用于猜测的游戏对象。</param> /// <returns>返回测试结果，包含猜测结果和尝试次数。</returns> static TestResult PlayGameA(Game game) { TestResult result; result.TryTimes = 0; result.SecretNumber = 0; GuessResult guessResult; int hi = game.N; int lo = 1; // 利用二分查找猜测，2lgN while (lo <= hi) { int mid = lo + (hi - lo) / 2; guessResult = game.Guess(lo); result.TryTimes++; if (guessResult == GuessResult.Equal) { result.SecretNumber = lo; return result; } guessResult = game.Guess(hi); result.TryTimes++; if (guessResult == GuessResult.Equal) { result.SecretNumber = hi; return result; } else if (guessResult == GuessResult.Hot) { lo = mid; } else { hi = mid; } } return result; } /// <summary> /// 方案二，根据 (lastGuess + nowGuess)/2 = (lo + hi) / 2 确定每次猜测的值。 /// </summary> /// <param name="game">用于猜测的游戏对象。</param> /// <returns>返回测试结果，包含猜测结果和尝试次数。</returns> static TestResult PlayGameB(Game game) { TestResult result; result.TryTimes = 0; result.SecretNumber = 0; GuessResult guessResult; int hi = game.N; int lo = 1; bool isRightSide = true; // 第一次猜测 guessResult = game.Guess(1); result.TryTimes++; if (guessResult == GuessResult.Equal) { result.SecretNumber = 1; return result; } while (lo < hi) { int mid = lo + (hi - lo) / 2; int nowGuess = (lo + hi) - game.LastGuess; guessResult = game.Guess(nowGuess); result.TryTimes++; if (guessResult == GuessResult.Equal) { result.SecretNumber = nowGuess; break; } else if (guessResult == GuessResult.Hot) { if (isRightSide) { lo = mid; } else { hi = mid; } } else { if (isRightSide) { hi = mid; } else { lo = mid; } } isRightSide = !isRightSide; if (hi - lo <= 1) { break; } } if (game.Guess(lo) == GuessResult.Equal) { result.TryTimes++; result.SecretNumber = lo; } else if (game.Guess(hi) == GuessResult.Equal) { result.TryTimes++; result.SecretNumber = hi; } return result; } } }
1. 一个 Node 对象包含一个 int(泛型 Item) 的引用和下一个 Node 对象的引用。push 操作创建新 Node 对象时会创建一个引用。因此对于第一种情况，压入 n 个 int 类型的元素创建了 N 个 Node 对象，创建了 2N 个引用。
2. 比起上一种情况，每个 Node 对象多包含了一个指向 Integer 的引用。因此对于第二中情况，压入 n 个 int 类型的元素创建了 N 个 Node 对象和 N 个 Integer 对象，比起第一种情况多创建了 N 个引用。
3. 对于数组来说，创建对象只有扩容时重新创建数组对象一种情况，对于 N 次 push 操作只需要 lgN 次扩容，因此创建的对象为 lgN 个。每次扩容都需要重新创建引用，(4 + 8 +...+ 2N)(扩容) + N(每次 push 操作) = 5N - 4 = ~5N
4. 创建引用和上题一样，创建对象则多出了装箱过程，每次 push 都会新建一个 Integer 对象，N + lgN = ~N。
1. N 个 Node<int> 对象的空间开销 = N * (16(对象开销) + 4(int) + 8(下一个 Node 的引用) + 4(填充字节)) = 32N
2. 比起上一题来说，空间开销变为 = N * (16(Node 对象开销) + 8(Integer 对象引用) + (16(Integer 对象开销) + 4(int) + 4(填充字节)) + 8(下一个对象的引用) = 32N + 24N = 56N。
3. 如果不扩容则是 4N，N 个元素最多可以维持 4N 的栈空间（少于四分之一将缩小）。
4. 比起上一题，数组元素变成了引用每个占用 8 字节，还要额外加上 Integer 对象的每个 24 字节。= (8 + 24)N ~ (8 * 4 + 24)N
数据量比较大时才会有比较明显的差距。
FixedCapacityStackOfInts，根据 FixedCapacityOfString 修改而来：
using System; using System.Collections; using System.Collections.Generic; namespace _1._4._37 { /// <summary> /// 固定大小的整型数据栈。 /// </summary> class FixedCapacityStackOfInts : IEnumerable<int> { private int[] a; private int N; /// <summary> /// 默认构造函数。 /// </summary> /// <param name="capacity">栈的大小。</param> public FixedCapacityStackOfInts(int capacity) { this.a = new int[capacity]; this.N = 0; } /// <summary> /// 检查栈是否为空。 /// </summary> /// <returns></returns> public bool IsEmpty() { return this.N == 0; } /// <summary> /// 检查栈是否已满。 /// </summary> /// <returns></returns> public bool IsFull() { return this.N == this.a.Length; } /// <summary> /// 将一个元素压入栈中。 /// </summary> /// <param name="item">要压入栈中的元素。</param> public void Push(int item) { this.a[this.N] = item; this.N++; } /// <summary> /// 从栈中弹出一个元素，返回被弹出的元素。 /// </summary> /// <returns></returns> public int Pop() { this.N--; return this.a[this.N]; } /// <summary> /// 返回栈顶元素（但不弹出它）。 /// </summary> /// <returns></returns> public int Peek() { return this.a[this.N - 1]; } public IEnumerator<int> GetEnumerator() { return new ReverseEnmerator(this.a); } IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); } private class ReverseEnmerator : IEnumerator<int> { private int current; private int[] a; public ReverseEnmerator(int[] a) { this.current = a.Length; this.a = a; } int IEnumerator<int>.Current => this.a[this.current]; object IEnumerator.Current => this.a[this.current]; void IDisposable.Dispose() { this.current = -1; this.a = null; } bool IEnumerator.MoveNext() { if (this.current == 0) return false; this.current--; return true; } void IEnumerator.Reset() { this.current = this.a.Length; } } } }FixedCapacityStack<Item>
using System; using System.Collections; using System.Collections.Generic; namespace _1._4._37 { /// <summary> /// 固定大小的栈。 /// </summary> class FixedCapacityStack<Item> : IEnumerable<Item> { private Item[] a; private int N; /// <summary> /// 默认构造函数。 /// </summary> /// <param name="capacity">栈的大小。</param> public FixedCapacityStack(int capacity) { this.a = new Item[capacity]; this.N = 0; } /// <summary> /// 检查栈是否为空。 /// </summary> /// <returns></returns> public bool IsEmpty() { return this.N == 0; } /// <summary> /// 检查栈是否已满。 /// </summary> /// <returns></returns> public bool IsFull() { return this.N == this.a.Length; } /// <summary> /// 将一个元素压入栈中。 /// </summary> /// <param name="item">要压入栈中的元素。</param> public void Push(Item item) { this.a[this.N] = item; this.N++; } /// <summary> /// 从栈中弹出一个元素，返回被弹出的元素。 /// </summary> /// <returns></returns> public Item Pop() { this.N--; return this.a[this.N]; } /// <summary> /// 返回栈顶元素（但不弹出它）。 /// </summary> /// <returns></returns> public Item Peek() { return this.a[this.N - 1]; } public IEnumerator<Item> GetEnumerator() { return new ReverseEnmerator(this.a); } IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); } private class ReverseEnmerator : IEnumerator<Item> { private int current; private Item[] a; public ReverseEnmerator(Item[] a) { this.current = a.Length; this.a = a; } Item IEnumerator<Item>.Current => this.a[this.current]; object IEnumerator.Current => this.a[this.current]; void IDisposable.Dispose() { this.current = -1; this.a = null; } bool IEnumerator.MoveNext() { if (this.current == 0) return false; this.current--; return true; } void IEnumerator.Reset() { this.current = this.a.Length; } } } }测试函数：
using System; using Measurement; namespace _1._4._37 { /// <summary> /// FixedCapacityStackOfInts 测试类。 /// </summary> public static class DoubleTest { private static readonly int MAXIMUM_INTEGER = 1000000; /// <summary> /// 返回对 n 个随机整数的栈进行 n 次 push 和 n 次 pop 所需的时间。 /// </summary> /// <param name="n">随机数组的长度。</param> /// <returns></returns> public static double TimeTrial(int n) { int[] a = new int[n]; FixedCapacityStackOfInts stack = new FixedCapacityStackOfInts(n); Random random = new Random(DateTime.Now.Millisecond); for (int i = 0; i < n; ++i) { a[i] = random.Next(-MAXIMUM_INTEGER, MAXIMUM_INTEGER); } Stopwatch timer = new Stopwatch(); for (int i = 0; i < n; ++i) { stack.Push(a[i]); } for (int i = 0; i < n; ++i) { stack.Pop(); } return timer.ElapsedTimeMillionSeconds(); } /// <summary> /// 返回对 n 个随机整数的栈进行 n 次 push 和 n 次 pop 所需的时间。 /// </summary> /// <param name="n">随机数组的长度。</param> /// <returns></returns> public static double TimeTrialGeneric(int n) { int[] a = new int[n]; FixedCapacityStack<int> stack = new FixedCapacityStack<int>(n); Random random = new Random(DateTime.Now.Millisecond); for (int i = 0; i < n; ++i) { a[i] = random.Next(-MAXIMUM_INTEGER, MAXIMUM_INTEGER); } Stopwatch timer = new Stopwatch(); for (int i = 0; i < n; ++i) { stack.Push(a[i]); } for (int i = 0; i < n; ++i) { stack.Pop(); } return timer.ElapsedTimeMillionSeconds(); } } }主函数：
using System; namespace _1._4._37 { /* * 1.4.37 * * 自动装箱的性能代价。 * 通过实验在你的计算机上计算使用自动装箱所付出的性能代价。 * 实现一个 FixedCapacityStackOfInts， * 并使用类似 DoublingRatio 的用例比较它和泛型 FixedCapacityStack 在进行大量 push() 和 pop() 时的性能。 * */ class Program { static void Main(string[] args) { Console.WriteLine("测试量\t非泛型耗时（毫秒）\t泛型耗时（毫秒）\t差值"); for (int n = 250; true; n += n) { double time = DoubleTest.TimeTrial(n); double timeGeneric = DoubleTest.TimeTrialGeneric(n); Console.WriteLine($"{n}\t{time}\t{timeGeneric}\t{Math.Abs(time - timeGeneric)}"); } } } }
把 DoublingTest 中调用的函数稍作修改即可。
ThreeSum 测试类
using System; namespace _1._4._38 { /// <summary> /// ThreeSum 测试类。 /// </summary> public static class DoubleTest { private static readonly int MAXIMUM_INTEGER = 1000000; /// <summary> /// 返回对 n 个随机整数的数组进行一次 ThreeSum 所需的时间。 /// </summary> /// <param name="n">随机数组的长度。</param> /// <returns></returns> public static double TimeTrial(int n) { int[] a = new int[n]; Random random = new Random(DateTime.Now.Millisecond); for (int i = 0; i < n; ++i) { a[i] = random.Next(-MAXIMUM_INTEGER, MAXIMUM_INTEGER); } Measurement.Stopwatch timer = new Measurement.Stopwatch(); ThreeSum.Count(a); return timer.ElapsedTime(); } } }
ThreeSum
using System; namespace _1._4._38 { /// <summary> /// 用暴力方法寻找数组中和为零的三元组。 /// </summary> public static class ThreeSum { /// <summary> /// 输出所有和为零的三元组。 /// </summary> /// <param name="a">输入数组。</param> public static void PrintAll(int[] a) { int n = a.Length; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { for (int k = 0; k < n; ++k) { if (i < j && j < k) { if ((long)a[i] + a[j] + a[k] == 0) { Console.WriteLine($"{a[i]} + {a[j]} + {a[k]}"); } } } } } } /// <summary> /// 计算和为零的三元组的数量。 /// </summary> /// <param name="a">输入数组。</param> /// <returns></returns> public static int Count(int[] a) { int n = a.Length; int count = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { for (int k = 0; k < n; ++k) { if (i < j && j < k) { if ((long)a[i] + a[j] + a[k] == 0) { count++; } } } } } return count; } } }
执行 N 次后取平均即可。
修改后的 DoublingTest：
using System; using Measurement; namespace _1._4._39 { /// <summary> /// ThreeSum 测试类。 /// </summary> public static class DoubleTest { private static readonly int MAXIMUM_INTEGER = 1000000; /// <summary> /// 返回对 n 个随机整数的数组进行一次 ThreeSum 所需的时间。 /// </summary> /// <param name="n">随机数组的长度。</param> /// <param name="repeatTimes">重复测试的次数。</param> /// <returns></returns> public static double TimeTrial(int n, int repeatTimes) { int[] a = new int[n]; double sum = 0; Random random = new Random(DateTime.Now.Millisecond); for (int i = 0; i < n; ++i) { a[i] = random.Next(-MAXIMUM_INTEGER, MAXIMUM_INTEGER); } for (int i = 0; i < repeatTimes; ++i) { Stopwatch timer = new Stopwatch(); ThreeSum.Count(a); sum += timer.ElapsedTime(); } return sum / repeatTimes; } } }
N 个数可组成的三元组的总数为：C(N, 3) = N(N-1)(N-2)/3! = ~ (N^3)/6 （组合数公式）[-M, M]中随机 N 次，有 (2M+1)^N 种随机序列（每次随机都有 2M+1 种可能）按照分步计数方法，将随机序列分为和为零的三元组和其余 N-3 个数这些序列中，和为零的三元组有 3M^2 + 3M + 1 种可能。其他不为零的 N-3 个位置有 (2M+1)^(N-3) 种可能。总共有 ((N^3)/6) * (3M^2 + 3M + 1) * (2M+1)^(N-3) 种可能性平均值为：
[((N^3)/6) * (3M^2 + 3M + 1) * (2M+1)^(N-3)] / (2M+1)^N
N^3/16M
这里使用了委托来简化代码。
DoublingRatio
using System; using Measurement; namespace _1._4._41 { public delegate int Count(int[] a); static class DoublingRatio { /// <summary> /// 从指定字符串中读入按行分割的整型数据。 /// </summary> /// <param name="inputString">源字符串。</param> /// <returns>读入的整型数组</returns> private static int[] ReadAllInts(string inputString) { char[] split = new char[1] { '\n' }; string[] input = inputString.Split(split, StringSplitOptions.RemoveEmptyEntries); int[] a = new int[input.Length]; for (int i = 0; i < a.Length; ++i) { a[i] = int.Parse(input[i]); } return a; } /// <summary> /// 使用给定的数组进行一次测试，返回耗时（毫秒）。 /// </summary> /// <param name="Count">要测试的方法。</param> /// <param name="a">测试用的数组。</param> /// <returns>耗时（秒）。</returns> public static double TimeTrial(Count Count, int[] a) { Stopwatch timer = new Stopwatch(); Count(a); return timer.ElapsedTimeMillionSeconds(); } /// <summary> /// 对 TwoSum、TwoSumFast、ThreeSum 或 ThreeSumFast 的 Count 方法做测试。 /// </summary> /// <param name="Count">相应类的 Count 方法</param> /// <returns>随着数据量倍增，方法耗时增加的比率。</returns> public static double Test(Count Count) { double ratio = 0; double times = 3; // 1K int[] a = ReadAllInts(TestCase.Properties.Resources._1Kints); double prevTime = TimeTrial(Count, a); Console.WriteLine("数据量\t耗时\t比值"); Console.WriteLine($"1000\t{prevTime / 1000}\t"); // 2K a = ReadAllInts(TestCase.Properties.Resources._2Kints); double time = TimeTrial(Count, a); Console.WriteLine($"2000\t{time / 1000}\t{time / prevTime}"); if (prevTime != 0) { ratio += time / prevTime; } else { times--; } prevTime = time; // 4K a = ReadAllInts(TestCase.Properties.Resources._4Kints); time = TimeTrial(Count, a); Console.WriteLine($"4000\t{time / 1000}\t{time / prevTime}"); if (prevTime != 0) { ratio += time / prevTime; } else { times--; } prevTime = time; // 8K a = ReadAllInts(TestCase.Properties.Resources._8Kints); time = TimeTrial(Count, a); Console.WriteLine($"8000\t{time / 1000}\t{time / prevTime}"); if (prevTime != 0) { ratio += time / prevTime; } else { times--; } prevTime = time; return ratio / times; } public static double TestTwoSumFast(Count Count) { double ratio = 0; double times = 2; // 8K int[] a = ReadAllInts(TestCase.Properties.Resources._8Kints); double prevTime = TimeTrial(Count, a); Console.WriteLine("数据量\t耗时\t比值"); Console.WriteLine($"8000\t{prevTime / 1000}\t"); // 16K a = ReadAllInts(TestCase.Properties.Resources._16Kints); double time = TimeTrial(Count, a); Console.WriteLine($"16000\t{time / 1000}\t{time / prevTime}"); if (prevTime != 0) { ratio += time / prevTime; } else { times--; } prevTime = time; // 32K a = ReadAllInts(TestCase.Properties.Resources._32Kints); time = TimeTrial(Count, a); Console.WriteLine($"32000\t{time / 1000}\t{time / prevTime}"); if (prevTime != 0) { ratio += time / prevTime; } else { times--; } prevTime = time; return ratio / times; } } }
主方法：
using System; using Measurement; namespace _1._4._41 { /* * 1.4.41 * * 运行时间。 * 使用 DoublingRatio 估计在你的计算机上用 TwoSumFast、TwoSum、ThreeSumFast 以及 ThreeSum 处理一个含有 100 万个整数的文件所需的时间。 * */ class Program { static void Main(string[] args) { int[] a = new int[977]; Random random = new Random(); for (int i = 0; i < 977; ++i) { a[i] = random.Next(977) - 489; } // ThreeSum Console.WriteLine("ThreeSum"); double time = DoublingRatio.TimeTrial(ThreeSum.Count, a); Console.WriteLine($"数据量：977 耗时：{time / 1000}"); double doubleRatio = DoublingRatio.Test(ThreeSum.Count); Console.WriteLine($"数据量：1000000 估计耗时：{time * doubleRatio * 1024 / 1000}"); Console.WriteLine(); //// ThreeSumFast Console.WriteLine("ThreeSumFast"); time = DoublingRatio.TimeTrial(ThreeSumFast.Count, a); doubleRatio = DoublingRatio.Test(ThreeSumFast.Count); Console.WriteLine($"数据量：977 耗时：{time / 1000}"); Console.WriteLine($"数据量：1000000 估计耗时：{time * doubleRatio * 1024 / 1000}"); Console.WriteLine(); //// TwoSum Console.WriteLine("TwoSum"); time = DoublingRatio.TimeTrial(TwoSum.Count, a); doubleRatio = DoublingRatio.Test(TwoSum.Count); Console.WriteLine($"数据量：977 耗时：{time / 1000}"); Console.WriteLine($"数据量：1000000 估计耗时：{time * doubleRatio * 1024 / 1000}"); Console.WriteLine(); // TwoSumFast // 速度太快，加大数据量 a = new int[62500]; for (int i = 0; i < 977; ++i) { a[i] = random.Next(62500) - 31250; } Console.WriteLine("TwoSumFast"); time = DoublingRatio.TimeTrial(TwoSumFast.Count, a); doubleRatio = DoublingRatio.TestTwoSumFast(TwoSumFast.Count); Console.WriteLine($"数据量：62500 耗时：{time / 1000}"); Console.WriteLine($"数据量：1000000 估计耗时：{time * doubleRatio * 16 / 1000}"); Console.WriteLine(); } } }
这里我们把时限设置为一小时，使用上一题的数据估计。
1.ThreeSum 暴力方法在输入倍增时耗时增加 2^3 = 8 倍。1K 数据耗费了 1.15 秒，在一小时内（3600 秒）可以完成 2^3 = 8K 数据。
2.ThreeSumFast 方法在输入倍增时耗时增加 2^2 = 4 倍。1K 数据耗费了 0.05 秒，在一小时内（3600 秒）可以完成 2^8 = 256K 数据。
3.TwoSum 暴力方法在输入倍增时耗时增加 2^2 = 4 倍。8K 数据耗费了 0.14 秒，在一小时内（3600 秒）可以完成 2^10 = 1024K 数据。
4.TwoSumFast 在输入倍增时耗时增加 2^1 = 2 倍。32K 数据耗费了 0.008 秒，在一小时内（3600 秒）可以完成 2^16 = 65536K 数据。
修改后的 DoublingRatio
using System; using Measurement; namespace _1._4._43 { static class DoublingRatio { /// <summary> /// 从指定字符串中读入按行分割的整型数据。 /// </summary> /// <param name="inputString">源字符串。</param> /// <returns>读入的整型数组</returns> private static int[] ReadAllInts(string inputString) { char[] split = new char[1] { '\n' }; string[] input = inputString.Split(split, StringSplitOptions.RemoveEmptyEntries); int[] a = new int[input.Length]; for (int i = 0; i < a.Length; ++i) { a[i] = int.Parse(input[i]); } return a; } /// <summary> /// 使用给定的数组对链栈进行一次测试，返回耗时（毫秒）。 /// </summary> /// <param name="a">测试用的数组。</param> /// <returns>耗时（毫秒）。</returns> public static double TimeTrialLinkedStack(int[] a) { LinkedStack<int> stack = new LinkedStack<int>(); int n = a.Length; Stopwatch timer = new Stopwatch(); for (int i = 0; i < n; ++i) { stack.Push(a[i]); } for (int i = 0; i < n; ++i) { stack.Pop(); } return timer.ElapsedTimeMillionSeconds(); } /// <summary> /// 使用给定的数组对数组栈进行一次测试，返回耗时（毫秒）。 /// </summary> /// <param name="a">测试用的数组。</param> /// <returns>耗时（毫秒）。</returns> public static double TimeTrialDoublingStack(int[] a) { DoublingStack<int> stack = new DoublingStack<int>(); int n = a.Length; Stopwatch timer = new Stopwatch(); for (int i = 0; i < n; ++i) { stack.Push(a[i]); } for (int i = 0; i < n; ++i) { stack.Pop(); } return timer.ElapsedTimeMillionSeconds(); } /// <summary> /// 对链栈和基于大小可变的数组栈做测试。 /// </summary> public static void Test() { double linkedTime = 0; double arrayTime = 0; Console.WriteLine("数据量\t链栈\t数组\t比值\t单位：毫秒"); // 16K int[] a = ReadAllInts(TestCase.Properties.Resources._16Kints); linkedTime = TimeTrialLinkedStack(a); arrayTime = TimeTrialDoublingStack(a); Console.WriteLine($"16000\t{linkedTime}\t{arrayTime}\t{linkedTime / arrayTime}"); // 32K a = ReadAllInts(TestCase.Properties.Resources._32Kints); linkedTime = TimeTrialLinkedStack(a); arrayTime = TimeTrialDoublingStack(a); Console.WriteLine($"32000\t{linkedTime}\t{arrayTime}\t{linkedTime / arrayTime}"); // 1M a = ReadAllInts(TestCase.Properties.Resources._1Mints); linkedTime = TimeTrialLinkedStack(a); arrayTime = TimeTrialDoublingStack(a); Console.WriteLine($"1000000\t{linkedTime}\t{arrayTime}\t{linkedTime / arrayTime}"); } } }
每生成一个随机数都和之前生成过的随机数相比较。
建立一个布尔数组，将每次随机出来的数作为下标，将相应位置的布尔值改为 true，每次随机都检查一遍这个数组是否都是 true。
转载于:https://www.cnblogs.com/ikesnowy/p/7467994.html
相关资源：Algorithms-4th-Edition-in-CSharp：算法（第四版）习题题解C＃版-源码