算法设计与分析耿国华第一章

第一章是算法概述，算法设计与分析，算法设计与分析，主编耿国华，本章内容，1.1算法概念1.1.1算法定义与特点1.1.2问题求解的基本过程1.1.3算法设计实例-最大公约数计算1.2算法设计与分析任务1.3算法分析标准1.4算法分析依据1.4.1常用数学表达式1.4.2对数与指数1.4.3数学证明方法1.5算法复杂性分析1.5.1 最差情况和平均情况1.5.3渐进分析1.5.4证明方法1.6本章概述，第1章，1，1.1算法概念，1.1.1算法定义和特征1.1.2问题解决的基本过程1.1.3算法设计示例-最大公约数的计算，第1章，1，1.1引言-定义和特征，1.1.1算法定义和特征定义：算法是一组有限的规则，是为解决特定问题而指定的一系列运算。 重要性：算法是计算机科学领域最重要的基石之一。算法只是解决问题的方法。当解决一个问题时，有许多方法供你选择，但其中之一必须是最优的(相对最优的)。第1章，1.1简介-算法特征，算法特征(1)有限性：算法必须确保在执行有限数量的步骤后结束(2)确定性(模糊性)算法的每一步都必须有一个精确的定义(3)可行的算法在原则上可以精确运行。在现有条件下，这是可以实现的。(4)输入一个算法有0个或多个输入来描述操作对象的初始条件(5)输出一个算法有一个或多个输出来反映处理输入数据的结果。由于算法需要给出解决具体问题的结果，所以没有输出结果的算法是没有意义的。注：这是指广义输出，包括各种形式的处理结果。第一章，1，1.1引言不同于程序、算法和程序算法和程序之间有许多不同，主要表现在以下几个方面：(1)程序是对语言规则的描述，算法是描述处理的方式或步骤。(2)算法依赖程序来完成功能；程序需要算法作为灵魂。(3)一个项目不一定能满足贫困。例如，只要整个系统没有损坏，操作系统就不会停止。即使没有要处理的作业，它仍在动态等待。因此，操作系统不是算法。第一章，1，1.1引言算法描述(1)自然语言所谓的“自然语言”是指日常生活中使用的语言，如汉语和英语。自然语言的描述容易理解和掌握，但不够严谨，容易产生歧义。(2)框图(流程图)这是一个用各种几何图形、流程线和文本描述来描述计算过程的框图。算法的整体结构表达直观，强调了处理流程，便于检查和修改。但是它不能表达数据流。第一章，1，1.1引言-算法描述，算法描述(3)伪代码是介于自然语言和计算机语言之间的一种算法描述。它结构强大，易于编写和理解，并且易于修改。(4)高级语言过于详细。高级语言是用计算机能够理解的语言来表达的，这种语言叫做程序设计。可以直接在计算机上运行。第1章，1.1简介-算法描述方法，算法描述方法(5)类语言接近高级语言，基本句子格式相同(但细节不限于一种模式)，注意力集中在处理步骤上。例如，类PASCAL和类C语言。概要：程序框图通常用于学习和研究算法。它不仅直观、方便、有利于交流，而且在设计算法时能更好地考虑算法执行的动态性能。第1章，1，1.1引言解决问题的基本过程，1.1.2解决问题的基本过程算法是问题的程序化解决。一般来说，解决问题的算法遵循以下步骤：解决问题的需求、建立模型、选择解决方案、设计算法和编程。(1)在弄清楚问题的性质和分析问题之前，应该有一个常见的方法是仔细阅读问题的描述，提出问题，尝试手动处理一些小规模的例子，并考虑特殊情况。不同类型的问题可以用不同的方法来处理。第1章，1.1引言解决问题的基本过程，1.1.2解决问题的基本过程(2)建立问题的描述模型对于数值问题，可以建立数学模型来描述问题。对于非数值问题，我们通常可以建立一个过程模型来描述问题。(3)选择解决方案模型后，我们可以采用不同的方法来处理不同的模型。第一章，1，1.1引言-解决问题的基本过程，1.1.2解决问题的基本过程(4)设计算法对于数值问题，我们可以用数值分析的方法来处理它们。在数值分析中，有许多现有的固定算法可以直接使用。对于非数值问题，我们可以通过数据结构或算法分析和设计来处理，也可以选择一些成熟的方法来处理，如穷举法、分治法、回溯法等。(5)用特定的编程语言以编程方式实现所设计的算法，并在特定的计算机上运行它。第1章，1.2算法设计与分析任务，算法设计与分析任务1。设计阶段主要是关于如何设计一个有效的算法来解决给定的问题。算法设计的任务是为各种具体问题设计高质量的算法，并研究设计算法的一般规则和方法。常用的算法设计方法包括分治法、动态规划法、贪心法和回溯法。第1章，1.2算法设计与分析任务，算法描述2。分析阶段主要是分析判断算法质量的标准和技术。对于设计的每一个特定算法，算法分析的主要任务是使用数字作为工具来讨论它的各种复杂性。复杂度分析的结果可以作为评价算法质量的标准之一，有时也可以为改进算法的方向提供参考。结论：算法设计与分析密切相关，相互影响。所设计的算法需要进行测试和评估，评估后可以对算法的设计进行改进。第1章，1.3算法分析准则，分析准则(1)正确性算法的正确性是最小也是最重要的。正确的算法应该能够获得所有合法输入数据的预期结果。正确性有四个层次：一、程序不包含语法错误；b、程序可以获得满足多组输入数据规格要求的结果；对于典型的、苛刻的、带有恶意的几组输入有正确的结果；所有合法输入的数据都能产生符合规范要求的结果。第1章，1.3算法分析标准分析标准(2)可读性算法的第一个目的是阅读和交流。可读性有助于理解算法以及调试和修改算法。(3)健壮性是指程序处理规范要求之外的输入情况的能力。所谓的健壮系统是指除了规范要求之外的输入，该输入可以被判断为不符合规范要求，并且可以以合理的方式处理。第1章，1.3算法分析标准分析标准(4)评估算法性能时要考虑的另一个因素是算法的运行效率，即估计在计算机上执行根据算法编译的程序所消耗的时间和空间。评价算法运行效率的主要技术指标是：算法运行的时间复杂度和空间复杂度。第一章，1，1.4算法分析基础，1.4.1常见数学术语1.4.2对数和指数1.4.3数学证明方法，第一章，1，1.4算法分析基础，1.4.1术语1，美国电气和电子工程师学会单位表达式：单位按大小升序排列：比特-B，字节-B，千字节-KB，兆字节-MB。2.阶乘函数大于1的任何自然数，用n阶乘表示：n！=123.阶乘的stirling公式是，第1章，1.4算法分析基础，1.4.1，术语3。排列组合这是组合学最基本的概念，排列组合的中心问题是研究给定要求的排列组合和可能情况的总数。4.布尔变量布尔变量是具有两种逻辑状态的变量，包含两个值：真和假，章节，1，1.4算法分析基础，1.4.1，术语5。作为舍入函数的上下舍入符号的一些性质如下：对于以、章、1、1.4算法分析为基础、1.4.2、对数和指数为1、以b为基础的变量，Y的对数可以表示为2。二进制搜索的次数小于或等于、章、1、1.4算法分析基、1.4.2、对数和指数3，对于任何函数M、N、R、任何正整数A、B、章、1、1.4算法分析基、1.4.2、对数和指数4，对于正整数M、N和实数A 0:章、1、1.4算法分析基、1.4.3，证明方法1:反证法：反证法是一种这是一种反角度的证明方法，即肯定问题，否定结论，从而得出矛盾。 例1-3:证明希尔排序的稳定性假设希尔排序是一个稳定的排序算法例2114，从上图可以看出排序结果中1和1的顺序已经改变，所以希尔排序是一个不稳定的排序算法。第1章，1，1，4，1.4算法分析的基础，1.4.3，证明方法2:数学归纳法：数学证明与自然数n有关的命题的一种特殊方法，主要用于研究与正整数有关的数学问题。该方法的证明步骤是：归纳假设、基础和演绎。例1-4。前N个奇数的和是n2，也就是说，证明了当i=1，1=集合i=n-1，当i=n，命题成立。1.5算法复杂性分析方法，1.5.1复杂性函数，1.5.2最佳、最差和平均情况，1.5.3顺序渐进分析方法，1.5.4章，1、1.5算法复杂性分析方法，复杂性是算法所需的计算机资源。我们需要的资源越多，算法就越复杂。相反，所需资源越少，算法的复杂性就越低。它是算法效率的度量，也是评价算法优劣的重要依据。第1章1.5算法复杂性分析方法复杂性根据算法占用计算机资源的类型可分为：算法的空间复杂性和算法的时间复杂性。时间复杂度：时间复杂度分为最佳时间复杂度、最差时间复杂度和平均时间复杂度。最佳时间复杂度是解决类似问题的最小成本，证明了解决问题的下界。相反，这是最糟糕的时间复杂度。平均时间复杂度是平均成本。第1章，1.5算法复杂性分析，1.5.1复杂性函数1。复变函数的复变函数公式是C=F(N，I，a)对于上述复变函数的参数解释如下：N是问题的规则，I是指输入，a是算法本身。问题大小n:反映问题大小的基本定义。第1章，1.5算法复杂性分析方法，1.5.1复杂性函数2。算法时间复杂度算法的执行时间=算法中所有语句的执行时间之和。每个语句的执行时间=语句的执行时间*一次执行所需的实际时间。在非递归算法中，时间计算如下：1for/while循环：循环中的计算时间*循环数2嵌套循环：循环中的计算时间*所有循环数3顺序语句：每个语句的计算时间加起来为4if-else语句：if语句的计算时间和else语句的计算时间中的较大者，第1章，1.5算法复杂性分析方法，1.5.1复杂性函数2。算法的时间复杂度空间复杂度通常记为S(n)，时间复杂度通常记为T(n)。请注意，常数不起作用，只考虑公式中的高阶。例如，时间复杂度函数如下：章，1，对于上述函数，每个参数的含义如下：操作I所需的时间，操作I的次数# define 100/* n可以根据需要定义，这里假设它是100 */Virtumatrixulti(INTAnn，intbnn，intcnn)该算法中每个语句的语句频率是(1)对于(I=0；如果算法的复杂度是一阶线性函数，它可以被记录为n，那么在时间t，新机器解决问题的规模是，也就是说，新机器可以用10n的规模解决问题。3如果算法的复杂性是一阶以上的函数，新机器将不能达到10n的问题规模。例如，对于一个算法，它在新机器上的复杂度将是，也就是说，它只能同时解决规模问题。第1、1、1、2、4、5、5、5、5、5、5、5、5、5、5、5、5、5、5、6、5、5、5、5、5、5、5、5、5、6、6、5、5、6、5、5、5、5、5、5、5、5、5、5、5、5、5、5、5、5、5、5、5、5、5、6、5、6、6、5、5、5、5、5、5、5、5、5、6、5、6、6、6平均复杂度平均情况1-9:要查找的值是x，要查找的表有n个条目。如果x出现在表中的概率是q，x不出现在表中的概率是1-q。如果x出现在表中，如果x不在表中，第1章，1，1，1.5算法复杂性分析方法，1.5.2最佳、最差和平均情况2。最差的时间复杂度是上限3。最佳时间律最优性程度：解决同类问题的最小成本，证明了解决该问题的下界。为了解决这个问题，将算法中的n个元素与n-1进行比较，并且F(n)=n-1A:证明下界的方法是在表中设置不同的元素，=n，n-1项不是最大的，并且输入一个元素，确定最差的时间界。每次比较都会产生一个数字，需要n-1个比较才能产生n-1个数字，第1章，b:确定下限：假设比较次数小于n-1，最多做n-2次，那么如果有2个项目没有比较，就不可能确定谁大谁小，所以这2个项目需要再次比较，所以比较次数是(n-2) 1=n-1，假设是矛盾的，所以w(n)=n-1，比较次数可以1.5算法复杂性分析方法，1.5.3渐进分析1。渐进时间复杂度：如果F和G是定义在N上的函数，那么F和G之间的函数阶可以用渐近形式表示。渐近形式的三个符号：0-低阶-高阶-等阶定义如下。1低阶O:如果所有nn0都有一个正常数c，n0和f(n)g(n)，则记录为