算法分析的基本介绍

分析算法意味着需要预测算法所需要的资源。一般来说，我们更想要度量计算时间。
通过分析某个问题的几种候选算法，我们可能会分析出不止一个可行的候选算法，但在这个过程中，我们往往可以抛弃几个较差的算法。
在本书中我们假定使用一种通用的单处理器计算模型——随机访问机（RAM）作为我们的实现技术。
在RAM模型中，指令一条接一条地执行，没有并发操作。
RAM模型中包含真实计算机中常见的指令：算术指令，数据移动指令和控制指令。每条这样的指令所需的时间都为常量。
简单来说，本书中简化了复杂的内存层次模型，计算精度问题，以及特殊指令。

插入排序算法的分析

输入规模和运行时间的基本介绍

输入规模：
输入规模的最佳概念依赖于研究的问题。
例如：排序中输入规模是输入的项数，图的最短路径问题中的输入规模则是该图中的顶点数和边数。
运行时间：
一个算法在特定输入上的运行时间是指执行的基本操作数或步数。

插入排序算法分析

注：对于Θ符号(将在后续章节给出精确定义)，这里统一写作O。
时间复杂度
对于n个数字的最坏情况，我们第一次需要执行for循环中的语句一次，第二次需要执行for循环中的语句两次，以此类推，第n-1次需要执行for循环中语句n-1次。所以我们得到总执行次数1+2+3+…+n-1。根据等差数列求和公式，我们可以得到最坏情况下，我们需要执行n(n-1)/2次。我们保留最高阶，并去掉系数最终得到时间效率O(n^2)。
*空间复杂度
空间复杂度为O(1)，除了创建了一个存储当前需要插入数的变量，并没有额外内存开销。

对于最坏情况与平均情况的分析

我们往往更加集中于求解最坏情况运行时间，即对于规模为n的任何输入，算法的最长运行时间。
在特定情况下，我们也会对一个算法的平均情况运行时间感兴趣，这点将在后续谈到。
其中也包括对于概率分析技术，随机化算法的探究。

增长量级

为了研究我们真正感兴趣的运行时间的增长率和增长量级。对于n趋于无穷大的时候，我们舍去了低阶项。
可以想象成为高数中对于n趋于无穷大时，(x^2+x)/x^2=1。这里的x就被舍去了。

练习

2.2.1用Θ记号表示函数n^3/1000-100n^2-100n+3
直接舍去后面低阶的项，得到答案 Θ(n3) 。
2.2.2考虑排序存储在数组A中的n个数：首先找出A中的最小元素并将其与A[1]中的元素进行交换。接着，找出A中的次最小元素并将其与A[2]中的元素进行交换。对A中前n−1个元素按该方式继续。该算法称为选择算法，写出其伪代码。该算法维持的循环不变式是什么？为什么它只需要对前n−1个元素，而不是对所有n个元素运行？用Θ记号给出选择排序的最好情况与最坏情况运行时间。

  1. void select_sort(vector<int>& A,int n){
  2.     for(int i = 0;i < n;i++){
  3.         int mina = i;
  4.         for(int j = i+1;j < n;j++){
  5.             if(A[j] < A[mina]){
  6.                 mina = j;
  7.             }
  8.         }
  9.         if(mina != i){
  10.             int tmp = A[i];
  11.             A[i] = A[mina];
  12.             A[mina] = tmp;
  13.         }
  14.     }
  15. }

维持的循环不变式：在第i次操作之后，保证数组A中前i-1个元素已经排好，保证前i-1个是数组中最小的，第二小的，一直到i-1小的元素。
因为第n-1次操作后，数组A中前n-1个元素已经排好序，而最后一个元素肯定就是下一次要挑选的第n大的元素。所以只用n-1次就可以完成n个数的排序。
最好：Θ(n^2) , 最坏： Θ(n^2)
2.2.3再次考虑线性查找问题(参见练习2.1-3)。假定要查找的元素等可能地为数组中的任意元素，平均需要检查输入序列的多少元素？最坏情况又如何呢？用Θ记号给出线性查找的平均情况和最坏情况运行时间。证明你的答案。
平均要检查n/2个，Θ(n)
最坏情况要检查n个，Θ(n)
2.2.4应如何修改一个算法，才能使之具有良好的最好情况运行时间？
针对最好情况下出现的数据，直接输出最好情况下出现的结果。
或者针对性书写算法逻辑。