1.2算法和算法评价-你,与世界的距离

算法与数据结构的关系:在数据结构中,将遇到大量的算法问题,算法联系着研究数据结构的重要途径。

算法的评价就是算达到这个条件需要运行多少次,是一个大概的量级,当然指数最牛逼。

做题,学习知识,似乎人人都能说一套很有道理的方法,似乎也是有效的,但是当自己实际去做的时候发现到处都是拦路虎。

1.2.1 算法的基本概念

算法(Algorithm)对特定问题求解步骤的描述,它是指令的有限序列,其中每个指令表示一个或者多个操作,算法具有五大特性

  • 有穷性。一个算法总是要执行有穷步后结束,且每一步都可以做有穷时间里完成。
  • 确定性。算法中的每条指令必须有确切的含义,对于相同的输入只能得到相同的输出。
  • 可行性。算法中的描述都是可以通过已经实现基本运算执行有限次来实现。
  • 输入 。一个算法有零个或者多个输入,这些输入取自某个特定的对象的集合。
  • 输出,一个算法有一个或者多个输出,这些输出是与输入有着某种特定关系的量,通常一个好的算法应该考虑达到以下目标:
  1. 正确性,算法能够正确的解决问题
  2. 可读性,算法要具有良好的可读性,帮助人们理解
  3. 健壮性,输入非法数据时,算法能适当的作出反应或者进行处理,而不是莫名其妙的输出结果
  4. 效率与低存储需求,效率是指算法执行的时间,存储量需求是指算法执行过程中需要的最大存储空间,这两者都和问题规模有关。

算法效率的度量

算法效率的度量是通过时间和空间复杂度来描述的。

  • 时间复杂度

一个语句的频度是指该语句在算法之中被重复执行的次数,算法中所有频度支和记为T(n),它是该算法规模n的函数,时间复杂度只要衡量T(n)的数量级,算次内的最深层循环内的语句)的频度与T(n)的数量级,因此通过采用算法中基本的运算频度f(n)来分析算法的时间复杂度,算法的时间复杂度记为T(n)=Of(n)

式子中O的含义是T(n)的数量级,严格的数学定义是:若T(n)和f(n)是定义在正证书集合上的两个函数,则存在正常数C和no,使得当m≥m0时,都满足0≤T(n)≤c=Cf(n)

算法的时间复杂度不仅和问题规模n有关,而且与与输入实例中A的各元素取值以及和k的取值有关

例如在数组A[0....n-1]中,查到给定值k的算法大致如下:

1 = n - 1;
while(i>=0&&(A[i]!=k)) 
i--;
return i;

 

语句三(基本运算)不仅与问题规模n有关,而且与输入实例中A的各元素不到取值及k的取值相关

  1. 若A中没有与k相等的元素,则语句三的频度f(n)= n
  2. 若A的最后一个元素等于k,则语句三的频度f(n)= n

最坏的时间复杂度是在考虑最坏的情况下,算法的时间复杂度

平均时间复杂度是指所有可能输入实例在等概率出现的情况下,算法的期望运行时间

最好的时间复杂度是最好的情况下,算法时间复杂度

一般是考虑最坏的复杂度,保证算法的运行时间不会比他更长

在分析一个程序的时间复杂度时,有两条规则:

1.2算法和算法评价-你,与世界的距离

空间复杂度

空间复杂度S(n)定义该算法所耗费的存储空间,它是问题规模n的函数,记为

S(n)=O(g(n))

一个程序除了自身需要存储空间存放本身所用的常量,变量,输入数据外,还需要对一些数据进行操作的工作单元和存储一些为实现计算所需要信息的辅助空间,若输入数据所占空间只取决于问题本身,和算法无关,则只需要分析除输入和程序之外的额外空间。

算法原地工作是指算法所需的辅助空间为常量,即O(1)

具有相同结构的运算体,它们的时间复杂度相同,随着后面内容的学习,会深化本节内容

和课本相比,王道的书中省略了很多例子,他的例子就是题目,根据题目来深化学习的内容。

时间复杂度计算是重点,到哪这这是一个衡量指标,随着学习的数据结构越来越多,越来越熟悉这套分析方法,后期我会回来的。