服务器之家

服务器之家 > 正文

Java数据结构--时间和空间复杂度

时间:2021-12-09 10:42     来源/作者:吞吞吐吐大魔王

一、算法效率

算法效率分析分为两种:时间效率和空间效率

时间效率

时间效率被称为时间复杂度,主要时衡量一个算法的运行速度

空间效率

空间效率被称为空间复杂度,主要衡量一个算法所需要的额外空间

二、时间复杂度 

1. 概念

一个算法所花费的时间与其中语句的执行次数成正比,故将算法中的基本操作的执行次数,作为算法的时间复杂度

并且时间复杂度其实还可以分成三种情况:

  • 最坏情况:任意输入规模的最大运行次数
  • 平均情况:任意输入规模的期望运行次数
  • 最好情况:任意输入规模的最小运行次数

而在实际中一般关注的是算法的最坏运行情况

2. 大 O 的渐进表示法

实际在我们计算时间复杂度时,并不一定要计算精确的执行次数,而只需要大概执行次数,故我们使用大 O 的渐进表示法(大 O 符号是用于描述函数渐进行为的数学符号)

使用方法

用常数1取代运行时间中的所有加法常数在修改后的运行次数函数中,只保留最高阶项如果最高阶项存在且不为1,则去除与这个项目相乘的常数

如某个算法的基本操作次数为 F(N) = N^2^ + 2*N + 10,用大 O 的渐进表示法为:O(N)

3. 练习

在这里放入两个递归函数的练习,我们来试着推导其的时间复杂度

练习一:计算阶乘递归 factorial 的时间复杂度

?
1
2
3
long factorial(int N) {
    return N < 2 ? N : factorial(N-1) * N;
}

这题很简单,结果为:O(N)

练习二:计算斐波那契递归 fibonacci 的时间复杂度

?
1
2
3
int fibonacci(int N) {
    return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);
}

这题可以结合画图类似于二叉树去思考,结果为:O(N2)

注意

递归的时间复杂度 = 递归的次数 * 每次递归内容要执行的次数

三、空间复杂度 

1. 概念

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度,它不是计算程序占用了多少 byte 的空间,而是计算变量的个数。(空间复杂度也使用大 O 的渐进表示法)

2. 练习

练习一:计算 bubbleSort 的空间复杂度

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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(1)

练习二:计算 fibonacci 的空间复杂度

?
1
2
3
4
5
6
7
8
9
int[] 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;
}

因为动态开辟了 N 个空间,故结果为:O(N)

练习三:计算阶乘递归 Factorial 的时间复杂度

?
1
2
3
long factorial(int N) {
    return N < 2 ? N : factorial(N-1)*N;
}

因为递归调用了 N 次,开辟了 N 个栈帧,每个栈帧使用了常数个空间,故结果为:O(N)

四、总结

本篇文章就到这里了,希望能够给你带来帮助,也希望您能够多多关注服务器之家的更多内容!

原文链接:https://blog.csdn.net/weixin_51367845/article/details/119944469

相关文章

热门资讯

yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
2021年耽改剧名单 2021要播出的59部耽改剧列表
2021年耽改剧名单 2021要播出的59部耽改剧列表 2021-03-05
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
返回顶部