算法 笔记-待续
Opened this issue · 0 comments
jianxiaoBai commented
关于算法
- 什么是算法?
- 算法的本质是寻找规律并实现
- 如何发现规律?
- 发现输入和输出的关系, 寻找突破点
- 如何实现?
- 实现是程序+数据结构的结合体
- 什么是时间复杂度?
- 时间复杂度是按照最大执行次数计算的
- 什么是空间复杂度?
- 空间复杂度是按照占用最大内存空间计算的
关于大O的概念?
- n表示数据规模
O(f(n))表示运行算法所需要执行的指令数, 和f(n)成正比
关于大O的提现
二分查找法 O(logn) => 所执行指令书: a * logn
寻找数组中的最大/最小值 O(n) => 所执行指令书: b * n
归并排序算法 O(nlogn) => 所执行指令书: c * nlogn
选择排序法 O(n^2) => 所执行指令书: d * n^2
举例
算法A: O(n) 所需执行指令数: 10000*n
算法B: O(n^2) 所需之星指令数: 10 * n^2
| n | A指令数 10000n | B指令数 10n^2 | 倍数 |
|---|---|---|---|
| 10 | 10^5 | 10^3 | 100 |
| 100 | 10^6 | 10^5 | 10 |
| 1000 | 10^7 | 10^7 | 1 |
| 10000 | 10^8 | 10^9 | 0.1 |
| 10^5 | 10^9 | 10^11 | 0.01 |
| 10^6 | 10^10 | 10^13 | 0.001 |
时间复杂度 O 衡量的是量级上的差距,
这种量级上的差距表现在,当数据达到一个临界点时,
时间复杂度低的算法,就一定比时间复杂度高的算法要快,
而且n越大,差距就越大再有一些复杂度很高的算法可能有常数级小的优势, 数据规模小的时候是有意义的.
对于所有的高级排序算法, 当数据规模小到一定程度时可选择插入排序法来进行优化, 优化的效率大约能有10%-15%左右.
算法复杂度比较
O(Cn) -> O(n2) -> O(n) -> O(logn) -> O(1)
| 符号 | 名称 |
|---|---|
| O (1) | 常数(阶，下同) |
| O (logn) | 对数 |
| O [(logn)] | 多对数 |
| O (n) | 线性，次线性 |
| O (n log* n) | log* n 为迭代对数 |
| O (nlogn) | 线性对数，或对数线性、拟线性、超线性 |
| O (n2) | 平方 |
| O (n%), Integer (c> 1) | 多项式，有时叫作'代数'(阶) |
| O (cn) | 指数，有时叫作'几何'(阶) |
| O (n!) | 阶乘，有时叫做'组合'(阶) |
关于大O在各领域的不同 ?
在学术界,严格的讲, O(f(n)) 表示算法执行的上界
什么是算法执行的上界?
归并排序算法的时间复杂度是O(nlogn)的, 同时也是O(n^2)
在业界,我们就是用O来表示算法执行的最低上界.
虽然在学术界归并排序算法复杂度是O(n^2)是对的, 但是在业界我们一般不会说你归并排序是O(n^2)的, 而是O(nlogn).
这不是一个严谨不严谨的问题, 是在业界约定俗成的问题, 世界各大公司都是默认这样的
如果我们设计了一个算法,我们以量级最高的时间复杂度作为主导
比如
O (nlogn + n) = O(nlogn)
O (nlogn + n^2) = O(n^2)