入门基础
Siona
入门基础
算法与数据结构基础知识
算法的特性
- 五个特征：有穷性、确定性、可行性、有输入、有输出
- 设计原则：正确性、可读性、健壮性（代码 bug 少，且系统比较稳定）
- 高效率与低存储：内存＋CPU 堆栈内存 OOM
- 好的算法：内存占用最小，CPU 占用最小，运算速度最快。
- 评价算法的两个重要指标：
- 时间复杂度：运行一个程序所花费的时间。
O() - 空间复杂度：运行程序所需要的内存 OOM
- 时间复杂度：运行一个程序所花费的时间。
时间复杂度
时间复杂度计算的意义：
怎么测试接口的性能？—— 压测、冒烟。依赖测试环境，流程很长，导致规模或数据不准确。
如何表示？
表示方法：大 O 表示法。 O(1) > O(logn) > O(n) > O(nlogn) > O(n^2) > O(n^x)
如何分析？
- 找 for、while 递归。且要找循环量最大的那一段。
- 同级循环怎么计算？
几种常见的时间复杂度分析【指的是某一段代码】
计算时间复杂度往往是计算比较大的，而且是不确定的数。如果已经确定了，那么就不用计算了，也就是我们说的常量。
- 常数：
O(1)。1 是常数，所有能确定的数字都用O(1)表示，O(1000) => O(1)。 - 对数：
O(logn)、O(nlogn)。 - 线性：
O(n)。 - 线性对数：
O(nlogn)。 - 平方：
O(n^2)。 - n 次方：
O(n^n)。
如何找时间复杂度？
- 找到有循环的地方；
- 找有网络请求（RPC、远程调用、分布式、数据库请求）的地方；
- 测试时间：log 打印，计算平均时间。