下载文档原格式
第一章：算法定义: 算法是若干指令的有穷序列, 满足性质: (1)输入: 有外部提供的量作为算法的输入。
(2)输出: 算法产生至少一个量作为输出。
1. (3)确定性：组成算法的每条指令是清晰, 无歧义的。
2. (4)有限性：算法中每条指令的执行次数是有限的, 执行每条指令的时间也是有限的。
3. 程序定义: 程序是算法用某种程序设计语言的具体实现。
可以不满足算法的性质(4)。
4. 算法复杂性分为时间复杂性和空间复杂性。
5. 可操作性最好且最有使用价值的是最坏情况下的时间复杂性。
6. O(n)定义: 存在正的常数C 和自然数N0, 当N>=N0时有f(N)<=Cg(N),则称函数f(N)当N 充分大时有上界, 记作f(N)=O(g(n)). 7. Ω(n)定义: 存在正的常数C 和自然数N0, 当N>=N0时有f(N)>=Cg(N),则称函数f(N)当N 充分大时有上界, 记作f(N)=Ω(g(n)). 8. (n)定义:当f(n)=O(g(n))且f(N)=Ω(g(n)), 记作f(N)= (g(n)), 称为同阶。
求下列函数的渐进表达式: 3n2+10n ~~~O(n2) n2/10+2n~~~O(2n) 21+1/n~~~O(1) logn 3~~~O(logn) 10log3n ~~~O(n) 从低到高渐进阶排序: 2 logn n2/3 20n 4n2 3n n!第二章：1. 分治法的设计思想: 将一个难以直接解决的问题, 分割成一些规模较小的相同问题, 以便各个击破分而治之。
2. 例1 Fibonacci 数列 代码（注意边界条件）。
int fibonacci(int n) {if (n <= 1) return 1;return fibonacci(n-1)+fibonacci(n-2);}3. Ackerman 函数双递归。
A(1,1)代入求值。
A(1,1)=A(A(0,1),0)=A(1,0)=24. 全排列的递归算法代码。
《算法设计与分析》课程的心得体会以最少的成本、最快的速度、最好的质量开发出合适各种各样应用需求的软件，必须遵循软件工程的原则，设计出高效率的程序。
一个高效的程序不仅需要编程技巧，更需要合理的数据组织和清晰高效的算法。
这正是计算机科学领域里数据结构与算法设计所研究的主要内容。
一些著名的计算机科学家认为，算法是一种创造性思维活动，并且处于计算机科学与技术学科的核心。
在计算机软件专业中算法分析与设计是一门非常重要的课程，很多人为它如痴如醉。
很多问题的解决，程序的编写都要依赖它，在软件还是面向过程的阶段，就有程序=算法+数据结构这个公式。
算法的学习对于培养一个人的逻辑思维能力是有极大帮助的，它可以培养我们养成思考分析问题，解决问题的能力。
如果一个算法有缺陷，或不适合某个问题，执行这个算法将不会解决这个问题。
不同的算法可能用不同的时间、空间或效率来完成同样的任务。
一个算法的优劣可以用空间复杂性和时间复杂度来衡量。
算法可以使用自然语言、伪代码、流程图等多种不同的方法来描述。
计算机系统中的操作系统、语言编译系统、数据库管理系统以及各种各样的计算机应用系统中的软件，都必须使用具体的算法来实现。
算法设计与分析是计算机科学与技术的一个核心问题。
因此，学习算法无疑会增强自己的竞争力，提高自己的修为，为自己增彩。
那么，什么是算法呢？算法是指解决问题的方法或过程。
算法满足四个性质，即输入、输出、确定性和有限性。
为了了解算法，这个学期马老师带我们走进了算法的世界。
马老师这学期提出不少实际的问题，以及解决问题的算法。
我在此只说比较记忆深刻的问题，即0-1背包的问题。
0-1背包问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。
问题的名称来源于如何选择最合适的物品放置于给定背包中。
首先，0-1背包问题具有最优子结构性质和子问题重叠性质，适于采用动态规划方法求解。
算法设计读后感读完算法设计这本书啊，就像是经历了一场超级刺激又烧脑的冒险。
我以前总觉得算法嘛，就是那些高深莫测的代码指令的组合，离我这小老百姓可远着呢。
但读了这本书才发现，算法就像生活里的小机灵鬼，无处不在。
比如说我们每天找东西的时候，其实就是一种很简单的搜索算法。
你像在乱糟糟的抽屉里找个小物件，你可能就会从一头开始，一个一个翻，这就是顺序搜索算法的雏形啊。
要是东西多了，聪明点的人就会先把抽屉里的东西分分类，再找的时候就快多了，这不就是一种优化的算法思维嘛。
书里讲的那些算法，像贪心算法，就特别有趣。
感觉它就像是一个贪心的小怪兽，每一步都想拿当下最好的东西。
不过可别小瞧这个贪心的家伙，在好多实际问题里，它都能给出意想不到的好答案呢。
就好比你要去旅行，要去好几个景点，贪心算法就像那个会算计的导游，每次都带你去离当前位置最近还没去过的景点，最后还真就把所有景点都逛完了，而且路程可能还挺短的。
当然啦，这个贪心的家伙有时候也会犯错，不是所有时候都能找到全局最优解，但那又怎样，它的简单直接还是很迷人的。
还有动态规划算法，这就像是一个老谋深算的军师。
它不是一下子就冲出去解决问题，而是先把问题分解成好多小问题，然后像搭积木一样，一块一块把答案拼起来。
我就想啊，这算法就跟我们过日子似的，你想一下子实现个大目标，比如突然就成为百万富翁，那太难了。
但是你可以把这个大目标分解成小目标啊，每个月存点钱，慢慢投资，这不就是动态规划在生活中的体现嘛。
这本书还让我意识到，算法设计不仅仅是为了让计算机干活，更是一种思考问题的方式。
就像我们解决生活中的矛盾，也可以用算法的思维来捋一捋。
先分析问题的本质，再想各种解决办法，评估每个办法的优劣，最后选出一个比较好的方案。
这和设计算法里的分析需求、提出算法、分析算法复杂度这些步骤，简直就是异曲同工啊。
不过呢，算法这东西也不是那么好懂的。
有时候那些公式啊，逻辑啊，就像一团乱麻，绕得我晕头转向的。
算法设计与分析总结一、算法引论算法：通常人们将算法定义为一个有穷的指令集，这些指令为解决某一特定的任务规定了一个运算序列。
什么是算法?计算机来解决的某一类问题的方法或步骤。
算法是程序的核心。
算法的两个要素：算法是由操作与控制结构两个要素组成。
（1）操作①算术运算：加、减、乘、除等。
②关系运算：大于、大于等于、小于、小于等于、等于、不等于等。
③逻辑运算：与、或、非等。
④数据传送：输入、输出、赋值等。
（2）控制结构各操作之间的执行顺序：顺序结构、选择结构、循环结构，称为算法的三种基本结构一个算法应当具有以下特性：1、输入。
一个算法必须有0个或多个输入。
它们是算法开始运算前给予算法的量。
2、输出。
一个算法应有一个或多个输出，输出量是算法计算的结果。
3、确定性。
算法的每一步都应确切地、无歧义的定义，对于每一种情况，需要执行的动作都应严格的，清晰的规定。
4、有穷性。
一个算法无论在什么情况下都应在执行有穷步后结束。
5、有效性。
算法中每一条运算都必须是足够基本的。
原则上都能够被精确的执行。
6、一个问题可以有多个解决的算法。
程序可以不满足条件4。
计算机程序是算法的实例，是算法采用编程语言的具体实现。
算法的分类：（1）数值计算算法（2）非数值计算算法算法的表示：1、自然语言2、传统流程图3、N-S流程图4、伪代码5、计算机语言计算机程序设计中有两个核心目标：1、算法必须是易于理解，编码和调试的2、设计的算法能够最有效的使用计算机的资源。
目标1是软件工程的概念 ；目标2是数据结构和算法设计的概念 ；判断一个算法的优劣，主要有以下标准：1、正确性：要求算法能够正确的执行预先规定的功能和性能要求。
2、可使用性：要求算法能够很方便的使用。
3、可读性：算法应当是可读的，这是理解、测试和修改算法的需要。
4、效率：算法的效率主要指算法执行时计算机资源的消耗，包括存储和运行时间的开销。
5、健壮性：要求在算法中对输入参数、打开文件、读文件记录、子程序调用状态进行自动检错、报错并通过与用户对话来纠错的功能，也叫作容错性或例外处理。
算法设计读后感读了算法设计相关的书籍或者资料后，那感觉就像是被带进了一个超级神秘又超级酷的世界。
我发现算法这玩意儿就像是生活中的锦囊妙计。
以前觉得那些复杂的问题解决起来毫无头绪，就像在一团乱麻里找线头。
但是算法就不一样了，它会告诉你，“从这儿开始，一步一步来，就像走迷宫有了路线图。
”比如说排序算法，就像给一群调皮捣蛋、横七竖八的小朋友排队，从高到矮或者从矮到高。
你看冒泡排序，就像是这些小朋友互相比较身高，高的慢慢往上冒，这个过程就特别有趣，感觉每个数字或者元素都有了自己的小脾气，在算法的指挥下变得规规矩矩的。
然后呢，算法的设计还很考验人的思维能力。
它有时候就像玩一场超级烧脑的游戏，你得提前想好每一步的走法，不能乱了阵脚。
你要是不小心设计错了一小步，那就可能像多米诺骨牌一样，整个程序都乱套了。
这就好比你要做一个超级复杂的蛋糕，材料的顺序、烤制的时间、搅拌的力度都得恰到好处，算法里每个环节也都得严丝合缝。
再说到算法的优化，这就像是给一辆已经跑得很快的汽车再进行改装，让它变得超级无敌快。
你以为你的算法已经很棒了，但是当你看到那些优化后的算法，就会惊掉下巴。
就像本来你觉得自己的小自行车已经能带你去很多地方了，突然看到人家的火箭自行车（虽然现实中可能没有，但就这感觉），一下子就把你甩出好几条街。
优化算法的过程就像是不断给这个数字世界的小机器人升级装备，让它变得更加聪明、更加高效。
算法设计也不是那么容易亲近的。
有时候那些复杂的概念和公式就像外星语言一样，让人看得晕头转向。
我就经常对着那些算法的代码和解释发呆，感觉自己像是走进了一个迷宫，到处都是弯弯曲曲的路，不知道哪条才能通向出口。
但是一旦你克服了这些困难，弄明白了其中的原理，那种成就感就像是爬上了一座超级难爬的山，站在山顶俯瞰一切的感觉。
算法设计这个领域就像是一个充满无限可能的魔法世界。
它既有着严谨的逻辑和规则，又有着无限的创新和优化空间。
不管是对我们处理日常生活中的问题，还是在计算机科学这个大舞台上，算法都像是一个幕后英雄，默默地发挥着巨大的作用。
算法设计与分析心得在当今数字化的时代，算法无处不在，从我们日常使用的手机应用到复杂的科学研究，从金融交易到交通管理，算法都在发挥着至关重要的作用。
作为一名对算法设计与分析充满兴趣和探索欲望的学习者，我在这个领域中经历了一段充满挑战与收获的旅程。
算法，简单来说，就是解决特定问题的一系列清晰、准确的步骤。
它就像是一本精心编写的指南，告诉计算机在面对各种情况时应该如何做出决策和处理数据。
而算法设计与分析，则是研究如何创造出高效、正确的算法，并评估它们在不同场景下的性能。
在学习算法设计的过程中，我深刻认识到了问题的定义和理解是至关重要的第一步。
如果不能清晰地明确问题的要求和约束条件，那么后续的设计工作就很容易偏离方向。
例如，在解决一个排序问题时，我们需要明确是对整数进行排序还是对字符串进行排序，是要求稳定排序还是非稳定排序，以及数据规模的大小等。
只有对这些细节有了准确的把握，我们才能选择合适的算法策略。
选择合适的算法策略是算法设计的核心。
这就像是在众多工具中挑选出最适合完成特定任务的那一个。
常见的算法策略包括分治法、动态规划、贪心算法、回溯法等。
每种策略都有其适用的场景和特点。
分治法将一个大问题分解为若干个规模较小、结构相似的子问题，然后逐个解决子问题，最后合并子问题的解得到原问题的解。
动态规划则通过保存子问题的解来避免重复计算，从而提高效率。
贪心算法在每一步都做出当前看起来最优的选择，希望最终能得到全局最优解。
回溯法则通过不断尝试和回退来寻找问题的解。
以背包问题为例，如果我们要求在有限的背包容量内装入价值最大的物品，贪心算法可能会因为只考虑当前物品的价值而忽略了整体的最优解。
而动态规划则可以通过建立状态转移方程，计算出在不同容量下能获得的最大价值，从而得到准确的最优解。
在实现算法的过程中，代码的准确性和可读性同样重要。
清晰的代码结构和良好的注释能够让我们更容易理解和维护算法。
而且，在实际编程中，还需要考虑边界情况和异常处理，以确保算法的健壮性。
算法设计与分析期末总结一、课程概述算法设计与分析是计算机科学与技术专业核心课程之一，主要讲解算法的设计与分析方法。
通过学习该课程，我对算法设计和分析的基本概念、方法和工具有了深入的了解和掌握。
以下是我在该课程中的学习心得与总结。
二、学习内容1. 算法设计与分析的基本概念：学习了算法的定义、算法的设计、算法的复杂度等基本概念，了解了算法在计算中的重要性。
2. 分治法与递归法：学习了分治法与递归法的基本思想与原理，并运用分治法与递归法设计了一些典型的算法，如归并排序、快速排序等。
3. 动态规划：学习了动态规划的基本思想与原理，并通过实例学习了如何应用动态规划解决实际问题，如最长公共子序列问题、背包问题等。
4. 贪心算法：学习了贪心算法的基本思想与原理，并运用贪心算法解决了一些经典问题，如活动选择问题、霍夫曼编码问题等。
5. 图算法：学习了图的基本概念与遍历算法，了解了图的存储结构与遍历算法的实现，掌握了图的广度优先搜索与深度优先搜索算法。
6. NP完全问题与近似算法：学习了NP完全问题的定义与判定方法，了解了NP完全问题的困难性，学习了近似算法的设计与分析方法，并运用近似算法解决了一些实际问题。
三、学习方法1. 阅读教材与参考书籍：在课程学习过程中，我认真阅读了教材和相关参考书籍，对于课上讲解的概念和算法有了更深入的理解。
2. 完成编程作业：课程布置了一些编程作业，通过编写代码实现算法，我进一步理解了算法的具体实现细节。
3. 解题训练与思考：课程中也布置了一些习题和思考题，通过解题训练和思考，我进一步巩固了算法设计与分析的基本概念和方法。
四、学习收获1. 对算法设计与分析的基本概念与方法有了深入了解和掌握。
2. 对算法的复杂度分析方法和技巧有了更清晰的认识。
3. 加强了问题抽象和建模的能力，能够将实际问题转化为算法设计与分析的问题。
4. 提高了编程能力和算法实现的技巧，能够编写高效、优雅的代码。
5. 培养了思考和解决问题的能力，对于复杂的问题能够进行分析、拆解和解决。
这本书是《算法设计与分析》王红梅编著一共有以下12章，我们学了1、3、4、5、6、7、8、9分别是“绪论、蛮力法、分治法、减治法、动态规划法、贪心法、回溯法、分治限界法第1章绪论考点：1、算法的5个重要特性。
（P3）答：输入、输出、有穷性、确定性、可行性2、描述算法的四种方法分别是什么，有什么优缺点。
（P4）答：1. 自然语言优点：容易理解；缺点：容易出现二义性，并且算法都很冗长。
2. 流程图优点：直观易懂；缺点：严密性不如程序语言，灵活性不如自然语言。
3. 程序设计语言优点：用程序语言描述的算法能由计算机直接执行；缺点：抽象性差，是算法设计者拘泥于描述算法的具体细节，忽略了“好”算法和正确逻辑的重要性，此外，还要求算法设计者掌握程序设计语言及其编程技巧。
伪代码优点：表达能力强，抽象性强，容易理解3、了解非递归算法的时间复杂性分析。
(P13)要点：对非递归算法时间复杂性的分析，关键是建立一个代表算法运行时间的求和表达式，然后用渐进符号表示这个求和表达式。
非递归算法分析的一般步骤是：（1）决定用哪个（或哪些）参数作为算法问题规模的度量。
（2）找出算法的基本语句。
（3）检查基本语句的执行次数是否只依赖问题规模。
（4）建立基本语句执行次数的求和表达式。
（5）用渐进符号表示这个求和表达式。
[例1.4]：求数组最小值算法int ArrayMin(int a[ ], int n){min=a[0];for (i=1; i<n; i++)if (a[i]<min) min=a[i];return min;}问题规模：n基本语句：a[i]<minT(n)= n-1=O(n)4、掌握扩展递归技术和通用分治递推式的使用。
（P15）扩展递归技术：通用分支递归式：5、习题1-4，习题1-7设计算法求数组中相差最小的两个元素（称为最接近数）的差。
要求给出伪代码描述，并用一组例子进行跟踪验证，写出验证过程。
算法设计与分析知识点算法是计算机科学的核心内容之一，它涉及到问题的描述、解决思路的设计以及解决方案的验证与分析等方面。
在学习算法设计与分析的过程中，掌握一些基本的知识点是非常重要的。
本文将介绍一些算法设计与分析中常见的知识点，供读者参考。
一、算法的定义与特性算法是指解决问题的一系列步骤或操作。
算法具有以下几个主要特性：输入、输出、有穷性、确定性和可行性。
其中，输入指算法的初始数据；输出指算法得到的结果；有穷性指算法在执行有限步骤后结束；确定性指算法的每一步骤都有确定的含义；可行性指算法是能够实际操作的。
二、算法效率分析在算法设计与分析中，我们通常需要评估算法的效率。
常用的评估标准有时间复杂度和空间复杂度。
时间复杂度用于衡量算法执行所需的时间，通常记作T(n)，其中n表示问题的规模；空间复杂度用于衡量算法执行所需的存储空间，通常记作S(n)。
三、常见的算法设计技巧1. 递归：递归是指在解决问题的过程中调用自身的方法。
递归的基本思想是将一个大问题拆分成多个规模较小的子问题，并通过递归调用解决这些子问题，最终得到原问题的解。
2. 分治法：分治法是指将一个大问题分解成若干规模较小且结构相似的子问题，然后通过递归调用求解子问题，并最终合并子问题的解得到原问题的解。
3. 动态规划：动态规划是指将一个问题拆解成多个阶段，每个阶段都需要做出一系列决策，并记录下每个阶段的最优决策。
通过迭代求解每个阶段的最优决策，最终得到原问题的解。
4. 贪心算法：贪心算法是指每一步都选择当前状态下最优的解，从而使得最终结果达到最优。
四、常见的算法分析方法1. 最坏情况分析：最坏情况分析是指对算法在最坏情况下的执行时间进行分析。
最坏情况下的时间复杂度是算法的上界，也是算法在任何输入情况下运行时间的界定。
2. 平均情况分析：平均情况分析是指考虑算法在所有可能输入情况下的执行时间的平均值。
平均情况分析通常需要对输入数据进行概率分布假设。
算法设计与分析2篇第一篇：贪心算法贪心算法是求解最优化问题的一种常用算法，其核心思想是在每一步选择中都采取当前状态下最好或最优的选择，从而希望最终得到全局最好或最优的解。
一、贪心算法的基本概念贪心算法的基本概念包括“贪心选择性质”和“最优子结构性质”。
1. 贪心选择性质：所谓的贪心选择性质是指，当使用贪心策略进行问题求解时，每一次选择所采用的策略都是局部最优的，即当前情况下最好或最优的选择。
可以通过数学归纳法证明。
2. 最优子结构性质：最优子结构性质是指，当一个问题的最优解包含其子问题的最优解时，该问题具有最优子结构性质。
这种情况下，可以使用贪心算法来求解子问题的最优解，从而推导出原问题的最优解。
二、贪心算法的优缺点1. 优点：贪心算法的实现通常比其他算法简单，计算时间较短。
对于一些求解最优化问题的情况，贪心算法可以得出较好的解。
2. 缺点：贪心算法可能会得到次优解，因为其仅仅关注当前状态下最好或最优的选择，并不能保证得到全局最好或最优的解。
对于一些复杂问题，贪心算法不能得到正确结果。
三、经典贪心算法应用1. 钞票找零问题：假设有一定面额的钞票，如1元、5元、10元和50元，现在需要找零n元，如何使用最少的钞票？解决方法：使用贪心算法，每次找零都选择当前面额最大的钞票。
此方法可以得到最少的钞票数量。
2. 区间调度问题：假设有若干区间，每个区间起始时间为S，终止时间为T，需要将尽可能多的完整区间安排在一条时间轴上。
解决方法：使用贪心算法，每次选择结束时间最早的区间，然后过滤掉与该区间相交的区间。
此方法可以得到最多的完整区间。
以上两个问题均是经典的贪心算法问题，可以通过贪心选择性质和最优子结构性质进行求解。
四、总结贪心算法是一种常用的求解最优化问题的算法，其核心思想是在每一步选择中都采取当前状态下最好或最优的选择，从而希望最终得到全局最好或最优的解。
虽然贪心算法具备一定的优点，但也存在其缺点。
在实际问题求解过程中，需要结合具体情况选择合适的算法。
<<算法引论>> ------- 一种创造性方法---读书笔记【美】Udi Mander计算1314苏帅豪201321121109Chapter 1: （引论）广义地说，算法是按部就班解决一个问题或完成某个目标的过程。
数学归纳法其原理的主要思想是命题无须从什么都没有开始证明，可以通过先证明对于一个小的基本实例集命题是正确的，然后由“若对相对较小的命题实例成立则可导出较大的命题实例成立”的方式，来证明对所有实例来说命题都是成立的。
因此它的基本思想是如何扩充一个解决方案而不是从零开始进行构造。
Chapter2: (数学归纳法) 显而易见与真知灼见水火不容。
——伯特兰·罗素每次用归纳法证明都分成两步：归纳基础和规约。
归纳基础一般都比较容易，偶尔也有不太简单的，但我们往往不太在意。
归纳法证明的核心就是规约，有多种规约方法，其中最常用的就是把命题从N规约到N—1 ，从N+1规约到N也比较常见。
强归纳法会把命题从N规约到比N小（但不一定是N-1）的一个或多个命题。
其它变形还有从2N规约到N，以及逆向归纳法，也就是命题在N时的情况是由N+1的情况推出的，而归纳基础是个已被证明的无限集。
规约的要点在于要完整保留原命题，不能在规约后的命题中加入多余的假设，除非这些假设是特别包含在归纳假设中的。
增量：很明显，增量就是和我们平时的数学归纳法一样，特殊点的就是证明起始条件；假设对于K，证明成立；用假设去证明对K+1，证明成立证明的重点就这如何利用‘K’证明‘(K+1)’当然也可以认为是利用某种性质去推广其实这个就是动态规划和贪心的基本性质，最优子结构性质以及重叠子问题性质(贪心选择性质)中的最优子结构性质；现在举个"不同"例子找多数元素(多数元素的定义：在给定有限个序列内，某元素的个数大于序列个数的1/2(比如 {1 2 3 3 3}中的3))首先我们第一会想到枚举，很简单，时间复杂度为O(n^2)；最好的情况是一遍遍历就找到了:O(n) 最坏的情况是序列中没有多数元素：O(n^2) 平均情况:O(n^2)现在让我们想下对于多数元素有什么性质，设序列元素个数为N，多数元素个数为m，接下来给出一个很直接的性质(虽说很直接但是对我来说是不容易自己想出来的)：性质1：删除序列中的两个不同的数，若存在多数元素，多数元素依然存在且不变。
现在我可以想出一个算法:集合A:序列循环：i：1->n-1if(A[i]==A[i+1]||A[i]不存在) continue;else delete A[i],A[i+1];得到集合A`很明显，集合A·中的元素一定相同但是有个问题：集合中的元素不一定就是多数元素。
原因是性质1的前提是多数元素对于序列存在，我们可能会得到一个非法解我们该怎么办，很简单，验证下最后得到的那个元素就行，时间复杂度：O(n);现在回过头看看我们的思路：找到多数元素的性质，依次"增量"递减得到可能解，验证；很明显找到性质是最关键的一步；第二个例子，贪心；双机调度问题：问题描述给定n个作业，每个作业有两道工序，分别在两台机器上处理。
一台机器一次只能处理一道工序，并且一道工序一旦开始就必须进行下去直到完成。
一个作业只有在机器1上的处理完成以后才能由机器2处理。
假设已知作业i在机器j上需要的处理时间为t[i,j]。
流水作业调度问题就是要求确定一个作业的处理顺序使得尽快完成这n个作业。
分析下：若只有一个作业(a,，b1),明显时间为a1+b1;若有两个作业(a1,b1),(a2,b2);若(a1,b1)在前，则有时间T12=a1+b1+a2+b2-min(a2,b1);若(a2,b2)在前，则有时间T21=a2+b2+a1+b1-min(b2,a1);有上可得时间为Tmin=a1+b1+a2+b2-max{min(a2,b1),min(a1，b2)};由此我们可以得到一个贪心的性质，(a1,b1)和(a2,b2)中的元素若min(a2,b1)>=min(a1，b2)则(a1,b1)放在(a2,b2)前面；反之(a2,b2)放在(a1,b1)前面；根据这个性质我们对作业进行排序即得到最优工作序列；PS：由于个人表述能力不行，所以这个例子还有一些思考量，所以请大家自己用笔在纸上写下就可以得到一样的结论。
例外这个问题有个很优美的算法 Johnson算法，基本原理与上面类似，但是把结论做得更漂亮些了，有兴趣的可以去看下证明过程；这里给出Johnson算法:对给定的任务进行如下排序：得到序列A：s1[i]>=s1[j] 且以s1不减排序序列B:s1[i]<s2[j] 且以s2不增排序最优调度即为A+B；现在再回到数学归纳法上，回想如果我们得到K结论不足以证明“K+1”该怎么办？！一个很常用的思想就是加强结论；例三：最大连续子序列和问题问题描述：给出序列A，求连续子序列和最大，我们定空序列为0；下面直接给数学归纳法的(思考)过程：设序列中元素个数为n若序列中元素个数n为1，则最大子序列和为:A[1]>0?A[1]:0;假设对于子序列"K"(前k个元素的子序列)，得到最大子序列S=“A[i]...A[j]”(1<=i<=j<=k) 那么对于子序列"K+1",若S中的j=k+1，那么S'=S+A[k+1]>=S?S+A[k+1]:S;若S中的j！=k+1，....这个，我们该怎么办呢，关于最大子序列S与A[k+1]我们找不到更多的联系；那么我们加强下论证结果，加入一个最大尾子序列和(包括当前序列尾节点的最大子序列)：S.end=“A[m]...A[k]”(1<=m<=k)明显若S.end<0时，我们可以将S.end=0;现在我们重新证明下；设序列中元素个数为n若序列中元素个数n为1，则最大子序列和为:A[1]>0?A[1]:0;最大尾子序列和为：0+A[1]>0?0+A[1]:0;假设对于子序列"K"(前k个元素的子序列)，得到最大子序列S=“A[i]...A[j]”(1<=i<=j<=k) 最大尾子序列S.end="A[m]...A[k]"(1<=m<=k)那么对于子序列"K+1",最大子序列和为S>S.end+A[k]?S:S.end+A[k];最大尾子序列和为S.end+A[k]>=0?S.end+A[k]:0;这样就可以得到我们熟悉的时间复杂度为O(n)的最大子序列和算法了。
首先给出时间复杂度的主方法;给出这个的目的是一种指引，对于设计算法的指引，通过这个你可以看到怎么样设计一个算法它的时间复杂度更低；例子四，最近点对问题问题描述：给出二维平面内若干个点的坐标，求出欧式距离最小的点对；这个问题的算法有种分治版本并且网上的证明很多，我只是想给出它的简单思想；首先对所有点进行排序，按照x递增的顺序排序；1，二分排序后的点；两边的点数目大致相等(这只是奇偶数问题)2，对两边点进行递归求解子最小点对距离len1，len2，直至点的数目<=3直接进行求解；3，合并；对于合并，如果我们枚举的话，根据上面的主方法得到时间复杂度为O(n^2)，这样还增加了问题的复杂性；我们可以看到只有在划分线周围的点才可能比两边找到的子最近点对距离，所以我们找到划分线两边距离d为min{len1，len2}的所有点；若此时仍然枚举，时间复杂度还是为O(n^2);接下来我就直接给出问题的正解，因为网上这类资料博客还是比较多的。
对于上一步得到的点，按照y不减排序，得到新的点序列，枚举每个点和每个点后6个的最小距离，更新最点点对距离；根据主方法我们得到时间复杂度为O(nlogn)Chapter3: (算法分析) 仅仅望着树上的果实，而不去测量树的高度，是个愚人。
——鲁夫斯1.时间复杂度（1）时间频度一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。
但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。
并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。
一个算法中的语句执行次数称为语句频度或时间频度。
记为T(n)。
（2）时间复杂度在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。
但有时我们想知道它变化时呈现什么规律。
为此，我们引入时间复杂度概念。
一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。
记作T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。
时间频度不同，但时间复杂度可能相同。
如：T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同，但时间复杂度相同，都为O(n2)。
按数量级递增排列，常见的时间复杂度有：常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2)，立方阶O(n3),...， k次方阶O(n k),指数阶O(2n)。
随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。
（3）最坏时间复杂度和平均时间复杂度最坏情况下的时间复杂度称最坏时间复杂度。
一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。
这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何更长。
在最坏情况下的时间复杂度为T(n)=0(n)，它表示对于任何输入实例,该算法的运行时间不可能大于0(n)。
平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。
指数阶0(2n)，显然，时间复杂度为指数阶0(2n)的算法效率极低，当n值稍大时就无法应用。
（4）求时间复杂度【1】如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。
此类算法的时间复杂度是O(1)。
x=91; y=100;while(y>0) if(x>100) {x=x-10;y--;} else x++;解答： T(n)=O(1)，这个程序看起来有点吓人，总共循环运行了1000次，但是我们看到n没有?没。
