如何简单理解集合框架和利用时空复杂度?

简介: 如何简单理解集合框架和利用时空复杂度?

什么是集合框架

Java 集合框架 Java Collection Framework ,又被称为容器 container ,是定义在 java.util 包下的一组接口 interfaces和其实现类 classes 。其主要表现为将多个元素 element 置于一个单元中,用于对这些元素进行快速、便捷的存储 store 、检索 retrieve 、管理 manipulate ,即平时我们俗称的增删查改CRUD。

例如,一副扑克牌(一组牌的集合)、一个邮箱(一组邮件的集合)、一个通讯录(一组姓名和电话的映射关系)等等。

什么是数据结构?

数据结构(Data Structure)是计算机存储、组织数据的方式,指相互之间存在一种或多种特定关系的数据元素的集合。

什么是算法?

算法(Algorithm):就是定义良好的计算过程,他取一个或一组的值为输入,并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤,用来将输入数据转化成输出结果。

如何衡量一个算法的好坏?

说到衡量算法的好坏就必须要提一下算法效率。算法效率分析分为两种:第一种是时间效率,第二种是空间效率。时间效率被称为时间复杂度,而空间效率被称作空间复杂度。 时间复杂度主要衡量的是一个算法的运行速度,而空间复杂度主要衡量一个算法所需要的额外空间,

在计算机发展的早期,计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展,计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。当然啦,算法好坏不仅仅与算法效率有关,还与是否美观,简洁等有关联。

时间复杂度定义:

在计算机科学中,算法的时间复杂度是一个数学函数,它定量描述了该算法的运行时间。一个算法执行所耗费的时间,从理论上说,是不能算出来的,只有你把你的程序放在机器上跑起来,才能知道。但是我们需要每个算法都上机测试吗?是可以都上机测试,但是这很麻烦,所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例,算法中的基本操作的执行次数,为算法的时间复杂度。

实际中我们计算时间复杂度时,我们其实并不一定要计算精确的执行次数,而只需要大概执行次数,那么这里我们使用大O的渐进表示法

大O的渐进表示法

推导大O阶方法

1、用常数1取代运行时间中的所有加法常数

2、在修改后的运行次数函数中,只保留最高阶项

3、如果最高阶项存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大O阶

其中有几个注意的点:

(1)最坏情况:任意输入规模的最大运行次数(上界)

(2)平均情况:任意输入规模的期望运行次数

(3)最好情况:任意输入规模的最小运行次数(下界)

一般我们所说的时间复杂度是最坏的情况(因为当最坏的情况下的时间复杂度达到了比较小的时候该算法的时间复杂度比较可靠)

例如:

1. void fun(int n) {
2. int i=l;
3. while(i<=n)
4.     i=i*2;
5. }

其时间复杂度为O(logn)。

1. void func3(int N, int M) {
2. int count = 0;
3. for (int k = 0; k < M; k++) {
4. count++;
5. } 
6. for (int k = 0; k < N ; k++) {
7. count++;
8. } 
9. System.out.println(count);
10. }

其时间复杂度为O(M+N)。(因为M和N都是未知的)

1. void func4(int N) {
2. int count = 0;
3. for (int k = 0; k < 100; k++) {
4. count++;
5. } 
6. System.out.println(count);
7. }

其时间复杂度为O(1)。(注意循环表达式中为常数)

1. void bubbleSort(int[] array) {
2. for (int end = array.length; end > 0; end--) {
3. boolean sorted = true;
4. for (int i = 1; i < end; i++) {
5. if (array[i - 1] > array[i]) {
6.                     Swap(array, i - 1, i);
7.                     sorted = false;
8.                 }
9.             }
10. if
11.             (sorted == true) {
12. break;
13.             }
14.         }
15.     }

其时间复杂度为O(n^2)。

1. int binarySearch(int[] array, int value) {
2. int begin = 0;
3. int end = array.length - 1;
4. while (begin <= end) {
5. int mid = begin + ((end-begin) / 2);
6. if (array[mid] < value)
7.                 begin = mid + 1;
8. else if (array[mid] > value)
9.                 end = mid - 1;
10. else
11. return mid;
12.         } 
13. return -1;
14.     }

二分查找:

设查找了x次,所以2^x=n,即x为以2为底n的对数。所以其时间复杂度为O()。

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

故N的时候是执行N次,也就是时间复杂度为O(N)。

所以递归的时间复杂度=递归的次数*每次递归执行的次数

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

这个稍微有一点点难度!需要进一步画图了解。

所以其时间复杂度为O(2^N)。

再次告诉我们算时间复杂度的时候不能只看代码,要了解到它的思想,画图来解决。

空间复杂度定义:

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少bytes的空间,因为这个也没太大意义,所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似,也使用大O渐进表示法。

1. void bubbleSort(int[] array) {
2. for (int end = array.length; end > 0; end--) {
3. boolean sorted = true;
4. for (int i = 1; i < end; i++) {
5. if (array[i - 1] > array[i]) {
6.                     Swap(array, i - 1, i);
7.                     sorted = false;
8.                 }
9.             }
10. if
11.             (sorted == true) {
12. break;
13.             }
14.         }
15.     }

使用了常数个额外空间,所以空间复杂度为 O(1)。

1. int[] fibonacci(int n) {
2. long[] fibArray = new long[n + 1];
3.     fibArray[0] = 0;
4.     fibArray[1] = 1;
5. for (int i = 2; i <= n; i++) {
6.         fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
7.     }
8. return fibArray;
9. }

动态开辟了N个空间,空间复杂度为 O(N)。

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

递归调用了N次,开辟了N个栈帧,每个栈帧使用了常数个空间。空间复杂度为O(N)。(递归过程会压栈

 

目录
打赏
0
0
0
0
2
分享
相关文章
从“笨重大象”到“敏捷火花”:Hadoop与Spark的大数据技术进化之路
从“笨重大象”到“敏捷火花”:Hadoop与Spark的大数据技术进化之路
237 79
【前端web入门第四天】02 CSS三大特性+背景图
本文详细介绍了CSS的三大特性:继承性、层叠性和优先级,并深入讲解了背景图的相关属性,包括背景属性、背景图的平铺方式、位置设定、缩放、固定以及复合属性。其中,继承性指子元素自动继承父元素的文字控制属性;层叠性指相同属性后定义覆盖前定义,不同属性可叠加;优先级涉及选择器权重,包括行内样式、ID选择器等。背景图部分则通过具体示例展示了如何设置背景图像的位置、大小及固定方式等。
365 91
FredNormer: 非平稳时间序列预测的频域正则化方法
FredNormer是一种创新的频域正则化方法,旨在提高时间序列预测模型处理非平稳数据的能力。现有正则化技术虽在分布偏移上有所成效,但在频域动态模式捕捉方面存在不足。FredNormer通过自适应增强关键频率分量的权重,解决了这一问题,并设计了即插即用模块,便于集成到各类预测模型中。实验表明,FredNormer在多个公共数据集上显著提升了预测精度,特别是在复杂频率特征的数据集上效果显著。此外,其计算效率也优于现有方法。该方法为非平稳时间序列预测提供了有力工具。
217 3
FredNormer: 非平稳时间序列预测的频域正则化方法
PolarDB MySQL 版 Serverless评测
对PolarDB的Serverless能力从多维度进行测评
61385 41
PolarDB MySQL 版 Serverless评测
数据分享|电信行业客户流失预测:KNN、朴素贝叶斯、逻辑回归、LDA/QDA、随机森林、支持向量机、CART、神经网络
数据分享|电信行业客户流失预测:KNN、朴素贝叶斯、逻辑回归、LDA/QDA、随机森林、支持向量机、CART、神经网络
云擎技术:通信网络单元定级备案指南
简介: 通信网络单元定级备案是指相关基础电信企业、增值电信企业要对本单位管理、运行的公用通信网和互联网及其各类信息系统进行单元划分,按照《通信网络安全防护管理办法》(工业和信息化部令第11号)的规定开展定级工作,并在工业和信息化部“通信网络安全防护管理系统”报送各单元的定级信息。
369 2
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问