什么是算法

算法是解决特性问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。

// 问题：解决 1 + 2 + 3 + ... + 100 的计算问题。两种算法实现

// 算法1：循环相加
int i, sum = 0, n = 100;
for(i = 1; i <= n; i++){
    sum = sum + i;
}
printf(" %d ", sum);

// 算法2：求和公式
int i, sum = 0, n = 100;
sum = (1 + n) * n / 2;
printf(" %d ", sum);

1.算法的定义

算法：(Algorithm)
- 一个有限指令集
- 接受一些输入（有些情况下不需要输入）
- 产生输出
- 一定在有限步骤之后终止
- 每一条指令必须：
  - 有充分明确的目标，不可以有歧义
  - 计算机能处理的范围之内
  - 描述应不依赖于任何一种计算机语言以及具体的实现手段

2.算法的特性和设计要求

（1）算法的5个特性

a.有穷性
- 一个算法必须总是在执行有穷步之后结束，且每一个步骤都在有穷的时间内完成。
b.确定性
- 算法中的每一条指令必须有明确的含义，读者理解时不会产生二义性。并且，任何条件下，相同的输入只能得出相同的输出。
c.可行性
- 算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。
d.输入
- 一个算法可以有零个或者多个输入。
e.输出
- 一个算法可以有一个或者多个输出。

（2）算法的设计要求

a.正确性
- 算法应当满足具体问题的需求。
- “正确”的四个层次
  - 第一层：算法程序没有语法错误
  - 第二层：算法程序对于合法的输入数据能够产生满足要求的输出结果
  - 第三层：算法程序对于非法的输入数据能够得出满足规格说明的结果
  - 第四层：算法程序对于精心选择的，甚至于刁难的测试数据都有满足要求的输出结果
b.可读性
- 算法主要是为了人的阅读与交流，其次才是计算机的执行。可读性强有助于读者理解、调试和修改。
c.健壮性
- 当输入非法数据时，算法也能做相应的处理，而不是产生异常或莫名其妙的结束。
d.效率与低存储量的需求
- 效率：算法执行的时间，执行时间短的算法效率高。
- 存储量：算法执行中需要多大内存。

3.算法的度量方法（空间和时间）

（1）什么是好的算法

空间复杂度S(n)
- 根据算法写成的程序在执行时占用存储单元的长度。这个长度往往与输入数据的规模有关。空间复杂度过高的算法可能导致使用的内存超限，导致程序非正常中断。
时间复杂度T(n)
- 根据算法写成的程序在执行时耗费时间的长度。这个长度往往也与输入数据的规模有关。时间复杂度过高的低效算法可能导致我们在有生之年都等不到运行的结果。

（2）算法的存储空间需求——空间复杂度

// 问题：打印1到N的全部正整数。两种算法实现

// 算法1：for循环实现
void PrintN ( int N )
{  int i;
   for ( i=1; i<=N; i++ ){
     printf("%d\n", i );
   }
   return;
}

//算法2：递归实现
void PrintN ( int N )
{  if ( N ){
     PrintN( N - 1 );
     printf("%d\n", N );   
   }
   return;
}

/* 结果展示：
      分别令 N = 100， 1000， 10000， 10000， ......
      for循环模式：不管N等于多大，都可以打印出来。
      递归模式：当N大到一定程度时，程序爆掉，直接跳出程序。
   结果分析：
      递归占用内存空间较大，输入规模变大时，导致爆栈（递归依赖于 栈 来实现）*/

空间复杂度

空间复杂度(space complexity)作为算法所需存储空间的量度，记作： S(n) = O(f(n)) ；其中，n是问题规模的大小。

（3）算法效率的度量——时间复杂度

关于时间复杂度的算法示例：
问题：一元多项式f(x)=a0 + a1x + … + an-1xn-1 + anxn, 求x在某一点处的取值。

// 问题：计算一元多项式在给定点x处的取值。两种算法

// 算法1：小白程序员
double f( int n, double a[], double x ){
  int i;
  double p = a[0];
  for( i=1; i<=n; i++ )
    p += (a[i] * pow(x, i));    // 在每个循环内部，执行了 i次 乘法运算。
  return p;
}

// 算法2：正常程序员
double f( int n, double a[], double x){
  int i;
  double p = a[n];
  for( i=n, i>0, i--)
    p = a[i-1] + x*p;    //在每个循环内部，只执行了 1次 乘法运算。
  return p;
}

/* 结果展示：
      分别赋值进行计算，并各自循环 1e7 次，查看两个程序执行的快慢情况。
      算法2 明显消耗时间比 算法1 要短。
   结果分析：
      乘除 比 加减 更加消耗时间，而 算法1 中的乘除次数明显比 算法2 中的乘除次数多。因此 算法2 的算法效率更高。*/

4）复杂度的渐进表示

当我们在分析算法复杂度时，没有必要一步一步地去数把每个操作做了多少次。我们关心的只是：随着要处理的数据的规模的增大，复杂度增长的性质。
在上述“时间复杂度的算法例子”中，只需要知道算法1 是 n2 在起主要作用，而算法2 是 n 在起主要作用。当 n 变大时，算法1 比算法2 耗时更大即可。

推导大O阶方法
- 用常数1取代运行时间中的所有加法常数；
- 在修改后的运行次数中，只保留最高阶项；
- 如果最高阶项存在且不是1，则去除与这个项相乘的常数。
推导大O阶的几个例子：
- O(1)阶例子
  注意：是O(1)而不是O(3)
```
int i, sum = 0, n = 100;
sum = (1 + n) * n / 2;
printf(" %d ", sum);
```
- O(n)阶例子
```
int i;
for(i = 1; i <= n; i++){
    printf(" %d ", i);
}
```
- O(n2)阶例子
```
// 例子1：j循环时的初始值为1
int i,j;
for(i = 1; i <= n; i++){
    for(j = 1; j <= n; j++){
        printf(" %d ", i);
    }
}

// 例子2：j循环时的初始值是i
int i,j;
for(i = 1; i <= n; i++){
    for(j = i; j <= n; j++){
        printf(" %d ", i);
    }
}
```
  - 例子1分析：两层循环，各自循环n次，总的执行次数是 n + n + … + n = n * n = n2，因此时间复杂度是O(n2)
  - 例子2分析：两层循环，外层循环n次，内层循环(n-i)次，因此总的执行次数是 n + (n – 1) + (n – 2) + … + 2 + 1 = n(n + 1)/2 = n2/2 + n/2。只保留最高阶并去除最高阶系数，得到时间复杂度为O(n2)
- O(logn)阶例子
```
int count = 1;
whie(count < 2){
    count = count * 2;
}
```
  - 例子分析：每次循环count都乘以2，因此当 2x >= n 时，退出循环。得到执行次数 x = log2n。时间复杂度即为O(logn)

常用复杂度的表示

常用的复杂度
函数、输入规模n、复杂度的图标
每秒钟10亿指令计算机的运行时间表
- 因此，越小的复杂度越好。
复杂度分析小窍门
- 如果两段算法分别有复杂度T1(n)=O(f1(n))和T2(n)=O(f2(n))，则：
  - T1(n) + T2(n) = max( O(f1(n)), O(f2(n)) )
  - T1(n) * T2(n) = O( f1(n) * f2(n) )
- 若T(n)是关于n的k阶多项式，那么T(n)=O(nk)
- 一个for循环的时间复杂度等于循环次数乘以循环体代码的复杂度。
- if-else结构的复杂度取决于if的条件判断复杂度和两个分支部分的复杂度，总体复杂度取三者中最大。