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

1. 两种算法的比较

一个求 1 + 2 + 3 + … +100结果的程序 :

int  i,  sum  =  0,  n  =  100;
for(  i  =  1;  i  <=  n;  i++)
{
      sum  =  sum  +  i;
}
printf("%d",sum);

高斯解析道 :
sum = 1 + 2 + 3 + … + 99 + 100
sum = 100 +99 + 98 + … + 2 + 1
2xsum = 101 + 101 + 101 + … + 101 + 101
共 100 个 / 所以 sum = 5050

用程序实现如下 :

1
2
3

int  i,  sum  =  0,  n  =  100;
sum  =  (1+n)  *  n  /  2;
printf("%d",sum);

2. 算法的定义

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

3. 算法的特征

算法具有五个基本特征 : 输入 / 输出 / 有穷性 / 确定性和可行性.

输入输出 :
算法具有零个或多个输入.算法至少有一个输出或多个输出.
有穷性 :
指算法在执行有限的步骤之后,自动结束而不会出现无限循环,并且每一个步骤在可接受的时间内完成.
确定性 :
算法的每一步骤具有确定的含义,不会出现二义性.算法在一定条件下,只有一条执行路径,相同的输入只能有唯一的输出结果.算法的每个步骤被精准定义而无歧义.
可行性 :
算法的每一步都必须是可行的,也就是说,每一步都能够通过执行有限的次数完成.

4. 算法设计的要求

正确性 :
算法的正确性是指算法至少应该具有输入,输出和加工处理无歧义,能正确反映问题的需求,能够得到问题的正确答案.
可读性 :
算法设计的另一目的是为了便于阅读,理解和交流.
健壮性 :
当输入数据不合法时,算法也能做出相关的处理,而不是产生异常或莫名其妙的问题.
时间效率高和存储量低 :
时间效率指的是算法的执行时间,对于同一个问题,如果有多个算法能够解决,执行时间短的算法效率最高,存储量需求指的是算法在执行过程中需要的最大存储空间,主要是指算法程序运行时所占用的内存或外部硬盘存储空间.设计算法应该尽量满足时间效率高和存储量低的需求.花最少的时间,办最大的事.

5. 算法效率的度量方法

事后统计方法 :
这种方法主要是通过设计的好的测试程序和数据,利用计算机时器对不同算法编制的程序的运行时间进行比较,从而确定算法效率的高低. (因受机器的影响,我们考虑不予采纳)
事前分析估算方法 :
在计算机程序编制前,依据统计方法对算法进行估算.一个程序的运行时间,依赖于算法的好坏和问题的输入规模,所谓问题输入规模是指输入量的多少.

第一种算法 :

int  i,  sum  =  0,  n  =  100;    //执行一次
for(  i  =  1;  i  <=  n;  i++)      //执行N+1次
{
      sum  =  sum  +  i;   //执行N次
}
printf("%d",sum);    //执行一次

第二种算法 :

1
2
3

int  i,  sum  =  0,  n  =  100;    //执行一次
sum  =  (1+n)  *  n  /  2;    //执行一次
printf("%d",sum);    //执行一次

显然第一种执行了2n+3次,而第二种算法执行了3次.最终,在分析程序的运行时间时,最重要的是把程序看成是独立于程序设计语言的算法或一系列步骤.

6. 函数的渐近增长

函数的渐进增长 : 给定两个函数 f(n) 和 g(n) ,如果存在一个整数 N ,使得对于所有的 n > N, f(n) 总是比 g(n) 大,那么,我们说 f(n) 的增长渐近快于 g(n).

判断一个算法的效率时,函数中的常数和其他次要项常常可以忽略,而更应该关注主项(最高阶项)的阶数.

某个算法,随着n的增大,它会越来越优于另一个算法,或者越来越差于另一个算法.

7. 算法时间复杂度定义

在进行算法分析时,语句总的执行次数 T(n) 是关于问题规模 n 的函数,进而分析 T(n) 随 n 的变化情况而确定 T(n) 的数量级.算法的时间复杂度,也就是算法的时间量度.记做 : T(n) = O(f(n)).它表示随问题规模 n 的增大,算法执行时间的增长率和 f(n) 的增长率相同,称作算法的渐近时间复杂度.简称为时间复杂度.其在 f(n) 是问题规模 n 的某个函数.

一般情况下, T(n) 增长最慢的算法为最优算法.

推导大 O 阶方法
- 用常数 1 取代运行时间中所有的加法常数.
- 在修改后的运行次数函数中,只保留最高阶项.
- 如果最高阶项在且不是 1 ,则去除与这个项相乘的常数.
常数阶
如高斯算法运行次数 f(n) = 3 ,第一步就是把常数项3改为1,所以为 O(1).
线性阶
如 : for(i = 0; i < n; i++){} 它的循环时间复杂度为 O(n) ,因为循环体中的代码须要执行 n 次.
对数阶
int count = 1; while(count<n){ count = count * 2; }

由于每次 count 乘以 2 之后,就距离 n 更近了一分.也就说说,有多少个 2 相乘后大于 n,则会退出循环. 由 2^x=n 得到 x=log2n.所以这个循环的时间复杂度为O[logn]

平方阶
下面是循环嵌套,它的内循环时间复杂度为 : O(n).

  int  i,j;
  for(i=0;  i<n;  i++)
{
    for(j=0;  j<n;  j++)
    {
          //  时间复杂度为O(1)的程序步骤系列
    }
}

对于外循环,不过是内部这个时间复杂度为 O(n) 的语句,再循环n次.所以这段代码的时间复杂度为 O(n^2).如果外循环的次数改为m,时间复杂度为 O(m*n).

总结出 :
循环的时间复杂度等于循环体的复杂度乘以该循环运行的次数.

  int  i,j;
  for(i=0;  i<n;  i++)
{
    for(j=i;  j<n;  j++)
    {
          //  时间复杂度为O(1)的程序步骤系列
    }
}

由于 i = 0 时,内循环执行了 n 次,当 i = 1 时,执行了 n-1 次,… 当 i = n - 1 时,执行了1次.所以总的执行次数为 :

用大 O 阶的方法,该段代码时间复杂度为 O(n^2).

  int  i,j;
  for(i=0;  i<n;  i++)
{
   function(i);
}
void   function(int count)
{
      print(count);
}

整体的时间复杂度为 O(n).

8. 常见的时间复杂度

常用的时间复杂度所耗费的时间从小到大依次是 :

9. 最坏情况和平均情况

最坏情况运行时间是一种保证,那就是运行时间将不会再坏了.在应用中,这是一种最重要的需求.通常,除非特别指定,我们提到的运行时间都是最坏情况下的运行时间.

平均运行时间是所有情况中最有意义的,因为它是期望的运行时间.

10. 算法空间的复杂度

算法的空间复杂度通过计算算法所需的存储空间实现,算法空间复杂度的计算公式记做 : S(n) = O(f(n)),其中,n 为问题的规模, f(n) 为语句 n 所占存储空间的函数.

11. 总结

算法的定义 :
算法是解决特定问题求解步骤的描述,在计算机中为指令的有限序列,并且每条指令表示一个或多个操作.
算法的特征 :
有穷性,确定性,可行性,输入,输出.
算法的设计要求 :
正确性,可读性,健壮性,高效性和低存储量需求.
算法的度量方法 :
事后统计方法(不科学),事前分析估算方法.
函数的渐近增长 :
给定两个函数 f(n) 和 g(n) ,如果存在一个整数 N ,使得对于所有的 n > N ,f(n) 总是比 g(n) 大,那么,我们说 f(n) 的增长渐近快于 g(n). 可以分析出 : 随着 n 的变大, 它会越来越优于另一算法,或者越来越差于另一算法.
推导大 O 阶 :
- 用常数 1 取代运行时间中所有加法常数
- 在修改后的运行次数函数中,只保留最高阶项
- 如果最高阶项存在且不是1,则去除与这个项相乘的常数
  得到的结果就是大 O 阶.