下载文档原格式
算法分析与评估1.概述在查找引擎优化范畴里边有一个疑问常常让人感受捉摸不透，到底是什么样的排序要素结尾决定了网页的排名。
而每个查找引擎公司都将其的查找引擎算法维护的极端严密，只有很少很少的一些的公司能有时机看到这些算法的全貌。
并且就算是有时机看到这些算法的真实容貌，要想领悟到话，还得具有深沉的数学功底。
这使得对查找引擎优化整个概念的晓得变得很艰难。
同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。
一个算法得出一个解，那么这个解是最优解还是可行解？如果是可行解，与最优解的偏差有多大？对于算法的效果，存在两种评价方法——证明方法和仿真分析方法。
证明方法是指利用数学方法对于算法进行评估，证明它的解的类型。
仿真分析方法是指产生或选取大量的、具有代表性的问题实例，利用该算法对这些问题实例进行求解，并对算法产生的结果进行统计分析。
例如对于TSP问题贪心算法的模拟与分析，关于贪心算法的正确性，直观上只需检查算法的输出结果中，每个城市出现且只出现一次，该结果即是TSP问题的可行解，说明算法正确的求解了这些问题。
关于它的效果，如果实例的最优解一直（问题规模小或问题已被成功求解），利用统计方法对若干问题实例的算法结果与最优解进行对比分析，即可对其进行效果评价。
而对于较大规模的问题实例，其最优解往往是未知的，因此，算法的效果评价只能借助于与前人算法的结果的比较。
2.复杂度评价一个算法时另一个问题是，算法能够执行的了吗？有限的时间和空间上这个算法能够执行吗？这就需要对算法的复杂性进行分析。
算法的时间复杂度和空间复杂度合称为算法的复杂度。
2.1.时间复杂度（1）时间频度一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。
但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。
并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。
算法的复杂性算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。
⼀个算法的复杂性的⾼低体现在运⾏该算法所需要的计算机资源的多少上⾯，所需的资源越多，我们就说该算法的复杂性越⾼；反之，所需的资源越低，则该算法的复杂性越低。
计算机的资源，最重要的是时间和空间（即存储器）资源。
因⽽，算法的复杂性有时间复杂性和空间复杂性之分。
不⾔⽽喻，对于任意给定的问题，设计出复杂性尽可能低的算法是我们在设计算法时追求的⼀个重要⽬标；另⼀⽅⾯，当给定的问题已有多种算法时，选择其中复杂性最低者，是我们在选⽤算法适应遵循的⼀个重要准则。
因此，算法的复杂性分析对算法的设计或选⽤有着重要的指导意义和实⽤价值。
1.时间复杂性：如果⼀个问题的规模是n，解这⼀问题的某⼀算法所需要的时间为T(n)，它是n的某⼀函数 T(n)称为这⼀算法的“时间复杂性”例1：设⼀程序段如下for (int i = 0; i < n; i++) // (i = 0) 1次 (i < n) n次 (i++) n次{for (int j = 0; j < n; j++) // (j = 0) n次 (j < n) n*n次 (j++) n*n次{x++; //(i++) n*n次}}可见，这段程序总的执⾏次数是：T(n)=1+3n+3n*n。
因为时间复杂度是不考虑系数的所以 T(n)=O(n^2)2.空间复杂性:包括程序代码所占⽤的空间，输⼊数据所占⽤的空间和辅助变量所占⽤的空间这三个⽅⾯。
⼀个算法的空间复杂度只考虑在运⾏过程中为局部变量分配的存储空间的⼤⼩只要不超过内存，尽可能⽤空间换时间。
算法的计算复杂性概念
计算复杂性是一个相当普遍的概念，用来衡量算法的复杂程度及其所需要的计算和存储资源。
它指出了通过解决一个特定问题所需要的资源数量和时间，是计算机科学领域中应用非常广泛的计算时间和空间复杂度理论。
计算复杂性的基本思想是：给定的算法的运行时间，由其所执行的基本步骤的重复次数决定。
这些步骤机会包括读写输出、内存操作、比较和逻辑判断等。
每一次的重复，都会消耗算法所需的资源。
算法的运行时间，在某程度上可以用消耗的资源数量来衡量。
计算复杂性概念被用来衡量算法空间和时间复杂度，以及评价算法效率，它是一种定量量度。
运行时间和空间复杂度由大O表示法来表示，Big O表示法在数学里描述函数增加量的时候，使用主要步骤多少来表示算法的复杂程度。
算法中最耗时的基本步骤是核心步，而计算复杂性可以衡量算法的效率，并评估算法的运行性能。
计算复杂性的概念历经多年，今天已经成为计算机科学领域的核心技术，深受计算性能分析专家、软件开发者和算法设计者的重视。
它不仅能够帮助识别算法效率的关键瓶颈，而且能够用精准的度量标准来比较两个算法的性能，帮助推进算法的改进，提高计算性能。
因此计算复杂性是一个极为重要的计算机科学概念，它能够用精确的方式衡量算法的复杂程度，用于评估算法的性能，以及帮助算法设计者和开发者识别算法缺陷并进行改进。
第一章算法概述1、算法的五个性质：有穷性、确定性、能行性、输入、输出。
2、算法的复杂性取决于：(1)求解问题的规模(N) , (2)具体的输入数据(I),( 3)算法本身的设计(A)，C=F(N,I,A。
3、算法的时间复杂度的上界，下界，同阶，低阶的表示。
4、常用算法的设计技术：分治法、动态规划法、贪心法、回溯法和分支界限法。
5、常用的几种数据结构：线性表、树、图。
第二章递归与分治1、递归算法的思想：将对较大规模的对象的操作归结为对较小规模的对象实施同样的操作。
递归的时间复杂性可归结为递归方程：1 11= 1T(n) <aT(n—b) + D(n) n> 1其中，a是子问题的个数，b是递减的步长，~表示递减方式，D(n)是合成子问题的开销。
递归元的递减方式~有两种：1、减法，即n -b，的形式。
2、除法，即n / b，的形式。
2、D(n)为常数c：这时，T(n) = 0(n P)。
D(n)为线形函数cn：r O(n) 当a. < b(NT(n) = < Ofnlog^n) "n = blljI O(I1P)二"A bl吋其中.p = log b a oD(n)为幕函数n x：r O(n x) 当a< D(b)II JT{ii) = O(ni1og b n) 'ia = D(b)ll].O(nr)D(b)lHJI：中，p= log b ao考虑下列递归方程：T(1) = 1⑴ T( n) = 4T(n/2) +n⑵ T(n) = 4T(n/2)+n2⑶ T(n) = 4T(n/2)+n3解：方程中均为a = 4，b = 2，其齐次解为n2。
对⑴，T a > b (D(n) = n) /• T(n) = 0(n);对⑵，•/ a = b2 (D(n) = n2) T(n) = O(n2iog n);对⑶，•/ a < b3(D(n) = n3) - T(n) = 0(n3)；证明一个算法的正确性需要证明两点：1、算法的部分正确性。
第1.1章算法复杂性问题-----NP完全问题§1 NP问题与NP完全问题在第一章中我们初步讨论了算法复杂性的概念。
从第三章到第七章，我们讨论了不少问题和它们的算法。
这些问题基本上都是P问题，即它们都有多项式算法。
但在第一章中我们就已经指出，有不少问题至今没有找到多项式算法。
一个问题很自然地摆到我们面前：一个组合最优化问题，如果没有找到它的多项式算法，原因究竟是什么？是因为它本质上就不存在多项式算法呢？还是由于我们研究得不透彻或者我们的能力不够？后一种可能性是可能存在的。
线性规划问题，从三十年代开始提出，一直延续到七十年代，几十年没有找到一个多项式算法，已经有不少人认为线性规划可能没有多项式算法。
但在1979年，年轻的苏联数学工作者XиЧиЯН找到了第一个解线性规划的多项式算法——椭球算法，以后又出现了Karmaka算法。
在科学史上，经过几百年甚至上千年才被攻克的难题不胜枚举。
因此，如果能够根据问题的难度对问题进行分类，将会给算法研究带来巨大的好处。
首先，我们知道我们研究的问题难度很大，不可能找到或者很难找到有效算法，我们将会把精力集中于寻找问题的近似算法，避免了可能无效的研究。
第二，如果我们知道两个问题有相同的难度，那末它们之间必然存在某种内在联系，解决第一问题的方法经过适当的修改很可能就能解决第二个问题，这就对我们寻找一个解决第二个问题的方法带来帮助。
但是，对问题进行分类和判定一个问题属于哪一类，这两件工作都十分困难。
两个看上去很相似的问题，例如第一章中介绍的中国邮递员问题和旅行售货员问题。
但前者提出不久就被判定为P问题，而对后者研究了四十多年却没有结果。
在第一章中我们提到“理想计算机”模式。
目前绝大多数算法理论讨论都在一种“图灵机”的理想数学模型上进行，“图灵机”是为纪念英国科学家图灵而得名，因为他最早提出了这个模型。
图灵机是对目前使用的实际计算机的一个很好的简化和抽象。
凡是用图灵机描述的用多项式时间运行的算法，都可以在实际计算机上用多项式时间运行；反过来，实际计算机上的多项式算法，也都可在图灵机上被描述并按多项式时间运行。
计算机算法的设计与复杂度分析计算机算法的设计与复杂度分析是计算机科学领域的重要研究方向。
算法设计是指根据特定的问题需求和约束条件，提出一种计算机程序的设计方法，以解决该问题并达到预期的效果。
复杂度分析是评估算法的效率和性能的过程，它衡量了算法解决问题所需的计算资源和时间。
本文将介绍计算机算法设计的基本原则和常见的复杂度分析方法。
一、算法设计的基本原则在进行计算机算法设计时，我们应该遵循以下基本原则来确保算法的正确性和高效性。
1. 明确问题需求：在开始设计算法之前，我们应该清晰地理解问题的需求和约束条件。
只有通过准确地定义问题，才能设计出相应的算法。
2. 模块化设计：将算法分解为多个独立的模块，每个模块负责一个特定的任务。
这样可以简化算法的设计和实现过程，并提高代码的可读性和可维护性。
3. 选择适当的数据结构：合适的数据结构能够更有效地处理算法涉及到的数据。
我们应该根据问题的特点选择最适合的数据结构，如数组、链表、栈、队列、树等。
4. 使用适当的算法策略：针对不同的问题，我们应该选择适当的算法策略来解决。
例如，对于查找问题，可以选择二分查找、哈希表等算法策略。
5. 考虑算法的时间复杂度和空间复杂度：在算法设计过程中，我们应该对算法的效率进行评估和预估，考虑算法的时间复杂度和空间复杂度，以便在实际应用中能够满足性能要求。
二、常见的复杂度分析方法计算算法的复杂度是评估其运行效率的重要指标。
常见的复杂度分析方法包括时间复杂度和空间复杂度。
1. 时间复杂度：时间复杂度衡量算法解决问题所需的时间资源。
常见的时间复杂度有O(1)、O(n)、O(nlogn)、O(n^2)等。
其中，O(1)表示算法的执行时间是一个常数，与问题的规模无关；O(n)表示算法的执行时间与问题的规模成线性关系；O(nlogn)表示算法的执行时间与问题的规模以及问题分解的规模成对数关系；O(n^2)表示算法的执行时间与问题的规模成平方关系。
