17.数据结构相关概念 知识点梳理- 2023届浙教版（2019）高考信息技术专题复习（选修）

第十七章 数据结构、算法效率以及大数据时代数据组织 一、数据结构 1.数据结构的设计：在计算机程序设计中，根据问题求解的需要，对数据进行有效的整理和组织，并以一定的形式加以存储和表示的过程。程序=算法+数据结构。 2.数据结构的概念： [1]数据元素是数据的基本单位，数据结构也称为元素、节点、顶点、记录等。有时一个数据元素可以由若干个数据项（链表节点有值域和指针域）组成，数据项是具有独立含义的最小数据表示单位。 [2]数据类型指的是具有相同性质的计算机数据的集合在这个数据集合上的一组操作。数据类型可以分为基本数据类型(也称为原子数据类型)和结构数据类型。基本数据类型由计算机编程环境提供(Python提供了整型、实型、布尔型、字符串型四种)；结构数据类型需要用户根据实际情况定义(Python中提供了列表、字典、元组和集合)。 [3]数据结构指的是数据之间的相互关系，即数据的组织形式。它包括了三个内容：1.数据元素之间的逻辑关系，也称为数据的逻辑结构；2.数据元素及其关系在计算机存储器内的表示，也称为数据的存储结构或者物理结构；3.数据的运算，即对数据施加的操作。 二、算法效率 算法效率的高低可以由算法复杂度来衡量，算法复杂度一般分为时间复杂度和空间复杂度。 1.时间复杂度 时间复杂度反映了算法执行所需要的时间。算法运行时，一般将算法中语句的执行总次数作为时间复杂度的度量标准。语句的总执行次数T(n)是关于问题规模n的函数，所谓问题规模，就是问题大小，即衡量输入数据量的整数。例如冒泡排序中，用原始列表中数据的个数作为问题规模。 时间复杂度常用符号O表述，用于反映程序执行时间随问题规模增长而增长的量级。 (1)推导大O阶的方法： [1]用常数1取代运行时间中的所有加法常数 [2]对修改后的运行次数函数中，只保留最高阶项 [3]如果最高阶项存在且不是1，则去除与该项相乘的常数。 例： def bubble_sort(a):     for i in range(1,len(a)): #运行n-1轮         for j in range(len(a)-i): #每轮次数递减             if a[j]>a[j+1]: #运行1次                 a[j],a[j+1]=a[j+1],a[j] #判断成立才运行 return a #运行1次 先计算T(n)=+1 [1]用1取代常数项： [2]保留最高项： [3]去除最高阶常数，得O(n2) (2)常见的时间复杂度的耗时比较 O(1)<O(log2n)<O(n)<O(n2)<O(n3)<O(2n)<O(n!) 2.空间复杂度 空间复杂度反映了算法执行所需要的占用的存储空间 例：计算15!可以使用循环和递归两种方式实现 #循环求15! n = 15 s = 1 for i in range(1,n+1):     s *= i print(s) #递归求15! def fac(n):     if n == 1:         return 1     else:         return n*fac(n-1) print(fac(15)) 用循环方式求解时，内存中存储的只有s、i、n三个临时变量，且运行过程中消耗的存储空间不会随着问题规模n增大而增大，空间复杂度为S(1)。而用递归方式求解时，代码在不断的创建新的fac函数，且运行过程中消耗的存储空间随着问题规模n增大而增大，空间复杂度为S(n)。 3.空间复杂度和时间复杂度的关系 对于一个算法来说，它的时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时，可能需要消耗更多的储存空间。 反之，如果追求较好的空间复杂度，算法执行的时间可能就会变长。程序员常说的“时间换空间”或“空间换时间”就是这个道理。 [拓展]算法稳定性 算法稳定性仅针对排序算法而言。在一组待排序列表中，如果存在任意两个相等的记录a1和a2,且在待排序列表中a1在a2前，如果在排序后a1依然在a2前，即它们的前后位置在排序前后不发生改变，则称为排序算法为稳定的。 三、数据结构对算法效率的影响 在计算机科学中，数据结构与算法有着密不可分的关系。解决实际问题时，数据总是需要以一定的结构组织在一起，不同的组织方式在解决同一类问题时，处理效率往往是不同的。故在设计算法时，需要根据实际情况选择合适的数据结构。 例如，超市商品数据库中，经常要执行两种操作：1.部分临期或新上架商品往往价格会有优惠，对这些商品就需要查找并修改价格；2.商品更换了供应商，需要将新商品数据插入，原商品数据删除。现在可选择的数据结构有数组和链表两种，数据结构的选择分析如下： 针对操作1：从算法效率角度考虑，数据结构采