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
|
||
### 对数器
|
||
### 局部最小值
|
||
数据状况和问题本身梳理问题。
|
||
二分排他性
|
||
俩边开始找，根据趋势，二分处理。 |