algorithms_rogramming.jpg
序言
虽然做了多年 coding 工作，但是谈起算法还是觉得离自己很远，似乎没有算法也可以写出能够满足用户需求的程序。不过最近觉得自己这样下去很难有所提升，所以准备开始刷题。
programming_confusing.jpg
开始刷了点 LeetCode 的题，感觉有点无从下手，不知所措的感觉。为此决定还是从基础开始吧，先看数据结构。那么我们算法除了实现一些方法，而且更多会考虑时间和空间资源上销毁
基本信息
| 分类 | 内容 |
|---|---|
| 更新频率 | 日更(尽量) |
| 语言 | python /java |
| 适用范围 | 面试 |
什么是算法
算法(Algorithm)是指用来操作数据、解决程序问题的一组方法。对于同一个问题，可能会有多种不同的算法来给出正确答案，但在过程中消耗的资源和时间却会有很大的区别。这也就是我们研究算法的目的。
时间复杂度和空间复杂度
- 时间复杂度：是指执行当前算法所消耗的时间。
- 空间复杂度：是指执行当前算法需要占用多少内存空间。
no_free_lunch.jpeg
因此，评价一个算法的效率主要是看它的时间复杂度和空间复杂度情况。然而，有的时候时间和空间却又是鱼和熊掌，不可兼得的，那么我们就需要从中去取一个平衡点。
programming_language.jpeg
语言
准备提供这些语言版本关于问题的解决方案。
- javascript
- java
- python
- go
- rust
- cpp
时间复杂度
平时优化 code 时，我通常是在代码段前后输出时间来计算方法的耗时，认为这就是算法消耗的时间。不过我们这种优化的前提是我们使用的同样硬件配置，因为这个算法更多是因为硬件支持。其实我们是有一套尺度来衡量我们算法。
因此，另一种更为通用的方法就出来了：**大O符号表示法 **，即 T(n) = O(f(n))
const n = 10;
var j = 0;
for(let i=1; i<=n; ++i)
{
j = i;
j++;
}
通过大 O 符号表示法，这段代码的时间复杂度为：O(n) ，为什么呢?
复杂度量级
常见的时间复杂度量级有：
- 常数阶O(1)
- 对数阶O(logN)
- 线性阶O(n)
- 线性对数阶O(nlogN)
- 平方阶O(n²)
- 立方阶O(n³)
- K 次方阶O(n^k)
- 指数阶(2^n)
const N = 10;
var a = 0;
var b = 0;
for (let i = 0; i < N; i++) {
a = a + Math.random() // $N \times 1$ 操作 = O(N)
}
| 维度 | 值 |
|---|---|
| 时间复杂度 | O(N) |
| 空间复杂度 | O(1) |
for (let i = 0; i < N; i++) {
a = a + Math.random() // $N \times 1$ 操作 = O(N)
b = b + Math.random() // $N \times 1$ 操作 = O(N)
}
| 维度 | 值 |
|---|---|
| 时间复杂度 | O(N) + O(N) = O(N) |
| 空间复杂度 | O(1) |
for (let i = 0; i < N/2; i++) {
b = b + Math.random() // $ \frac{1}{2} N \times 1$ 操作 = O(N)
}
| 维度 | 值 |
|---|---|
| 时间复杂度 | |
| 空间复杂度 | O(1) |
空间复杂度 O(1) 因为不依赖于 N 所以是常数复杂度
for (let i = 0; i < N; i++) {
for (let j = N; j > i; j--) {
a = a + i + j;
}
}
最简单有效方法，就是我们将每一个步骤一一列出后来总结规律来解决问题
i = 0: j = N...1 (N)
i = 1: j = N...2 (N-1)
i = 3: j = N...3 (N-2)
i = N-1: j = N (1)
时间复杂度，因为 复杂度要严格大于
的复杂度
| 维度 | 值 |
|---|---|
| 时间复杂度 | |
| 空间复杂度 |
var a = 0;
var i = N;
while (i > 0) {
a += i; //1 个操作
i /= 2; //1 个操作
}
网友评论