数据结构二(算法)

一.算法的定义

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

二.算法的定义

算法具有五个特性:输入输出,有穷性,确定性和可行性

• 输入输出
  算法具有零个或多个输入
  算法至少有一个多个输出,输出的形式可以是打印输出,也可以返回一个或多个值等
• 有穷性
  有穷性:指算法在执行有限的步骤后,自动结束而不会出现无限循环,并且每一个步骤在可接受的时间内完成
• 可行性
  可行性:算法的每一步都必须是可行的,也就是说,每一步都能通过执行有限次数完成

三.算法设计的要求

• 正确性
  正确性:算法的正确性是指算法至少应该具有输入,输出和加工处理无歧义性,能正确反映问题的需求,能够得到问题的正确答案
  算法正确的四个层次:
  1)算法程序没有语法错误
  2)算法程序对于合法的输入数据能够产生满足需求的输出结果
  3)算法程序对于非法的输入数据能够得出满足规格说明的结果
  4)算法程序对于精心选择的,甚至刁难的测试数据都有满足要求的输出结果
  一般情况下,把层次3作为一个算法是否正确的标准
• 可读性
  可读性:算法设计的另一目的是为了便于阅读,理解和交流
• 健壮性
  健壮性:当输入数据不合法时,算法也能做出相关处理,而不是产生异常或莫名其妙的结果
• 时间效率高和存储量低
  时间效率是指算法的执行时间
  数据算法应该满足时间效率高和存储量低的需求

算法效率的度量问题

• 事后统计方法
  事后统计方法:这种方法主要通过设计好的测试程序和数据,利用计算机计时器对不同算法编制的程序的运行时间进行比较,从而确定算法效率的高低
  有很大的缺陷:
  1)必须依靠算法事先编好程序,这通常需要大量的时间和精力
  2)时间的比较依赖计算机硬件和软件等环境因素
  3)算法的测试数据设计困难
  所以这种方法一般不进行考虑
• 事前分析估算方法
  事前分析估算方法:在计算机程序编制前,依据统计方法对算法进行估算
  分析算法在计算机上运行所消耗的时间取决因素:
  1.算法采用的策略,方法(算法好坏的根本)
  2.逻辑产生的代码质量(由软件支持)
  3.问题的输入规模
  4.机器执行指令的速度(硬件性能)

一个程序的运行时间,依赖于算法的好坏和问题的输入规模.问题的输入规模是指输入量的多少

ok,让我们活动下脑子,比较两个求和的算法

//第一种算法
int i , sum = 0 , n = 100; //执行1次
for ( i = 1; i < n ; i++) //执行 n + 1次
{ 
 sum  = sum + 1; //执行n次
 }
 print ("%d",sum);//执行1次
 //第二种算法
 int sum = 0 , n = 100; //执行1次
 sum  = (1 + n) * n / 2; //执行1次
 print("%d",sum);//执行1次

第一种算法执行了 1 + n + 1 + n + 1 = 2n + 3,
第二种算法执行了 1 + 1 + 1 = 3次.算法的第一条和最后一条语句是一样的,所以我们只需要关心中间部分就可以了,我们把循环看成一个整体,忽略头尾循环判断的开销,那么这两个算法其实就是 n次与1次的差距.如果这个效果不明显的话,在举个例子

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

这个算法的执行次数对于相同的输入规模 n = 100,要多于前面的两种算法,这个算法的执行时间随着n的增加也将远远大于前面两种算法

n^2

测试运行时间最可靠的方法就是计算对运行时间有消耗的基本操作的执行次数.运行时间与这个计数成正比

三,函数的渐进增长

• 一元一次方程的对比

A: 2x + 3 , B: 3x + 1

x < 2 A的效率不如B
x = 2 两种算法效率相同
x > 2 A的效率就由于算法B了,随着n的增加,算法A比算法B越来越好
所有我们得出结论,算法A要比算法B要好
结论:输入规模x在没有限制的情况下,只要超过一个数值X,这个函数总是大于另一个函数,我们称函数是渐进增长的
**函数的渐进增长:给定两个函数f(n)和g(n),如果存在一个整数N,使得对于所有的n > N,f(n)总比g(n)大,那么我们就说f(n)的增长渐快于g(n),其中我们可以忽略不影响算法变化的加法常数.
一元一次方程,最高项的常数越大,算法的效率越低

• 一元二次与一元一次的对比

C : y = 4x + 8, D :y = 2x^2 + 1

4x+8 = 2x^2 + 1
解得 x = sqrt(2.5) + 1 ,大约等于2.58
其中y是比较次数
n <= 3 ,C要差于D
n > 3, C要优于 D,在后来更是远远胜过D

• 去掉常数项

C : 4x, D: 2x^2

• 去掉与最高次项相乘的常数

C : 4x D:x^2
去掉与x相乘的常数,或者去掉常数项,算法C的次数随x的增长,都要远远小于算法D,也就是睡与最高次项相乘的常数并不重要
一元二次方程和一元一次方程进行对比,不管最高项的常数,二次效率要低于一次方程

• 一元二次方程和一元三次方程的对比

E:y = 2x^2 + 3x+1 ,F:y = 2x^3 + 3x+ 1

x = 1 两种算法效率相同
x > 1,E的效率要优于F,随着x的增长,差异越来越大

最高次项的指数大的,函数随着n的增长,结果也变得增长的特别快
判断一个算法效率时,函数中的常数和其他次要项长长可以忽略,应该关注主项(最高阶项)的阶数

屏幕快照 2016-09-14 下午4.19.01.png B1CB8FB7-FA9A-4737-88D7-1897D285AFCB.png

当n的值变得非常大的时候,3n+ 1已经没法跟2n^2的结果进行比较,算法G已经趋于算法I,所有我们可以得出结论,某个算法,随着n的增大,它会越来越优于一种算法或越来越差于一种算法

四.算法时间复杂度

1.算法时间复杂度定义

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

完全没看懂定义

用大写的O()来体现时间复杂度的记法,我们称之为大O记法.
一般情况下,随着n的增大,T(n)增长最慢的算法为最优算法

H,J,K

由算法的时间复杂度定义可知,H,J,K算法的时间复杂度分别是O(1),O(n),O(n^{2).我们分别给它们取非官方的名称,**O(1)叫常数阶,O(n)叫线性阶,O(n}2)叫平方阶**

2.推导大O阶方法

f(n)相当于前面的求y的函数

• 1.用常数1取代运行时间内所有的加法运算

• 2.在修改后的运行次数函数中,只保留最高阶项

• 3.如果最高阶项存在且不是1,则去除与这个项相乘的常数

得到的结果就是大O阶
事实上,分析一个算法的时间负责度,没这么简单,还需要分析几个例子

3.常数阶

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

为什么这个算法的时间复杂度不是O(3),而是O(1)那?????
算法的运行次数函数f(n) = 3.根据我们推导大O阶的方法,第一步就是把常数项3改为1,在保留最高阶项时发现,它没有最高阶项,所有算法的时间复杂度为O(1).
如果sum = (1+ n) * n /2 有10句

  int sum = 0, n = 100; //执行1次
  sum = (1+ n) *n/2;//执行1次
  sum = (1+ n) * n/ 2;//执行2次
  sum  = (1+ n) * n/ 2;//执行3次
  ......
  sum = (1+ n)*n/ 2;//执行10次
  print("%d",sum);//执行1次

事实上,无论n为多少..上面两段代码就是3次和12次执行的差异,这种鱼问题的大小无关(n的多少),执行时间恒定的算法.我们称为具有O(1)的时间复杂度,又叫常数阶
** 注意:不管这个常数是多少,我们都记做O(1),而不是O(2),O(3)等其他任何数字.**
对于任何分支结构而言,无论是真,还是假,执行的次数都是恒定的,不会随着n的变大而发生变化,所有单纯的分支结构(不包含在循环结构中),其时间复杂度也是O(1).
4.线性阶
分析算法的复杂度,关键是要分析循环结构的运行情况
下面这段代码,它的循环复杂度为O(n),因为在循环体中的代码要执行n次

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

5.对数阶

  int count = 1;
  while(count < n){
  count = count * 2;
  }

有多少个2相乘后大于n,则会退出循环.由2^x = n 得到x = log2N,所有这个循环的时间复杂度为O(logn)
6.平方阶

  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 = 2时,内循环执行n - 2次
......
当 i =