44 lines
1.2 KiB
Markdown
44 lines
1.2 KiB
Markdown
|
# 认识复杂度、对数器、二分法或异运算
|
|||
|
|
1. 时间复杂度
|
|||
|
|
2. 额外空间复杂度
|
|||
|
|
3. 常数项，一个操作的执行时间不以具体样本量为转移（数组寻址），每次执行时间都是固定的时间。
|
|||
|
|
### 时间复杂度
|
|||
|
|
#### 选择排序
|
|||
|
|
1. n*（看+比）+1
|
|||
|
|
2. （n-1）* n*（看+比）+1
|
|||
|
|
3. （n-2）* n*（看+比）+1
|
|||
|
|
4. 2*（n+n-1+n-2+····+1）+n 看+比 2
|
|||
|
|
5. 2an平方+bn+n+c
|
|||
|
|
6. 2an平方
|
|||
|
|
最高阶,选出最小的，从头开始放。
|
|||
|
|
#### 冒泡排序
|
|||
|
|
1. 相邻的两个比较，大的放后面，最大值在后面。
|
|||
|
|
2. n-1
|
|||
|
|
3. n-2
|
|||
|
|
4. n-3
|
|||
|
|
5. 1
|
|||
|
|
5. n平方
|
|||
|
|
#### 插入排序
|
|||
|
|
1. 最好n
|
|||
|
|
2. 最差n平方
|
|||
|
|
#### 计算时间复杂度
|
|||
|
|
1. 按照最坏的情况来
|
|||
|
|
2. 拆分为一个个基本动作
|
|||
|
|
3. 如果数据量为n，看基本动作和n之间的关系。
|
|||
|
|
4. 只把高阶项留下，低阶项和常数项去除。
|
|||
|
|
### 常数项
|
|||
|
|
### 最优解
|
|||
|
|
1. 时间复杂度
|
|||
|
|
2. 空间复杂度
|
|||
|
|
#### 常数时间操作
|
|||
|
|
1. 常见算数操作
|
|||
|
|
2. 移位、位运算
|
|||
|
|
3. 复制、比较、自增、自减操作
|
|||
|
|
4. 数组寻址操作
|
|||
|
|
#### 非常数时间操作
|
|||
|
|
1、链表LinkedList
|
|||
|
|
### 对数器
|
|||
|
|
### 局部最小值
|
|||
|
|
数据状况和问题本身梳理问题。
|
|||
|
|
二分排他性
|
|||
|
|
俩边开始找，根据趋势，二分处理。
|