算法Lecture1宣讲培训.ppt

渐进符号 Example: f(n) = 8n + 128 c=1, n0=16, f(n)=c*n2 c=2, n0=10.2, f(n)=c*n2 c=4, n0=6.7, f(n)=c*n2 f(n) = O(n2) 渐进符号 渐进符号 C0=O(1): f(n) 等于非零常数的情形。 3n+2=O(n): 可取c＝4，n0＝2。 100n+6=O(n): 可取 c=101，n0＝6。 2n2+11n-10=O(n2): 可取 c=3, n0 =10 6×2n+n2=O(n2): 可取c =7，n0=4. 3×log n + 2×n + n2 =O(n2). n×log n +n2=O(n2). 3n+2=O(n2). 算法分析 本部分的重点在于讲述如何对算法进行分析。分析算法的目的既在于从解决同一问题的不同算法中选出较为适用的，也在于对现有的算法进行改进，对后面将要介绍的算法设计来说，也是很重要的。 分析算法的一些原则 分析一个算法的优劣，主要考虑以下几个方面的问题： 正确性 也即要求该算法在合理的输入数据下，能在有限的时间中得出正确的结果。分析算法的正确性，一般需要用到有关的数学定理（例如线性代数、图论、组合数学等方面的定理）。对于长的程序，可以将其分成一些小段来分析，只有每个小段都是正确的，才能保证整个程序的正确性。在分析算法的正确性时，数学归纳法是很有用的。 运算工作量 此处并非指的是计算机真正的运算时间，因为这因计算机而异，也不是指需要执行的指令和语句数目，因为这与所用的程序语言和程序员的习惯有关。此处是分析算法本身的特点，我们希望有一个足够准确又足够一般的衡量方法，通常是计算所需的一些基本运算的次数。例如所需的比较次数，所需的加法和乘法次数等。而且通常是对不同的算法进行相对的比较。在分析比较算法时，运算量是一个非常重要的因素。 所占空间量 这也不是具体指真正占多少计算机的内存或外存，因为这同样与所采用的计算机所用的程序语言和程序员惯用的格式有关。此处也是进行相对的比较。如果输入数据有其固有的形式，则我们分析还需要占多少额外的单元。当所需额外存储单元数不随输入数据的规模变化时，我们称这种算法是“就地”进行运算的（例如排序算法中的堆阵排序），对于大型的问题这当然比所需额外单元与输入数据规模大小有关的算法（如合并排序）要优越。应说明，这里所说“存储单元”，并无严格的定义，是因问题而异的。如果输入数据可以表示成不同的形式，例如图就有不同的表示方法，则还需要比较输入数据的不同形式占空间的多少。 简单性 最简单最直接的方法往往不是最有效的方法，例如递归算法虽然简单，但运算工作量较大。但算法的简单性使得证明其正确性比较容易，编写程序、改错和修改程序都比较方便，可以节省人的时间，还是应当强调的。即使如此，对于经常使用的程序来说，算法的效率还是比其简单性更重要。 算法的复杂性 算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上面，所需的资源越多，我们就说该算法的复杂性越高；反之，所需的资源越低，则该算法的复杂性越低。 算法的复杂性 算法的各个复杂性可以用一个变量表示，这个变量就是问题实例的“规模”，用它反映描述该实例所需要输入的数据总量。这样做是方便的，因为预料问题实例的相对难度随着它们的规模而变化。 我们用n作为表示问题规模的量，例如排序问题中n为需要排序的元素的个数；图的问题中n为图的顶点数或边数；矩阵求逆中n为矩阵的阶数等。 不同时间复杂性函数的对比 可以看出，不同T(n)的算法当n增长时运算时间增长的快慢很不同。T(n)为指数形式的算法当n较大时实际上是无法应用的。有些算法T(n)与n！成正比，它随n的加大比指数函数增长还要快，这种算法更是没有实用价值。凡是T(n)为n的对数函数、线性函数或多项式的(幂函数也是多项式的特例)，我们称这类算法为“有效算法”，或好的算法；反之，凡是T(n)为指数函数或阶乘函数的，称之为坏的算法。 提高计算速度对不同时间复杂性函数的影响对比 n T(nm) T(n) T(nm) T(n) T(n) 不同性能计算机求解问题规模的比较 t n1 n2 n1 n2 T(n1)=kT(n2) Example K = 64, T(n)= 3*2n 3*2n1 = 64*3*2n2 n1= 6 n2 算法的复杂性 关于算法的复杂性，有两个问题要弄清楚： 1 用怎样的一个量来表达一个算法的复杂性； 2 对于给定的