🟡前言
本文是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整数倍)
🟡结语
从下一篇文章起会分享有关算法中排序的知识点以及对应习题