简介
在日常的开发过程中经常会用到算法，一些看似无关紧要的编程语句往往和程序的执行效率有着莫大的关联，比如：一个 For 循环、一个简单的加减乘除也有很多优化的空间。关于算法执行的效率问题，主要有两个重要的评定指标，分别是时间复杂度、空间复杂度。本文将主要围绕这两个评定指标的概述、如何计算时间复杂度和空间复杂度以及在 Java 语言中的经典算法的复杂度计算。
什么是时间复杂度？
在日常的编程开发中，时间复杂度又称之为时间复杂性，可以用来衡量程序的执行时间效率。一般情况下，一个程序的执行时间是无法通过理论进行计算出来的，所谓的时间复杂度只是大概衡量一个算法或是语句的执行效率，从而对比筛选出比较优秀的程序执行逻辑。通常通过设定一个操作单元来进行理论上时间复杂度的计算，比如：一个简单的打印语句 system.out.println("执行一行代码"); 在时间复杂度的计算中可以看做是一个操作单元，然后通过计算程序执行的外围循环次数等等，从而计算出此代码块的时间复杂度。
时间复杂度的常见类别？
简介
通常，时间复杂度可以分为六种，分别是 O(1)、O(m + n)、O(n ^2)、O(log...n)、O(2 ^ n)、O(n !)，其中 O() 代表的就是一个计算函数，而主要的时间复杂度计算结果主要取决于 O() 函数中的参数大小，进而通过 Tn()= O(参数) 的形式来进行判断，因为假定 Tn() 和 O() 的关系是成线性增长的。所以，时间复杂度的结果主要还是取决于 O() 的参数的大小决定的。一般情况下，一个算法的执行时间是和一个操作单元的执行次数成正比的、操作单元执行的次数越多，则代码块所需要的时间就越多。
类别
常数时间 O(1)
时间复杂度的常数时间类型是指执行操作单元的次数是常数，比如下面的代码块执行次数是一次，可以用 O(1) 来表示其理论程度上的时间复杂度。
public static void main(String[] args) {
double m = 100.23d;
int n = 100;
System.out.println(String.format("m * n = %s", (m * n)));
}
线性时间 O(m + n)
当 O(m + n) 函数内的参数 m + n 为不定次数的参数时，可以使用此种方式的线性方式进行时间复杂度的计算。下面举一个例子将 m 和 n 作为不定长的参数进行传递然后做不同次数的循环，可以根据 O(m + n) 计算出时间复杂度。
public static void main(String[] args) {
call(2, 3);
}
public static void call(int m,int n) {
int sum1 = 0;
do {
sum1++;
} while (sum1 < m);
int sum2 = 0;
do {
sum2++;
} while (sum2 < n);
System.out.println(String.format("cycle is %s", sum1 + sum2));
}
通过执行不定长的参数值，从而计算出总共的循环次数。比如上述中的 m 和 n 的值分别是 2 和 3，套用此种计算方式就是 O(2 + 3)，计算出理论上的时间复杂度。
平方数时间 O(n ^2)
public static void main(String[] args) {
mub(5);
}
public static void mub(int n) {
int m = 0;
do {
System.out.println("执行操作单元");
m++;
} while (m < (n * n));
System.out.println(String.format("cycle is %s", m));
}
如上述，和 O(m + n) 的计算方式都可以理解为是不定次数的执行操作单元，上述执行 5 的平方次就是执行了 25 次操作单元，因此，时间复杂度也就可以表示为 O(5 * 5)。
对数时间 O(log...n)
public static void main(String[] args) {
logn(1000, 10);
}
public static void logn(double val,double base) {
double res = LogAriUtil.log(val, base);
int i = 0;
do {
i++;
} while (i < res);
System.out.println(String.format("i = %s", i));
}
public static class LogAriUtil{
static double log(double val,double base) {
return Math.log(val)/Math.log(base);
}
}
上述示例中使用 Java 中定义的对数方法计算出自定义底数的对数值之后，再进行计算循环次数，从而得出理论的时间复杂度 O(3) 函数值。
指数数时间 O(2 ^ n)
public static void main(String[] args) {
ins2(10);
}
public static void ins2(int n){
int num = 2;
BigInteger bigInteger = BigInteger.valueOf(num);
int ns = bigInteger.pow(n).intValue();
System.out.println(String.format("cycle is %s", ns));
int i = 0;
do {
System.out.println("执行操作单元");
i++;
} while (i < ns);
System.out.println(String.format("i = %s", i));
}
上述循环次数总共执行了 2 的 10 次方，也就是 1024 次，通过在我们的操作单元中加入以上算法也可以计算出理论的时间复杂度。
网友评论