计算机算法基础

1、2020/7/6，顺序，专业基础课程：数据结构，计算机语言操作系统，编译方法计算机程序：数据结构算法=程序算法：计算机软件的“灵魂”算法是计算机科学和计算机应用程序的核心，2020/7/6，教科书： 章节排列、第一章指南和基本数据结构第二章划分方法第三章贪心方法第四章动态计划第五章搜索和旅行第六章回溯方法第七章分支-边界第八章NP-问题？2020/7/6，第1章指南和基本数据结构，1.1算法的定义和特性1。什么是算法？数字、计算等算法是基本概念。算法是确定类问题的特殊方法。在计算机科学中，算法是使用计算机解决一类问题的正确有效方法的代名词。算法是一组穷规则，规定了解决特定类型问题的一系列运算。

2、2020/7/6，2。算法的五个重要特性确定、能力、输入、输出、贫困、1)确定性：算法的每个运算都必须有正确的定义，没有异议。例如：不确定性的运算5/0是6或7和x加上未赋值的变量，2020/7/6，2)可能性算法要完成的运算是基本运算，原则上，每个运算可以使用纸和笔在“有限”时间内完成。例如：整数的算术运算是“可以”的实数的算术运算是“不能”，2020/7/6，3)，每个输入算法有零个或多个输入。这些输入在算法开始之前给定的量，从特定对象集合域(或范围)中获取，输出与4)输入具有特定关系的量的一个或多个输出的算法。2020/7/6，5)贫穷的算法总是在执行具有贫穷阶段的运算后结束。计算过程：

3、仅满足以下四个特性的规则集：确定、执行能力、输入和输出。算法和计算过程之间的区别：计算过程：操作系统(不关闭的执行过程)算法的及时性：只有在相当贫困的阶段终止的算法才能投入计算机运行。2020/7/6，4。我们主要的工作算法学习涉及五个方面。1)设计算法：创造性活动2)表达算法：思想的表达，SPARKS语言3)确认算法：证明算法可以对所有可能的合法输入获得正确答案。算法证明：已证明算法的正确性，与语言无关的程序证明：已证明程序的正确性4)分析算法：算法的时间，通过空白特性定量分析确定算法的好坏5)测试程序：调试：“调试只能表示有错误，不能表示没有错误”的时空分布图：分析结论验证，优化算法设计这

4、一过程与学习算法的设计和通过学习，掌握计算机算法设计和分析的基本策略和方法，为更复杂、更有效的算法设计奠定了基础，2020/7/6，5。课程关系数据结构编程语言：结构化设计数学基础非数值计算领域的基础知识，2020/7/6，1.2分析算法，1 .分析算法的目的是通过对算法的分析，在将算法转换为实际运行之前，知道为完成一个任务而设计的算法的好坏，运行好的算法，改进坏的算法，避免无益的人力和物力的浪费。算法分析是计算机领域的“古代”和“前沿”任务。，2020/7/6，2。重要假设和协议1)计算机模型的家庭计算机形态理论模型：餐饮机械模型一般计算机模型：连续计算机具有足够的“内存”以在固定时间获取数

5、据单元，2020/7/6，2)计算出的要约算法的运行时间=fi*ti其中fi是算法中使用的特定运算I的数量。用于此操作的“频率数”ti与执行该操作所用的时间与程序语言和硬件有关：确定使用的计算和执行时间。在运算的“时间特性”中，运算的分类：时间限制为常数的运算：整数、浮点数加、减、乘、字符除、分配运算、过程调用等基本算术运算：每个运算的执行时间不同，但通常只需要一个固定时间(单位时间)。2020/7/6，2)计算规则(续)，其他计算：字符串操作：与字符串中的字符数成正比的记录操作：与记录的属性数、属性类型等相关的特性：计算时间没有量化。分析非时间从属为常数的运算的方法：分解为时间常数的多个运算

6、。例如：tstring=length (string) * tchar，2020/7/6，3)工作数据集的选择可以反映算法在最佳、平均和最坏情况下工作的数据配置。然后使用这些数据配置运行算法，以了解算法的性能。编写测试数据是程序测试和算法分析中的关键技术之一。分析为算法的数据集：将算法的一般特性反映为程序准确性和性能测试的数据集：测试程序的对与错、边界值、2020/7/6，3。算法分析方法？对算法的综合分析可以分为预分析两个阶段。也就是说，为算法查找一个时间/空间边界函数。也就是说，通过计算的“理论”分析，算法的时间和空间特性的特性函数(，)与计算机物理、软件和硬件没有直接关系。后测试：对算法

7、进行编程后，实际将其放入计算机中运行，收集执行时间和空间占用等统计信息，分析判断直接与物理实现相关。2020/7/6，1)预分析目的：以一种形式表示算法特性，并对“理论上”算法的“好坏”进行测量的尝试。如何提供反映算法特性的说明？统计算法中各种运算的执行方式，包括引用每次执行每个运算的次数执行该运算所用的时间。算法执行时间=fi*ti，2020/7/6，频率数频率数：算法执行语句或运算的次数。例如：xx y for I 1 to n do for I 1 to n do x y for j 1 to n do repeat x y repeat repeat(a)(b)(c)分析：(a): x

8、x y运行了一次(b)，2020/7/6，数量级别测量频率数的“大小”测量语句数级别：语句执行频率示例：1，n，N2算法的计数级别：算法中所有语句的执行频率总和。数量级别反映了算法复杂性最本质的特性。范例：解决相同问题的三个演算法各有n、N2、n3数量层次。N=10时，可能的执行时间为10，100，1000个单比特时间与环境因素无关。，2020/7/6，频率数的函数表示在预分析阶段，针对频率数的算法的函数与大小n相关的函数的形式。g(n)是另一种算法，g(n)是g(n)的典型形式，例如logn、nlogn、N2:n的基于简单函数的“实际”可以得到：1)基于函数的最大值2)最大子项和函数整体关系

9、。空间特性分析(与时间特性分析相似，近似)，2020/7/6，2)后测试目的：验证以前的分析结论，比较和优化设计算法，包括运行程序，实际运行所需的准确时间和空间的统计执行，与预分析结论进行比较，以及准确性和执行性能。分析方法：时间，空性能分布图，2020/7/6，4。计算时间的渐近表示，记录：算法的实际计算时间为f(n)，计算时间的边界函数为g(n)。其中n是输入或输出规模的测量。F(n)表示算法的“实际”执行时间与机器和语言相关。G(n)是预分析的结果，是简单形式的函数，例如nm，logn，2n，n！等。与频率数相关但与机器和语言无关的函数。上限()、下限()、平均值()等算法运行时间如下：

10、2020/7/6，1)为所有nn0定义上限函数，如果|f(n)| c|g(n)|存在，则表示f(n)=(g(n)。也就是说，如果算法在系统中使用n值保持不变的相同类型的数据运行，则使用的时间将小于|g(n)|中的常量。因此，g(n)是计算时间f(n)的上限函数。F(n)的比例为g(n)。如果尝试求最小的g(n)，则结果为f(n)=(g(n)。2020/7/6，多项式定理1 A(n)=如果amnm a1n A0是m阶多项式，则存在A(n)=(nm)。换句话说，变量n的固定阶为m的任意多项式等于此多项式的最高nm同构。证明：n0=1，存在于nn0时| a(n)| am | nm | a1 | n

11、| A0 |(| am | | am-1 |/n | A0 |/，2020/7/6，计算时间的数量级大小对算法的有效性具有决定性影响的示例：假设解决同一问题的两个算法都有n个输入，则计算时间的数量级分别为N2和nlogn。N=1024:需要分别进行1048576和10240操作。N=2048:需要分别进行4194304和22528次运算。分析：比较相同规模的计算量：大小增加时的比较：n增加一倍时，一个(N2)的算法计算时间增加四倍，一个(nlogn)算法完成时间超过一倍。2020/7/6，多项式时间算法和指数时间算法，多项式时间算法：通过可用多项式(函数)计算时间边界的算法。典型的多项式边界函

12、数包括：(1)(logn)(n)(n)(n logn)(N2)(n3)指数时间算法：使用计算时间的指数函数界限的算法典型指数时间边界函数：(2n) (n！(nn)说明：n的值越大，指数时间算法和多项式时间算法在计算中的差异就越大。2020/7/6，典型计算时间函数曲线，2020/7/6，我知道在数据集较大的情况下，在传统计算机系统上运行比(nlogn)更复杂的算法更困难。指数时间算法仅在n值非常高的情况下有效。扩大顺序处理程序处理的问题规模的有效方法不仅仅是加快计算器的速度，而是降低算法的计算复杂性。2020/7/6，计算时间函数值比较，3，2020/7/6，定义1.2如果有两个正常c和n0，

13、则对于所有nn0，| f(n)| c | g(n)| f因此，g(n)是计算时间f(n)的下限函数。我想求最大的g(n)、f(n)=(g(n)。，2)下限函数，2020/7/6，定义1.3常数C1，C2和n0存在时，所有nn0的C1 | g (n) | f (n) | C2 | g (n) |表示意义请参阅：如果既有f(n)=(g(n)和f (n)=(g (n)限制函数，2020/7/6，4)边界函数的性质，1)。有传达性。(相同)2)，和3。也就是说，定义了从定义出发的对等关系(对等类)证明。证明过程有点。2020/7/6，5。常用整数求和公式(算法分析中统计语句频率的聚合公式为：对于2020/7/6，1，1.3 SPARKS语言，本书为从算法中选择的计算机语言类型PASCAL语言结构设计，2020/7/6，1)。基本语法组件，1)数据类型整数integer实际float布尔字符char，2)变量声明类型说明符变量；Integer i，j；boolean b；Char c 3)阵列随机整数下标integer a (1:5，7336920)integer b(5，7336920)，2020/7/6，4)配置运算(变数)5)逻辑运算：and or not 6)