1.复习内容
2.灵感代办
3.学习内容
-
算法效率衡量
-
大O记法
- 时间复杂度:假设存在函数f,使得算法A处理规模为n的问题示例所用时间为T(n)=O(f(n)),则称O(f(n))为算法A的渐近(忽略常数)时间复杂度,简称时间复杂度,记为T(n)
-
最坏时间复杂度一般是衡量算法的标准
- 最优时间复杂度
- 最坏时间复杂度
- 平均时间复杂度
-
时间复杂度的几条基本计算规则
- 一条基本语句 时间复杂度为 O(1)
- 顺序结构,时间复杂度用加法
- 循环结构,时间用乘法
- 分支结构,时间复杂度取最大值(for n次里面 if n,就是n^2)
- 判断一个算法的效率,关注操作数量最多的,其余次要项和常数项省略
- 没有特殊说明,算法时间复杂度说的一定是最坏时间复杂度
-
常见时间复杂度
-
执行次数函数举例
阶
非正式术语
12
O(1)
常数阶
2n+3
O(n)
线性阶
3n2+2n+1
O(n2)
平方阶
5log2n+20
O(logn)
对数阶
2n+3nlog2n+19
O(nlogn)
nlogn阶
6n3+2n2+3n+4
O(n3)
立方阶
2n
O(2n)
指数阶
- 注意,经常将log2n(以2为底的对数)简写成logn
-
常见时间复杂度之间的关系

- 所消耗的时间从小到大
- O(1) < O(logn) < O(n) < O(nlogn) < O(n2) <O(n^2logn)< O(n3) < O(2n) < O(n!) < O(nn)
-
Python中List内置操作时间复杂度
- python的extend方法比+的效率要高
- 尽量不要用+来操作列表,+=倒是可以
- +=是被优化过的,所以跟extend差不多

-
Dict内置操作时间复杂度时间复杂度

-
数据结构
-
数据结构定义
- 一些数据(int float str)按照一定结构 (name,age,score)组成的关系,就是数据结构
-
python的内置数据结构
- 列表 ,元组,字典
- 自定义扩展数据结构
-
算法与数据结构
- 程序=数据结构+算法
- 算法是为了解决实际问题而设计的,数据结构是算法需要处理的数据载体
-
抽象数据类型(Abstract Data Type)
- 抽象数据类型(ADT):把数据类型和对数据类型的运算封装在一起
- 常用的数据运算:插入、删除、修改、查找、排序
-
线性表
-
顺序表,就是地址是连续的,列表就是顺序表的实现
-
顺序表的基本布局(传统):
- 索引之所以从零开始,就是因为没有地址偏移量,
- 比如存放int数据,int占用四字节,所以第二个元素就是从相对上一个元素,偏移1个单位(int四个字节)
- 顺序表的构成,
- 开头是容量和个数

- 顺序表有两种实现方法
- 一体式结构
- 地址连续,从头到尾
- 分离式结构
- 一个头指针存放容量,个数,还有一个指向列表的指针
- 元素存储区替换(一体式结构)
- 线性表扩充时候,是所有元素搬迁,全部移动到新开辟的数组中
- 元素存储区扩充(分离式结构)
- 推荐按照数量扩充,以空间换时间
- 每次扩充,有两种方式,一种是按数量扩充,一种是按倍数扩充
- 按数量特点:
- 节省空间,但是扩充操作频繁,操作次数多
- 按倍数特点:
- 减少了扩充操作的执行次数,但可能会浪费空间资源
-
元素外置顺序表(存地址)

-
链表,节点,一个元素,一个是指向下一个节点的指针。
4.扩展延伸知识
-
python的变量本质
- python的变量指向的是一块地址,然后这块地址存的是变量的地址
- a,b=b,a 实际上就是b地址指向的和a地址指向的内容赋值给a,b
- https://www.bilibili.com/video/BV18W411T7Vv?p=10
-
python单双下划线
- "单下划线" 开始的成员变量叫做保护变量,类对象和子类对象可以访问;
- "双下划线" 开始的是私有成员,只有类对象可以访问
- _xxx 不能用'from moduleimport *'导入
- __xxx__ 系统定义名字
- __xxx 类中的私有变量名
5.知识内容个人梳理
6.今天都复习了之前的什么内容
3.学习内容
-
算法效率衡量
-
大O记法
- 时间复杂度:假设存在函数f,使得算法A处理规模为n的问题示例所用时间为T(n)=O(f(n)),则称O(f(n))为算法A的渐近(忽略常数)时间复杂度,简称时间复杂度,记为T(n)
-
最坏时间复杂度一般是衡量算法的标准
- 最优时间复杂度
- 最坏时间复杂度
- 平均时间复杂度
-
时间复杂度的几条基本计算规则
- 一条基本语句 时间复杂度为 O(1)
- 顺序结构,时间复杂度用加法
- 循环结构,时间用乘法
- 分支结构,时间复杂度取最大值(for n次里面 if n,就是n^2)
- 判断一个算法的效率,关注操作数量最多的,其余次要项和常数项省略
- 没有特殊说明,算法时间复杂度说的一定是最坏时间复杂度
-
常见时间复杂度
-
执行次数函数举例
阶
非正式术语
12
O(1)
常数阶
2n+3
O(n)
线性阶
3n2+2n+1
O(n2)
平方阶
5log2n+20
O(logn)
对数阶
2n+3nlog2n+19
O(nlogn)
nlogn阶
6n3+2n2+3n+4
O(n3)
立方阶
2n
O(2n)
指数阶
- 注意,经常将log2n(以2为底的对数)简写成logn
-
常见时间复杂度之间的关系

- 所消耗的时间从小到大
- O(1) < O(logn) < O(n) < O(nlogn) < O(n2) <O(n^2logn)< O(n3) < O(2n) < O(n!) < O(nn)
-
Python中List内置操作时间复杂度
- python的extend方法比+的效率要高
- 尽量不要用+来操作列表,+=倒是可以
- +=是被优化过的,所以跟extend差不多

-
Dict内置操作时间复杂度时间复杂度

-
数据结构
-
数据结构定义
- 一些数据(int float str)按照一定结构 (name,age,score)组成的关系,就是数据结构
-
python的内置数据结构
- 列表 ,元组,字典
- 自定义扩展数据结构
-
算法与数据结构
- 程序=数据结构+算法
- 算法是为了解决实际问题而设计的,数据结构是算法需要处理的数据载体
-
抽象数据类型(Abstract Data Type)
- 抽象数据类型(ADT):把数据类型和对数据类型的运算封装在一起
- 常用的数据运算:插入、删除、修改、查找、排序
-
线性表
-
顺序表,就是地址是连续的,列表就是顺序表的实现
-
顺序表的基本布局(传统):
- 索引之所以从零开始,就是因为没有地址偏移量,
- 比如存放int数据,int占用四字节,所以第二个元素就是从相对上一个元素,偏移1个单位(int四个字节)
- 顺序表的构成,
- 开头是容量和个数

- 顺序表有两种实现方法
- 一体式结构
- 地址连续,从头到尾
- 分离式结构
- 一个头指针存放容量,个数,还有一个指向列表的指针
- 元素存储区替换(一体式结构)
- 线性表扩充时候,是所有元素搬迁,全部移动到新开辟的数组中
- 元素存储区扩充(分离式结构)
- 推荐按照数量扩充,以空间换时间
- 每次扩充,有两种方式,一种是按数量扩充,一种是按倍数扩充
- 按数量特点:
- 节省空间,但是扩充操作频繁,操作次数多
- 按倍数特点:
- 减少了扩充操作的执行次数,但可能会浪费空间资源
-
元素外置顺序表(存地址)

-
链表,节点,一个元素,一个是指向下一个节点的指针。
4.扩展延伸知识
-
python的变量本质
- python的变量指向的是一块地址,然后这块地址存的是变量的地址
- a,b=b,a 实际上就是b地址指向的和a地址指向的内容赋值给a,b
- https://www.bilibili.com/video/BV18W411T7Vv?p=10
-
python单双下划线
- "单下划线" 开始的成员变量叫做保护变量,类对象和子类对象可以访问;
- "双下划线" 开始的是私有成员,只有类对象可以访问
- _xxx 不能用'from moduleimport *'导入
- __xxx__ 系统定义名字
- __xxx 类中的私有变量名
5.知识内容个人梳理
6.今天都复习了之前的什么内容
算法效率衡量
-
大O记法
- 时间复杂度:假设存在函数f,使得算法A处理规模为n的问题示例所用时间为T(n)=O(f(n)),则称O(f(n))为算法A的渐近(忽略常数)时间复杂度,简称时间复杂度,记为T(n)
-
最坏时间复杂度一般是衡量算法的标准
- 最优时间复杂度
- 最坏时间复杂度
- 平均时间复杂度
-
时间复杂度的几条基本计算规则
- 一条基本语句 时间复杂度为 O(1)
- 顺序结构,时间复杂度用加法
- 循环结构,时间用乘法
- 分支结构,时间复杂度取最大值(for n次里面 if n,就是n^2)
- 判断一个算法的效率,关注操作数量最多的,其余次要项和常数项省略
- 没有特殊说明,算法时间复杂度说的一定是最坏时间复杂度
-
常见时间复杂度
-
执行次数函数举例 阶 非正式术语 12 O(1) 常数阶 2n+3 O(n) 线性阶 3n2+2n+1 O(n2) 平方阶 5log2n+20 O(logn) 对数阶 2n+3nlog2n+19 O(nlogn) nlogn阶 6n3+2n2+3n+4 O(n3) 立方阶 2n O(2n) 指数阶 - 注意,经常将log2n(以2为底的对数)简写成logn
-
-
常见时间复杂度之间的关系
- 所消耗的时间从小到大
- O(1) < O(logn) < O(n) < O(nlogn) < O(n2) <O(n^2logn)< O(n3) < O(2n) < O(n!) < O(nn)
-
Python中List内置操作时间复杂度
- python的extend方法比+的效率要高
- 尽量不要用+来操作列表,+=倒是可以
- +=是被优化过的,所以跟extend差不多
-
Dict内置操作时间复杂度时间复杂度
数据结构
-
数据结构定义
- 一些数据(int float str)按照一定结构 (name,age,score)组成的关系,就是数据结构
-
python的内置数据结构
- 列表 ,元组,字典
- 自定义扩展数据结构
-
算法与数据结构
- 程序=数据结构+算法
- 算法是为了解决实际问题而设计的,数据结构是算法需要处理的数据载体
-
抽象数据类型(Abstract Data Type)
- 抽象数据类型(ADT):把数据类型和对数据类型的运算封装在一起
- 常用的数据运算:插入、删除、修改、查找、排序
-
线性表
-
顺序表,就是地址是连续的,列表就是顺序表的实现
-
顺序表的基本布局(传统):
- 索引之所以从零开始,就是因为没有地址偏移量,
- 比如存放int数据,int占用四字节,所以第二个元素就是从相对上一个元素,偏移1个单位(int四个字节)
- 顺序表的构成,
- 开头是容量和个数
- 顺序表有两种实现方法
- 一体式结构
- 地址连续,从头到尾
- 分离式结构
- 一个头指针存放容量,个数,还有一个指向列表的指针
- 一体式结构
- 元素存储区替换(一体式结构)
- 线性表扩充时候,是所有元素搬迁,全部移动到新开辟的数组中
- 元素存储区扩充(分离式结构)
- 推荐按照数量扩充,以空间换时间
- 每次扩充,有两种方式,一种是按数量扩充,一种是按倍数扩充
- 按数量特点:
- 节省空间,但是扩充操作频繁,操作次数多
- 按倍数特点:
- 减少了扩充操作的执行次数,但可能会浪费空间资源
- 索引之所以从零开始,就是因为没有地址偏移量,
-
元素外置顺序表(存地址)
-
-
链表,节点,一个元素,一个是指向下一个节点的指针。
-
-
python的变量本质
- python的变量指向的是一块地址,然后这块地址存的是变量的地址
- a,b=b,a 实际上就是b地址指向的和a地址指向的内容赋值给a,b
- https://www.bilibili.com/video/BV18W411T7Vv?p=10
-
python单双下划线
- "单下划线" 开始的成员变量叫做保护变量,类对象和子类对象可以访问;
- "双下划线" 开始的是私有成员,只有类对象可以访问
- _xxx 不能用'from moduleimport *'导入
- __xxx__ 系统定义名字
- __xxx 类中的私有变量名
5.知识内容个人梳理
6.今天都复习了之前的什么内容