(
课件网) 数据结构与算法效率 数据结构指的是数据之间的相互关系，即数据组织形式。包括：逻辑结构、存储结构、基本操作（数据运算）。 数据结构概念及类型 常见类型：数组、链表、队列、栈、树和图等。 同一个问题若采用不同的数据结构，算法效率也将不同。 算法效率是指算法执行的时间，算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。 活动一：求和问题的效率探讨 求1+2+3+……+n的和 算法一：高斯求和 n=int(input()) s=(1+n)*n/2 print(s) 例 算法二：累加求和 n=int(input()) s=0 for i in range(1,n+1): s=s+i print(s) 这两种算法的执行效率一样吗？ 算法效率的度量方式 方法一：可依据该算法编制的程序在计算机上运行时所消耗的时间来度量； 方法二：算法效率的高低也可由算法复杂度来度量。 利用计算机的计时功能，对不同算法编制的程序的运行时间进行比较。 方法一：计算算法执行所需时间度量算法效率。 算法一:高斯求和 import time start = time.time() n=int(input()) s=(1+n)*n/2 print(s) end = time.time() print(end - start) 算法二:累加求和 import time start = time.time() n=int(input()) s=0 for i in range(1,n+1): s=s+i print(s) end = time.time() print(end - start) 任务要求 执行算法一和算法二的程序，输入不同的n,并将运行时间记录在任务单上，比较分析两种算法的算法效率。 结 论 当输入的问题规模n大到一定程度，高斯求和的运行时间低于累加求和算法， 高斯求和的算法效率高。 算法复杂度分为时间复杂度和空间复杂度。 方法二：预估算法复杂度度量算法效率 时间复杂度: 指该算法中基本操作重复执行的次数与问题规模n的某个函数。 空间复杂度:指该算法在运行过程中临时占用存储空间大小的度量。 算法时间复杂度的表示 算法一:高斯求和 n=int(input()) s=(1+n)*n/2 print(s) 算法二:累加求和 n=int(input()) s=0 for i in range(1,n+1): s=s+i print(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)=3 O(3) O(1) 常量阶 算法二：累加求和 T(n)=2n+3 O(2n+3) O(2n+1) 线性阶 O(n) O(2n) 结论 时间效率:O(1)
