算法

1.定义:是对特定问题求解步骤的一种描述,是指令的有限序列。

2.特征:

输入:算法有零个或多个输入量;

输出:算法至少产生一个输出量;

确定性:算法的每一条指令都有确切的定义,没有二义性;

能行性:算法的每一条指令必须足够基本,他们可以通过已经实现的基本运算执行有限次来实现。

有穷性:算法必须总能在执行有限步之后终止。

程序:程序是算法用某种程序语言的具体实现

程序可以不满足算法的5条性质。

操作系统,是一个在无限循环中执行的程序,因而不是一个算法。

操作系统的各种任务可看成是单独的问题,每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。

算法的性能:算法所需的计算时间和占用的内存空间

问题和问题求解

常见的应用问题类型:

1.搜索问题;2.排序问题;3.图论问题;4.组合数学问题;5.几何问题;6.数值计算问题;

P问题

  • P问题能够保证存在多项式时间求解算法;
  • NP问题不确定是否存在多项式时间求解算法,但确定存在多项式时间验证算法;
  • P问题是NP问题的子集,因为存在多项式时间求解算法的问题,一定能够在多项式时间内被验证;
  • NP-hard问题不一定是NP问题,有可能是不可判定问题。这时候说明原问题也是不可判定的;
  • NPC问题既是NP问题的子集,又是NP-hard问题的子集,所以NPC问题是NP问题和NP-hard问题的交集;
  • NP-hard问题和NPC问题都要求能够在多项式时间内规约成另外一个问题。这里规约的意思是将一个特殊问题一般化,即将原问题推广为一个最一般的,最有概括性,也更难得,计算复杂度更高的问题,这个问题具有最高的计算复杂度,如果这个最一般的问题也能有多项式时间求解算法,那么那些特殊的原问题也能有多项式时间求解算法。