第一章 数据结构与算法

1.数据结构1.1数据结构的三要素1.1.1逻辑结构定义数据中各个元素之间的逻辑关系本质就是为如何在计算机中存储做铺垫常见的逻辑结构集合所有数据只是被放在一起彼此之间没有任何联系线性结构数据之间只存在一对一的关系树形结构数据之间是一对多的关系图结构数据之间是多对多的关系1.1.2存储结构定义存储结构又称物理结构指数据在计算机中如何存放常见的存储结构顺序存储把逻辑上相邻的元素存储在物理上也相邻的存储单元中链式存储通过指针来存储前一个或者下一个数据的地址从而实现元素和元素之间的关系1.1.3数据的运算定义包括数据结构的实现以及基于数据结构上的各种操作2.算法算法通俗来讲就是解决问题步骤的集合算法可以没有输入但一定要有输出2.1算法好坏的度量时间和空间的消耗情况就是我们度量一个算法好坏的标准2.2时间复杂度在计算机科学中算法的时间复杂度是一个函数式T(N)它定量描述了该算法的运行时间。这个T(N)函数式计算了程序中语法的执行次数。2.2.1 大O表示法在计算时间复杂度的时候一般会把T(N)中对结果影响不大的项忽略掉该种表示时间复杂度的方式称为大O渐进时间复杂度。是一种粗略的估计方式只看影响时间开销最大的一项。推导大O渐进时间复杂度的规则1.时间复杂度函数式T(N)中只保留最高阶项去掉那些低阶项2.如果最高阶项存在且不是1则去除这个项目的常数系数3.T(N)中如果没有N相关的项目只有常数项用常数1取代所有加法常数。2.2.2最优、平均和最差时间复杂度在查找的过程中需用x与数组中元素依次比较因此总的比较次数就是该算法的时间复杂度。则若待查找元素x为21只需比较1次为算法的最优情况若待查找元素为17或者是不存在的元素需要比较n次为算法的最坏情况所有情况的比较次数之和除以总次数为算法的平均情况查找第一个元素比较1次查找第2个元素需比较2次...查找第n个元素需比较n次假设每个元素查找的概率相同则平均比较次数为f(n)1n/2因此算法最好时间复杂度为O(1);最坏时间复杂度为O(n);平均时间复杂度为O((1_n)/2),也就是O(n)但是无论是在竞赛还是工程中算法的时间复杂度一般为最差情况。因为最差情况是人对一件事情所能承受的底线因此find算法的时间复杂度为O(n).2.3空间复杂度案例一冒泡排序案例二递归求阶乘2.4常见复杂度的增长对比2.5算法竞赛中的时间限制和空间限制1.信息学竞赛中C通常设定1到2秒的时间限制要控制运行次数在至之间2.空间限制在128MB或256MB可以开一个3*大小的int类型数组或者5000*5000大小的二维数组一般情况下都是够用的。