文章目录
研究时间复杂度的重要性
我们知道CPU提升的速度是很慢的，就算夸张点10年间提升了10000倍
如果一个可以有时间复杂度为 O(n) 的算法的程序，我们写成了 O(n2)，那么程序只提升了 10000=100倍 ,而对于O(n)时间复杂度的算法却能提升10000倍
最坏情况和平均情况
示例：
在一个由n个元素的数组中，按顺序查找一个数
最好的情况是查找的就是第一个数，复杂度 O(1)
平均运行时间需要从概率来看，也就是期望
每个数是查找的概率是 1/n ，然后乘以对应的随机变量
期望 E=1∗1/n+2∗1/n+...+n∗1/n=(1+n)/2
所以平均查找次数是2(1+n)次
最坏情况是这个数字在最后一个位置，所以需要查找n次
平均运行时间是最有意义的，因为这是一个通常的运行时间，比如除了双十一外的364天，淘宝运行时间都是1秒，但是最坏情况是双十一那天，淘宝运行时间可能是100秒
最坏情况运行时间是一种保证，也就是说运行时间不会再多了，这在实际应用中是一个很重要的需求，所以一般我们说的时间复杂度都是指最坏情况的运行时间
时间复杂度的渐进表示法
我们把语句的总的执行次数记作 T(n)
T(n)是关于问题规模n的函数
大O表示法
- T(n)=O(f(n))表示存在常数C>0,n0>0，使得当n>=n0时有 T(n)<=Cf(n)
对于充分大的n而言，f(n)是T(n)的某种上界
但是一个东西的上界可以有很多个，太大的上界对我们分析算法复杂度没有什么参考意义，我们希望跟真实情况越贴近越好
推导大O阶：
- 用常数取代运行时间中的所有加数常数
- 在修改后的运行次数函数中，只保留最高阶项
- 如果最高阶项且不是1，则去除与这个项相乘的常数 得到的结果就是大O阶
例1：T(n)=4n3 + 7n2 + 53logn + 2
推导大O阶得：T(n)=O(n3)
例2：O(3)=O(1)
例3： O(2logn+n/2)=O(n)
- T(n)=Ω(g(n))表示存在常数C>0,n0>0，使得当n>=n0时有 T(n)>=Cg(n)
- T(n)=θ(h(n))表示同时有 T(n)=O(h(n))和 T(n)=Ω(h(n))
常见的时间复杂度
常见的时间复杂度所耗时间的大小排名：
O(1)<O(logn)<O(n)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)学数学的时候用的记忆技巧：对幂指阶超
空间复杂度分析
算法空间复杂度的计算公式记作： S(n)=O(f(n)) ，其中 n 为问题的规模， f(n)为语句关于 n 所占存储空间的函数
一个程序执行时，除了需要存储程序本身的指令、常数、遍历和输入数据外，还要存储对数据操作的存储单元
如果输入数据所占空间只取决于问题本身，与算法无关，那我们只需要分析该算法在实现时所需的辅助空间，也就是分析额外使用的空间即可
例如：
下面的代码输入数据matrix所占空间与算法优劣没有关系，所以我们只需要看额外的使用空间即可
这里我们定义了变量：n、m、d、x、y、a、b，数组：dx，dy，res
用大O推导法知S(N)=O(N)，其中N表示矩阵中的所有元素个数N=n∗m（需要res数组来存储信息）
class Solution {
public:
vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
if(!matrix.size() || !matrix[0].size()) return {};
int n = matrix.size(), m = matrix[0].size();
vector <int> res;
int dx[] = {0, 1, 1, -1}, dy[] = {1, -1, 0, 1};
int x = 0, y = 0, d = 0;
for (int i = 1; i <= n * m; i ++) {
res.push_back(matrix[x][y]);
matrix[x][y] = INT_MAX;
if (i == n * m) break;
// 利用(a,b)找到下一个可以走的点
int a = x + dx[d], b = y + dy[d];
while(a < 0 || a >= n || b < 0 || b >= m || matrix[a][b] == INT_MAX) {
d = (d + 1) % 4;
a = x + dx[d], b = y + dy[d];
}
// 让(x,y)变成下一个可走的点，然后进入下一个循环
x = x + dx[d];
y = y + dy[d];
if (d == 0 || d == 2) d = (d + 1) % 4;
}
return res;
}
};