时间/空间复杂度计算
1.算法基本概念
是对特定问题求解步骤的描述，他是指令的有限序列。
他具有5种特性：有穷性，确定性，输入，输出，可行性。
2.算法的度量指标
2.1 时间复杂度
概念：
语句频度：该语句在算法中被重复执行的次数 所有语句的频度之和记为T(n);算法中基本运算也就是循环中最里面的那一层语句的频度记为f(n) 这是时间复杂度T(n)=O(f(n)) 因此算法的时间复杂度是在研究：
时间开销T(n) 与 问题规模n 的关系2. 一些常用规则
加法规则
T(n)=T1(n) + T2(n) = O(f(n)) + O(g(n)) = O(max(f(n),g(n)))
乘法规则
T(n) = T1(n) * T2(n) = O(f(n)) * O(g(n)) = O(f(n)*g(n))
平均算法时间复杂度
所有输入的示例等概率出现的情况下 算法期望运行的时间 例如元素n在任意一个位置出现的概率相同都为1/n 则平均复杂度：（1+2+3+...+n）*1/n = (1+n)/2
3.举例
简单的单层循环
时间复杂度和T(n)有关 利用加法原则：T(n)=n+1 = O(n)
public static void test1(int n) {
int i = 1;
while (i <= n){
i++;
}
}复制代码2.嵌套循环 T(n) = n + n^2 + 1 = O(n^2)
public static void test1(int n) {
int i = 1;
while (i <= n){
i++;
for(j=1;j<=n;j++){
System.out.println(j);
}
}
}复制代码跳着循环
T(n) = O(log2n) 因为i=i*2执行的次数可以设为x 这2^x > n 则退出循环 执行完 故为log2n
public static void test1(int n) {
int i = 1;
while (i <= n){
i = i*2;
}
}复制代码常见算法时间复杂度大小比较
O(1)<O(log2n)<O(n)<O(nlog2n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)
2.2 空间复杂度
一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))
若算法所需要的空间为常量 则也可称为算法的原地工作
算法的空间复杂度需要关注的是：存储空间的大小和问题规模大小（一般为常数）
其中S(n)=O(n)
若将 int m[n] 改为 int m[n][n]则S(n)=O(n^2)
public static void test1(int n) {
int i=1;
int m[n];
while (i <= n){
i = i*2;
}
}复制代码S(n)=O(n)+O(n^2)+O(1) = O(n^2) 加法规则
public static void test1(int n) {
int i=1;
int s[n];
int m[n][n];
while (i <= n){
i = i*2;
}
}
作者：又菜又想玩的XXX
链接：https://juejin.cn/post/7025862523614134286