您好,登录后才能下订单哦!
这篇文章主要介绍“如何通过Java算法了解时间复杂度和空间复杂度”,在日常操作中,相信很多人在如何通过Java算法了解时间复杂度和空间复杂度问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”如何通过Java算法了解时间复杂度和空间复杂度”的疑惑有所帮助!接下来,请跟着小编一起来学习吧!
算法效率分析分为两种:第一种是时间效率,第二种是空间效率。时间效率被称为时间复杂度,而空间效率被称作空间复杂度。 时间复杂度主要衡量的是一个算法的运行速度,而空间复杂度主要衡量一个算法所需要的额外空间。
在计算机发展的早期,计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展,计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。因为现在的内存不像以前那么贵,所以经常听到过牺牲空间来换取时间的说法
在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。
算法中的基本操作的执行次数,为算法的时间复杂度。从理论上说,是不能算出来的,只有你把你的程序放在机器上跑起来,才能知道。但是我们需要每个算法都上机测试吗?是可以都上机测试,但是这很麻烦,所以才有了时间复杂度这个分析方式。
一个算法所花费的时间与其中语句的执行次数成正比例,
算法中的基本操作的执行次数,为算法的时间复杂度。
实际中我们计算时间复杂度时,我们其实并不一定要计算精确的执行次数,而只需要大概执行次数,那么这里我们使用大O的渐进表示法
大O符号(Big O notation):是用于描述函数渐进行为的数学符号
(1)推导大O阶方法
用常数1取代运行时间中的所有加法常数。在修改后的运行次数函数中,只保留最高阶项。如果最高阶项存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大O阶
代码如下(示例):
void func(int N){
int count = 0;//执行1次
for (int i = 0; i < N ; i++) {//执行N*N次
for (int j = 0; j < N ; j++) {
count++;
}
}
for (int k = 0; k < 2 * N ; k++) {//执行2*N次
count++;
}
int M = 10;//执行1次
while ((M--) > 0) {//执行10次
count++;
}
System.out.println(count);
}
所以func方法的执行次数为 1+N2+2*N+1+10
我看到func的执行次数,如果当我们的N非常大时,假设N = 100,那么这里的+1和+10是不是可以忽略了,因为1002=10000,在一万面前+1和+10可以说是微乎其微了,所以+1和+10没什么区别。
这就用到了前面说了推导大O阶方法,
用常数1取代运行时间中的所有加法常数。
就变成了 1+N2+2*N+1+1
再来看
在修改后的运行次数函数中,只保留最高阶项。
简化后 N2
如果最高阶项存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大O阶
这里我们的最高阶项是2,但前面没有常数所以没必要去除,如果N2前面还有个2就是2N2就要去除2变成 N2
所以使用大O的渐进表示法以后,Func的时间复杂度为 O(N2)
通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项,简洁明了的表示出了执行次数。时间复杂度是一个函数,只能大致估一下这个算法的时间复杂度。
另外有些算法的时间复杂度存在最好、平均和最坏情况。
(1) 最坏情况
最坏情况:任意输入规模的最大运行次数(上界) 也就是 O(N)
这里的N代表的是问题的规模
(2)最好情况
任意输入规模的最小运行次数(下界) 也就是 O(1)
(3)平均情况
任意输入规模的期望运行次数
注意:这里的平均情况并不是最好和最坏情况相加的平均值,而是我们期望运行的次数,有时候平均情况可能和最好或者是最坏情况一样。
在平常我们所说的时间复杂度一般说的都是算法的最坏情况
示例1:
void func2(int N) {
int count = 0;//1
for (int k = 0; k < 2 * N ; k++) { //2*N
count++;
}
int M = 10;//1
while ((M--) > 0) {//10
count++;
}
System.out.println(count);
}
1+2*N+1+10 通过推导大O阶方法后:时间复杂度为 O(N)
示例2:
void func3(int N, int M) {
int count = 0;//常数可以不加
for (int k = 0; k < M; k++) {//M
count++;
}
for (int k = 0; k < N ; k++) {//N
count++;
}
System.out.println(count);
}
时间复杂度为:O(M+N)
示例3:
void func4(int N) {
int count = 0;
for (int k = 0; k < 100; k++) {//用常数1取代运行时间中的所有加法常数
count++;
}
System.out.println(count);
}
这里的时间复杂度为 O(1),因为传进来的N并没有使用
示例4:
这是一个冒泡排序,我们来求一下它的最好最坏和平均情况的时间复杂度
void bubbleSort(int[] array) {
for (int end = array.length; end > 0; end--) {
boolean sorted = true;
for (int i = 1; i < end; i++) {
if(array[i - 1] > array[i]){
Swap(array, i - 1, i);
sorted = false;
}
}
if (sorted == true) {
break;
}
}
}
最好:O(N)
最坏:O(N2)
平均:O(N)
这是一个经过优化后的冒泡排序,最好的情况就是该组数据已经是有序的了,所以只需走一遍就好了,也是是O(N).
而最坏的情况就把数组全部遍历了一遍就是 N2
我们前面说过平均情况就是我么个期望的情况,我们期望的当然就是O(N)
我们知道求时间复杂度一般求的都是最坏的情况,二分查找只有当我们找最旁边那两个个数时才是最坏情况,我们就假设我们要找的就是最边边的那个数。
public static int binarySearch(int[] arr,int x){
int left = 0;
int right = arr.length-1;
int mid = 0;//中间下标
while(left <= right){
mid = left+(right-left)/2;
if(arr[mid] > x){
right = mid - 1;
}else if(arr[mid] < x){
left = mid+1;
}else{
return mid;
}
}
return -1;
}
所以二分查找的时间复杂度为 O(log2N)
递归的时间复杂度 = 递归的次数*每次递归执行的操作的次数
示例1:
long factorial(int N) {
return N < 2 ? N : factorial(N-1) * N;
}
这里的的递归次数为 N 次,这里没有循环,每次执行的是一个三目操作符相当于1次。所以为 N+1次,时间复杂度就是 O(N)。
示例2:
这是一个递归实现的斐波那契数列
public static int fib(int n){
if(n==1||n==2){
return 1;
}else{
return fib(n-1)+fib(n-2);
}
}
斐波那契数列的递归次数其实就是一个等比数列求和,最后的执行次数为 (2n) - 1,通过通过推导大O阶方法最后的时间复杂度为 O(2N)
时间复杂度只是一个大概的,当数字足够大时这里缺失的部分并不影响我们时间复杂度的计算。
空间复杂度是对一个算法在运行过程中临时(额外)占用存储空间大小的量度
占用存储空间大小的量度 。
空间复杂度不是程序占用了多少bytes的空间,因为这个也没太大意义,所以空间复杂度算的是变量的个数。
空间复杂度计算规则基本跟实践复杂度类似,也使用大O渐进表示法
(1) 冒泡排序
这个冒泡排序的空间复杂度为 O(1)
为什么呢?因为空间复杂度是为了解决一个问题额外申请了其他变量,这里的array数组并不是额外的它是必须的,但这里的 sorted 是额外申请的,它每循环一次就定一次为什么不是O(N)呢?因为每循环一次这个变量是不是不要了呢?所以来来回回就是这一个变量。
void bubbleSort(int[] array) {
for (int end = array.length; end > 0; end--) {
boolean sorted = true;//额外变量
for (int i = 1; i < end; i++) {
if (array[i - 1] > array[i]) {
Swap(array, i - 1, i);
sorted = false;
}
}
if (sorted == true) {
break;
}
}
}
(2) 斐波那契数列
这里的空间复杂度为 O(N)
这里为了求第1~N的斐波那契数列的代码,为了解决这个问题申请了一个额外的数组的空间,空间大小为 N+1。因为1是常数项,所以这个代码的空间复杂度为 O(N)
public static long[] fibonacci(int n) {
long[] fibArray = new long[n + 1];//额外空间
fibArray[0] = 0;
fibArray[1] = 1;
for (int i = 2; i <= n ; i++) {
fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
}
return fibArray;
}
(3)递归
这是一个求阶层的递归,他的空间复杂度为 O(N)
因为递归在递的过程中,每递一次都会都会创建一个临时变量。
long factorial(int N) {
return N < 2 ? N : factorial(N-1)*N;
}
到此,关于“如何通过Java算法了解时间复杂度和空间复杂度”的学习就结束了,希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习,快去试试吧!若想继续学习更多相关知识,请继续关注亿速云网站,小编会继续努力为大家带来更多实用的文章!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。