浙教版信息技术高中选修1 数据与数据结构5.1 数据结构与算法效率-课件.pptxVIP

二叉树的基数据结构与算法效率本操作浙教版信息科技

数据结构指的是数据之间的相互关系，即数据组织形式。包括：逻辑结构、存储结构、基本操作（数据运算）。常见类型：数组、链表、队列、栈、树和图等。同一个问题若采用不同的数据结构，算法效率也将不同。算法效率是指算法执行的时间，算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。数据结构概念及类型

求1+2+3+……+n的和算法一：高斯求和n=int(input())s=(1+n)*n/2print(s)例算法二：累加求和n=int(input())s=0foriinrange(1,n+1): s=s+iprint(s)这两种算法的执行效率一样吗？活动一：求和问题的效率探讨

方法一：可依据该算法编制的程序在计算机上运行时所消耗的时间来度量；方法二：算法效率的高低也可由算法复杂度来度量。算法效率的度量方式

利用计算机的计时功能，对不同算法编制的程序的运行时间进行比较。算法一:高斯求和importtimestart=time.time()n=int(input())s=(1+n)*n/2print(s)end=time.time()print(end-start)算法二:累加求和importtimestart=time.time()n=int(input())s=0foriinrange(1,n+1): s=s+iprint(s)end=time.time()print(end-start)任务要求执行算法一和算法二的程序，输入不同的n,并将运行时间记录在任务单上，比较分析两种算法的算法效率。结论当输入的问题规模n大到一定程度，高斯求和的运行时间低于累加求和算法，高斯求和的算法效率高。方法一：计算算法执行所需时间度量算法效率。

算法复杂度分为时间复杂度和空间复杂度。时间复杂度:指该算法中基本操作重复执行的次数与问题规模n的某个函数。空间复杂度:指该算法在运行过程中临时占用存储空间大小的度量。方法二：预估算法复杂度度量算法效率

算法一:高斯求和n=int(input())s=(1+n)*n/2print(s)算法二:累加求和n=int(input())s=0foriinrange(1,n+1): s=s+iprint(s)#执行1次#执行1次#执行1次执行次数T(n)=3执行次数T(n)=2n+3#执行1次#执行1次#执行n次#执行n次#执行1次时间复杂度常用符号O表示，记作:O(T(n))它表示随着问题规模n的增大，算法执行时间的增长率和T(n)的增长率相同算法时间复杂度的表示

算法一：高斯求和T(n)=3O(3)O(1)常量阶算法二：累加求和T(n)=2n+3O(2n+3)O(2n+1)线性阶O(n)O(2n)结论时间效率:O(1)O(n)算法时间复杂度的表示

n=int(input())s=0x=0foriinrange(1,n+1):forjinrange(1,n+1):x=x+1s=s+xprint(s)#执行1次#执行1次#执行1次#执行n次#执行n*n次#执行n*n次#执行n*n次#执行1次算法时间复杂度：O(3n2+n+4)O(3n2+n+1)O(3n2)O(n2)平方阶试一试：推导算法时间复杂度

阶术语O(1)常量阶O(n)线性阶O(n2)平方阶O(log2n)对数阶O(n3)立方阶O(2n)指数阶算法的时间复杂度反映了程序执行时间随问题规模增长而增长的量级。常见的算法时间复杂度

数据结构逻辑结构存储结构基本操作数组确定连续增、删、改、查链表确定不连续增、删、改、查数据结构查看第n个元素的时间复杂度插入、删除元素时间复杂度数组链表head移动O(1)O(n)O(n)O(1)活动二：数据结构对算法效率的影响

数学家斐波那契在他的《算盘书》里排了一个数列:1,1,2,3,5……这个数列可以和黄金分割联系起来。这个数列越排到后面,前一个数与后一个数的比值就越接近0.61