下载文档原格式
算法与数据结构学习指导第一章第1章概述讲课提要【主要内容】1．数据结构的研究目的和研究内容2．数据结构中的几个重要概念和术语3．算法设计的基本要求以及算法复杂度的分析和计算方法【教学目标】1．了解数据结构的研究目的和研究内容2．掌握数据结构中的重要概念和术语3．掌握算法设计的基本要求以及算法复杂度的分析和计算方法【所需课时】2次课。
[第一次课]1．数据结构的研究目的和研究内容2．数据结构中的重要概念和术语[第二次课]3．算法设计的基本要求以及算法复杂度的分析和计算方法学习指导1．概念和术语数据：是能输入到计算机中并能被计算机程序处理的符号的总称。
数据元素：是数据的基本单位，它在计算机处理和程序设计中通常作为一个整体进行考虑和处理。
一个数据元素可由若干数据项组成。
数据对象：是具有相同特征的数据元素的集合，是数据的一个子集。
数据结构：是数据元素的组织形式，或数据元素相互之间存在一种或多种特定关系的集合。
数据的逻辑结构：是指数据结构中数据元素之间的逻辑关系。
数据的存储结构：是数据的逻辑结构在计算机内存中的存储方式，又称物理结构。
数据类型：是一组具有相同性质的操作对象以及该组操作对象上的运算方法的集合。
抽象数据类型：是指一个数学模型以及在该模型上定义的一套运算规则的集合。
算法：建立在数据结构基础上的，为解决问题而采取的步骤和方法。
2．逻辑结构的四种基本形态根据数据元素之间关系的不同特征，通常有下列四类基本结构：（1）集合：结构中的数据元素间除了“同属于一个集合”的关系外，别无其它关系。
（2）线性结构：结构中的数据元素之间存在一个对一个的关系。
（3）树型结构：结构中的数据元素之间存在一个对多个的关系。
（4）图型结构或网状结构：结构中的数据元素之间存在多个对多个的关系。
3．数据存储结构的基本组织方式数据存储结构有顺序和链式两种方式。
（1）顺序存储结构的特点：要借助数据元素在存储器中的相应位置来体现数据元素相互间的逻辑关系，常用高级编程语言中的“一维数组”来描述或实现。
第1章 群体智能算法概述1975年，美国Michigan大学的John Holland[1]教授发表了其开创性的著作《Adapatation in Natural and Artificail System》，在该著作中John Holland教授对智能系统及自然界中的自适应变化机制进行了详细阐述，并提出了计算机程序的自适应变化机制，该著作的发表被认为是群体智能（Swarm Intelligence）[2]算法的开山之作。
随后，John Holland和他的学生对该算法机制进行了推广，并正式将该算法命名为遗传算法（Gentic Algorithm，GA）[3]~[5]。
遗传算法的出现和成功，极大地鼓舞了广大研究工作者向大自然现象学习的热情。
经过多年的发展，已经诞生了大量的群体智能算法，包括：遗传算法、蚁群优化（Ant Colony Optimization，ACO）[6]~[7]算法、差异演化（Differential Evolution，DE）[8]~[12]算法、粒子群优化（Particle Swarm Optimization，PSO）[13]~[16]算法等。
随着群体智能算法在诸如机器学习、过程控制、经济预测、工程预测等领域取得了前所未有的成功，它已经引起了包括数学、物理学、计算机科学、社会科学、经济学及工程应用等领域的科学家们的极大兴趣。
目前关于群体智能计算的国际会议在全世界各地定期召开，各种关于信息技术或计算机技术的国际会议也都将智能进化技术作为主要研讨课题之一。
甚至有专家指出，群体智能计算技术、混沌分析技术、分形几何、神经网络等将会成为研究非线性现象和复杂系统的主要工具，也将会成为人们研究认知过程的主要方法和工具。
1.1 群体智能算法的特点1.1.1 智能性群体智能算法通过向大自然界中的某些生命现象或自然现象学习，实现对于问题的求解，这一类算法中包含了自然界生命现象所具有的自组织、自学习和自适应性等特性。
第一章算法概述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). 算法采⽤的策略、⽅法；(2). 编译产⽣的代码质量；(3). 问题的输⼊规模；(4). 机器执⾏指令的速度。
⼀个算法是由控制结构（顺序、分⽀和循环3种）和原操作（指固有数据类型的操作）构成的，则算法时间取决于两者的综合效果。
为了便于⽐较同⼀个问题的不同算法，通常的做法是，从算法中选取⼀种对于所研究的问题（或算法类型）来说是基本操作的原操作，以该基本操作的重复执⾏的次数作为算法的时间量度。
1、时间复杂度（1）时间频度⼀个算法执⾏所耗费的时间，从理论上是不能算出来的，必须上机运⾏测试才能知道。
但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。
