🟡前言
本文是21天学习挑战赛的第一天，会有一个系列的文章重新梳理算法，本文主要是描述时间复杂度和空间复杂度
活动地址：CSDN21天学习挑战赛
🟡时间复杂度
1️⃣实例说明
public class test { public static void main(String[] args) { int i = 1 , sum = 0; for(i = 0 ; i <= 100 ; i += 1){ sum = sum +i; } System.out.println("和是："+sum); } }
public class 运用for语句求和 { public static void main(String[] args) { int sum = 0; int n = 100; sum = (n+1)*n/2; System.out.println("和是：" + sum); } }
上面两个程序的执行时间不同；第一个程序需要执行100次累加语句，而第二个程序只需要执行三次运算，这就牵涉到时间复杂度
2️⃣时间复杂度分析
如上图所示，可得出结论：算法函数中n最高次幂越小，算法效率越高
在比较算法随着输入规模的增长量时，规则如下
- 算法函数中的常数可以忽略
- 算法函数中最高次幂的常数因子可以忽略
- 算法函数中最高次幂越小，算法效率越高
3️⃣算法时间复杂度计法
（1）大O记法
大O记法的规则如下：
- 用1取代运行时间中所有的加法常数
- 修改后的运行次数中，只保留高阶项
- 若高阶项存在且系数不为1，则去除系数
下面是一些实例
public static void main(String[] args){ int sum =0;//执行1次 int n = 100;//执行1次 sum = (n+1)*n/2//执行1次 }
这个程序执行了 3 次，根据规则记为O(1)
public class test { public static void main(String[] args) { int sum = 0; int n = 100;//执行1次 for(i = 0 ; i <= n ; i += 1){ sum = sum +i;//执行n次 } System.out.println("和是："+sum); } }
这个程序执行了 n+1 次，记为 O(n)
public class test { public static void main(String[] args) { int sum = 0;//执行1次 int n = 100;//执行1次 for(i = 0 ; i <= n ; i += 1){ for(j = 1 ; j <=n ; j++){ sum = sum +i;//执行n^2次 } } System.out.println("和是："+sum); } }
这个程序执行了 n^2+1 次，记为 O(n^2)
（2）常见大O阶
- 线性阶
非嵌套语句涉及；随输入规模扩大，计数次呈直线增长
public static void main(String[] args) { int i = 1 , sum = 0; for(i = 0 ; i <= 100 ; i += 1){ sum = sum +i; } System.out.println("和是："+sum); }
- 平方阶
一般嵌套语句涉及
public static void main(String[] args) { int sum = 0;//执行1次 int n = 100;//执行1次 for(i = 0 ; i <= n ; i += 1){ for(j = 1 ; j <=n ; j++){ sum = sum +i;//执行n^2次 } } System.out.println("和是："+sum); }
- 立方阶
一般三层嵌套循环涉及
public static void main(String[] args) { int sum = 0;//执行1次 int x = 100;//执行1次 for(int i = 1 ; i <= n ; i++){ for(int j = i ; j <=n ; j++){ for(int j =i; j <=n; j++){ x++ } } } System.out.println("和是："+sum); }
- 对数阶
int i = 1, n = 100; while(i<n){ i = i*2 }
- 常数阶
public static void main(String[] args) { int n = 100; int i = n+2; System.out.println(i); }
时间复杂度总结如下
（3）方法调用时间复杂度
只要将方法体内语句代替方法名，即可用上述方法求出时间复杂度
public class Test4 { public static void main(String[] args) { int n = 100; show(n);//执行n次 for(int i = 0; i < n; i++){ show(i);//执行n次 } for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ System.out.println(j);//执行n^2次 } } } private static void show(int i) { for (int j = 0; j < i; j ++){ System.out.println(i);//执行n次 } } }
总共执行：n + n * n + n^2 = 2n ^2 + n 次
所以时间复杂度为：O(n^2)
（4）最坏情况
最坏情况指将程序运行到最后一种情况才是期望的目标，在考虑时间复杂度时要考虑最坏情况
🟡空间复杂度
1️⃣Java中常见内存占用
| 数据类型 | 占用字节数 |
| byte | 1 |
| short | 2 |
| int | 4 |
| long | 8 |
| float | 4 |
| double | 8 |
| boolean | 1 |
| char | 2 |
2️⃣创建对象内存占用
- 计算机一次访问一个字节
- 每个对象自身开销16字节，用来保存对象头信息
- 一个引用（机器地址）需要8字节
- 内存若不够8字节（或其倍数），自动填充为8字节（或其倍数）
- 一个原始数据类型的数组需要24字节的头信息
（16字节自己对象开销＋4字节保存长度+4字节填充为8整数倍）
🟡结语
从下一篇文章起会分享有关算法中排序的知识点以及对应习题
