《挑战程序设计竞赛》笔记
算法复杂度的基石
在程序设计竞赛中，算法的复杂度是衡量算法优劣的重要标准。通过对《挑战程序设计竞赛》一书的学习，我们了解到复杂度主要从最好情况、平均情况和最坏情况三种角度进行估算。由于平均情况的复杂度通常与最坏情况持平，且估算最坏情况的复杂度可以避免后顾之忧，因此在设计算法时，我们一般直接估算最坏情况的复杂度。
书中通过一张详细的表格对几种典型数量级的复杂度进行了比较。表格显示，当输入数据大小 ( n ) 不同时，各种算法的复杂度差异非常明显。例如，当 ( n ) 达到 ( 10^6 ) 时，( O(n^2) ) 算法的复杂度已经高达 ( 10^12 )，而 ( O(n log n) ) 算法的复杂度仅为 ( 10^6 log 10^6 approx 10^6 times 20 = 2 times 10^7 )。这说明，复杂度的选择对算法的效率有着决定性的影响。
此外，书中还提到，现代计算机的处理能力可以在几秒内处理百万或千万级别的运算次数。因此，在设计算法时，我们需要根据输入数据的上限，评估算法在最坏情况下的复杂度，以确保程序具有实用价值。例如，使用 ( O(n^2) ) 算法在 ( n = 200000 ) 时，运算次数将高达 ( 200000^2 = 4 times 10^10 )，这显然无法在合理时间内完成。因此，我们需要设计更高效的算法。
最大利润问题的优化之道
书中通过一个最大利润问题，生动地展示了算法优化的重要性。问题描述如下：给定一系列货币价格 ( R )，计算在 ( j > i ) 的条件下，( R[j] – R[i] ) 的最大值。输入示例1为 ( 6， 3， 1， 3， 4， 3 )，输出为 ( 4 – 1 = 3 )。输入示例2为 ( 3， 4， 3， 2 )，输出为 ( -1 )。
书中首先给出了一个复杂度为 ( O(n^2) ) 的简单算法，但由于其效率低下，无法处理大规模输入。例如，当 ( n = 200000 ) 时，运算次数高达 ( 200000^2 = 4 times 10^10 )，这显然无法在合理时间内完成。因此，书中提出了一个优化算法，将复杂度降低至 ( O(n) )。
优化算法的核心思想是：在遍历数组时，维护当前的最小值 ( textminv ) 和最大利润 ( textmaxv )。对于每个元素 ( R[j] )，我们首先更新 ( textmaxv ) 为 ( max(textmaxv， R[j] – textminv) )，然后更新 ( textminv ) 为 ( min(textminv， R[j]) )。这种方法只需遍历数组一次，即可得到最大利润。
代码实现如下：
int main()
int n;
cin >> n;
int R[MAX];
for (int i = 0; i < n; ++i)
cin >> R[i];
int maxv = -2000000;
int minv = R[0];
for (int i = 1; i < n; ++i)
maxv = max(maxv， R[i] - minv);
minv = min(minv， R[i]);
cout << maxv << endl;
return 0;
排序算法的初步探索
排序是许多算法的基础，其目的是将数据按一定顺序重新排列，以便更容易处理。书中介绍了几种初等排序算法，虽然这些算法的效率较低，但它们的实现相对简单，是学习排序算法的起点。
书中还提到，排序算法的稳定性是需要考虑的重要因素。稳定排序指的是当数据中存在多个键值相等的元素时，这些元素在排序前后顺序不变。例如，表3.3和表3.4展示了稳定排序和不稳定排序的区别。在实际应用中，稳定排序通常更为重要，尤其是在需要保留数据原始顺序的场景下。
此外，书中还提到，排序算法的复杂度是衡量其优劣的重要标准。初等排序算法的复杂度通常为 ( O(n^2) )，而高效排序算法（如快速排序、归并排序）的复杂度为 ( O(n log n) )。这些高效排序算法将在第7章中详细介绍。
通过对《挑战程序设计竞赛》一书的学习，我们不仅掌握了算法复杂度的基本概念，还通过实际问题的优化，深刻理解了算法设计中复杂度优化的重要性。同时，初等排序算法的学习为我们后续学习高效排序算法奠定了基础。