Java数据结构“时间复杂度“和“空间复杂度“
1.如果衡量一个算法的好坏?
在Java编程中，时间复杂度和空间复杂度是评估算法性能的两个重要指标。它们帮助我们理解和比较不同算法的效率，尤其是在处理大规模数据时。
2.算法效率 :
算法效率分析分为两种：第⼀种是时间效率，第⼆种是空间效率。时间效率被称为时间复杂度，⽽空 间效率被称作空间复杂度。时间复杂度主要衡量的是⼀个算法的运⾏速度，⽽空间复杂度主要衡量⼀ 个算法所需要的额外空间，在计算机发展的早期，计算机的存储容量很⼩。所以对空间复杂度很是在 乎。但是经过计算机⾏业的迅速发展，计算机的存储容量已经达到了很⾼的程度。所以我们如今已经 不需要再特别关注⼀个算法的空间复杂度
3.时间复杂度
3.1时间复杂度的概念
时间复杂度的定义：在计算机科学中，算法的时间复杂度是⼀个数学函数，它定量描述了该算法的运 ⾏时间。⼀个算法执⾏所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上 跑起来，才能知道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很⿇烦，所以 才有了时间复杂度这个分析⽅式。⼀个算法所花费的时间与其中语句的执⾏次数成正⽐例，算法中的 基本操作的执⾏次数，为算法的时间复杂度。
3.2 ⼤O的渐进表⽰法
实际中我们计算时间复杂度时，我们其实并不⼀定要计算精确的执⾏次数，⽽只需要⼤概执⾏次数， 那么这⾥我们使⽤⼤O的渐进表⽰法。
3.3 推导⼤O阶⽅法
1、⽤常数1取代运⾏时间中的所有加法常数。
2、在修改后的运⾏次数函数中，只保留最⾼阶项。
3、如果最⾼阶项存在且不是1，则去除与这个项⽬相乘的常数。得到的结果就是⼤O阶
4.O(1) - 常数时间复杂度:
算法的执行时间与输入规模无关。例如，访问数组的第一个元素。
int getFirstElement(int[] array) {
return array[0]; // O(1)
}O(log n) 对数时间复杂度: 常见于分治算法，如二分查找。每次操作将问题规模减半。
int binarySearch(int[] array, int target) {
int left = 0, right = array.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (array[mid] == target) return mid;
else if (array[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1; // O(log n)
}O(n) 线性时间复杂度: 算法的执行时间与输入规模成正比。例如，遍历数组。
int sumArray(int[] array) {
int sum = 0;
for (int num : array) sum += num; // O(n)
return sum;
}O(n^2) - 二次时间复杂度: 常见于嵌套循环，如冒泡排序。
void bubbleSort(int[] array) {
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array.length - 1 - i; j++) {
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
} // O(n^2)
}空间复杂度
定义: 空间复杂度描述了算法在运行过程中临时占用的额外存储空间的大小，也用大O符号表示。
O(1) 常数空间复杂度: 算法使用的空间是固定的，不随输入规模变化。
int add(int a, int b) {
return a + b; // O(1)
}O(n) 线性空间复杂度: 使用的空间与输入规模成正比。例如，创建一个与输入数组大小相同的数组
int[] copyArray(int[] array) {
int[] newArray = new int[array.length]; // O(n)
for (int i = 0; i < array.length; i++) newArray[i] = array[i];
return newArray;
}O(n^2) 二次空间复杂度: 常见于需要存储二维数组或矩阵的算法。
int[][] createMatrix(int n) {
int[][] matrix = new int[n][n]; // O(n^2)
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) matrix[i][j] = i * j;
return matrix;
}时间复杂度和空间复杂度是有部分区别的:时间是一去而不复返的,空间是可以反复利用的
重要性
性能优化: 低时间复杂度的算法在处理大规模数据时更高效；低空间复杂度的算法可以减少内存消耗。
资源利用: 影响CPU和内存的使用效率，尤其是在资源受限的环境中。
可扩展性: 决定了算法在数据规模增长时的表现。
用户体验: 更高效的算法可以提高应用程序的响应速度。
理解时间复杂度和空间复杂度是设计和优化算法的基础，帮助开发者在不同的应用场景中选择合适的算法。
原文地址：https://blog.csdn.net/lxsxjsj/article/details/144380234
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！