1.有序列表逻辑结构和存储结构 四种逻辑结构: 四种存储结构: 在计算机内任何逻辑结构只能用顺序存储和链式存储实现。 随机访问表示到任何一个位置的时间相等,数组支持随机访问。 链式存储在内存中跳跃存放 链式存储的前提是表示整个结构时只有一个指针L,称为头部。L指向A,A中除本身数据外有一个指向下一个存储数据的位置信息,可以不断向下链接。 2.时间复杂度和空间复杂度 算法是对特定问题求解步骤的描述。 算法的特性有:有穷、确定、可行、输入、输出。
时间复杂度: ::: tip 用O体现算法的时间复杂度的记法称为大O记法。主要关心f(n)的最高阶数,表示随着问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐进时间复杂度,简称时间复杂度。 O(1)为常数阶,只要代码的执行次数是常数次,不会随着问题规模n的增长而增长,时间复杂度都是常数阶。 ::: ::: warning 规定:时间复杂度的计算忽略高阶项系数和低阶项。 ::: 如:算法执行次数为3n²+5n,时间复杂度为O(n²)。 例: 分析:i<n,i=1,则从i到n跳出循环共执行n-1次,忽略低阶项系数,1忽略,剩下n。 时间复杂度T(n)=O(n)。 例: 分析:执行频次最高的语句是x=2x。x可能的取值是2、4、8、16…,x的取值以2的幂次增长,设运行t次,x的值为2的t+1次方,即2的t+1次方<n/2,两边求对数,t=log2(n/2)-1=log2n。 时间复杂度T(n)=O(log2n)。 例: 分析:内层循环执行了log2n次,外层执行了n次,总计执行次数为nlog2n次。 例: 输入可以有多个因子 嵌套循环: 并列循环: 空间复杂度 *n个元素数组排列时,不使用随着n的增长而增长的空间,空间复杂度为O(1)。**