算法相关概述(算法,程序,复杂度分析,基本结构,表示方法,NP完全性理论,最优化问题,判定问题,P类问题,NP类问题)_复杂问题由基础问题构成

算法(Algorithm)的定义

 算法是指解决问题的一种方法或一个过程。

 算法是对特定问题求解步骤的一种描述，是若干指令的有穷序列。

算法(Algorithm)的性质

1. 输入：有外部提供的量作为算法的输入
2. 输出：算法产生至少一个量作为输出
3. 确定性：组成算法的每条指令是清晰、无歧义的。相同的输入只能有唯一的输出结果;算法在一定条件下，只有一条执行路径;
4. 有限性：算法中每条指令的执行次数是有限的，每条指令的执行时间也是有限的

程序(Program)

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

 程序可以不满足算法的性质：有限性。

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

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

算法复杂性分析

 算法复杂性分析分为时间复杂性分析和空间复杂性分析

  算法的时间复杂性T(N, I)表示所需的时间资源的量，其中N是问题的规模， I 是算法的输入。

  算法的空间复杂性S(N, I)表示所需的空间资源的量

 主要讨论时间复杂性, 空间复杂性分析相对比较简单, 计量方法相似。

算法的时间复杂性

 根据T(N, I)的概念， T(N, I)是算法在计算机上执行所需要的时间。

 T(N, I)： 基本元运算的计算时间

 定义计算机元运算：$O_1$，$O_2$， … , $O_k$，执行一次运算所需要的时间为$t_1$, $t_2$, …, $t_k$。对于给定一算法A，用到元运算$O_i$的次数为$e_i$，对于每一个i，1 ≤ i ≤ k， $e_i$是N和I的函数， $e_i$= $e_i$(N, I)，定义:

算法的空间复杂度

 一个程序的空间复杂度是指运行完一个程序所需内存的大小。利用程序的空间复杂度，可以对程序的运行所需要的内存多少有个预先估计。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。程序执行时所需存储空间包括以下两部分。

1. 固定部分。这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间。这部分属于静态空间。
2. 可变空间，这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等。这部分的空间大小与算法有关。一个算法所需的存储空间用f(n)表示。S(n)=O(f(n)) 其中n为问题的规模，S(n)表示空间复杂度。

算法渐近复杂性

概念介绍

 先举个栗子:

  T(N)      3N²+4NlogN+7

  T’(N)      N²

  T'(N)是T(N)当N -> ∞时的渐进表达式，或渐近性态；
  T'(N)是算法当N -> ∞的渐近复杂性。

---

 函数T(N)的阶： 随着规模N的增大， T(N)增长速度的快慢

   举个栗子：T(N)=4NlogN+7    T’(N)=N²，

   随着规模N的增大， T‘(N)的增长速度比T(N)的增长速度快， 此时，T’(N)的阶高于T(N)，或相对于T(N)， T’(N)=是高阶项

---

 渐进复杂性：对于T(N)，如果存在函数T’(N)，使得当N→∞使有如下公式成立，则T’(N)是T(N)当N→∞时的渐进复杂性。

 在数学上，T‘(N)是T(N)当N→ ∞时的渐进表达式，是T(n)略去低阶项留下的主项，比T(n) 简单。

分析算法复杂性：只要得到不同T'(N)的阶即可。

渐近上界记号 O

 O(g(N)) = { f(N) | 存在正常数C和N0，使得对所有N ≥ N0有：0 ≤ f(N) ≤ Cg(N) } , 记为 f(N) ＝O(g(N)) ，则称f(N)的阶不高于g(N)的阶 as N -> ∞。

 渐进上界符号O(g(N)) ：保存了所有以g(N)为上界的正函数的集合，或者不高于g(N）的阶的正函数组成的集合。该上界的阶越低越好。

实际上：f(N) ＝O(g(N)) 表示f(N) ∈ O(g(N))

例子

 当N ≥ 1时，有N+1024 ≤ 1025N, 所以有N+1024=O(N)

 当N ≥ 10时，有2N² +11N-10 ≤ 3N², 所以2N² +11N-10=O(N²)

 当N ≥ 1时，有N² ≤ N³ ，所以有N² = O(N³ )

运算规则

1. O(f)+O(g)=O(max(f,g))；
2. O(f)+O(g)=O(f+g)；
3. O(f)O(g)=O(fg)；
4. 如果g(N)=O(f(N))，则O(f)+O(g)=O(f)；
5. O(Cf(N))=O(f(N))，其中C是一个正的常数；
6. f=O(f)。

渐近下界记号 Ω

 Ω (g(N)) = { f(N) | 存在正常数c和n0使得对所有N ≥ N0有：0 ≤ cg(N) ≤ f(N) }, 记为 f(N) =Ω(g(N)) ，或说f(N)的阶不低于g(N)的阶1 as N -> ∞。

 渐进下界符号Ω(g(N)) ：保存了以g(N）为下界的正函数的集合。该渐进下界的阶越高，则评估就越准确，结果就越有价值。

f(N) ＝ Ω (g(N)) 表示f(N) ∈ Ω(g(N))

紧渐近界记号θ

 f(N)=θ(g(N))当且仅当f(N)=O(g(N))且f(N)=Ω(g(N))。此时称f(N)与g(N)同阶

：f(N) ＝ θ(g(N)) 表示f(N) ∈ θ(g(N))

非紧上界记号 o

 o(g(N)) = {f(N) | 对于任何正常数$\epsilon$>0，存在正数n0 >0使得对所有n ≥ $n_0$有：0 ≤ f(N)/ g(N) < $\epsilon$}, 记为 f(N) ＝o (g(N)) ，则称f(N)的阶比g(N)低 as n -> ∞ 。

f(N) ＝o (g(N)) 实际上表示f(N)  o (g(N))

 例：4NlogN+7=o(3N2+4NlogN+7)。

算法基本结构

算法表示方法

• 用自然语言表示
• 用流程图表示
• 用伪代码表示：伪代码是一种描述语言。.它只是一种描述程序执行过程的工具，是面向读者的，不能直接用于计算机。伪代码使用一种介于自然语言和计算机语言之间的文字和符号来描述算法的方法。
• 用计算机语言表示

NP完全性理论

• 从计算的观点来看，如何判断一个问题是“易”计算的，还是“难”计算的？
• 如果一个问题的计算时间下界，就可以评价已对该问题提出的各种算法的效率，就可以确定已有算法有多少改进的余地。
• 然而，要确定一个问题的计算复杂性很难。如何区分一个问题是“易” 还是“难”？
• 一般地，可由多项式时间算法求解的问题看作是易解问题，而需要超多项式时间算法才能求解的问题看作是难解问题（如：复杂度函数为指数函数，阶乘函数等）。
• 另外一种判定难，易方法(两类问题：最优化问题与判定问题)

最优化问题与判定问题

 最优化问题

  1. 寻找一个有最优目标函数值的可行解

  2. 许多最优化问题是难解问题

  判定问题

  1. 输出仅为“是”或“否”的一类问题

  2 可抽象为所有输入到{yes, no}的映射

---

 优化问题例子(旅行售货员问题)

  某售货员到若干城市去推销商品，已知各城市之间的路程(或旅费)。他要选定一条路线，经过每个城市一遍最后回到驻地的路线，使得总的路程(或总旅费)最小。

  判定问题例子(旅行售货员问题)

  某售货员到若干城市去推销商品，已知各城市之间的路程(或旅费)。他要经过每个城市一遍后回到驻地，要求判定图G中是否存在总费用不超过d的周游路线。

判定问题比最优化问题容易求解

• 最优化问题可简化为判定问题
• 以简单的判定问题为研究对象
• 若判定问题是难解问题，则更为复杂的优化问题也定是难解问题
• 可通过分析判定问题的难易，来判断优化问题的难易
  
  

P类问题（Polynomial）

 Polynomial：多项的，多词的；多项式的  /,pɑlɪ’nomɪəl/    (先来学个单词