java时间复杂度详解,数据结构时间复杂度是什么
00-1010算法效率、时间复杂度和空间复杂度总结
00-1010算法的效率分析分为两种：第一种是时间效率，第二种是空间效率。时间效率叫时间复杂度，空间效率叫空间复杂度。时间复杂度主要衡量一个算法的运行速度，空间复杂度主要衡量一个算法需要的额外空间。在计算机发展的早期，计算机的存储容量非常小。所以我们很在意空间的复杂性(以前是时间换空间)。但是随着计算机行业的飞速发展，计算机的存储容量已经达到了很高的水平。所以现在我们不需要特别关注一个算法的空间复杂度(现在是空间的时候了)。
00-1010时间复杂度的定义：在计算机科学中，算法的时间复杂度是定量描述算法运行时间的函数。理论上，一个算法执行的时间是无法计算的。只有把你的程序放到机器上运行，你才能知道。但是我们需要每一个算法都在电脑上测试吗？可以在电脑上测试，但是很麻烦，于是就有了时间复杂度的分析公式。一个算法花费的时间与语句的执行次数成正比，算法中基本操作的执行次数就是算法的时间复杂度。
其实我们在计算时间复杂度的时候，并不一定要计算精确的执行次数，只需要大概的执行次数就可以了，所以这里用的是大o的递进式表示。
大O符号：用来描述函数渐进行为的数学符号。
高阶方法的推导：
1.用常数1替换运行时的所有加法常数。
2.在操作次数的修正函数中，只保留最高阶项。
3.如果最高阶项存在且不为1，则移除乘以该项的常数。结果就是大O阶。
看一些例子：
//请计算一下func1的基本运算进行了多少次？void func 1(int N){ int count=0；for(int I=0；I N；I){ for(int j=0；j N；j){ count；} } for(int k=0；k ^ 2 * N；k){ count；} int M=10while((M-)0){ count；} system . out . println(count)；}
通过以上可以发现，大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了地显示了执行次数。
此外，一些算法具有最佳、平均和最差的时间复杂度：
最坏情况：任何输入标度的最大运行次数(上限)
平均情况：任何输入规模的预期运行次数。
最佳情况：任何输入规模的最小运行次数(下限)
例如，在长度为n的数组中搜索数据X。
最好的情况：找到一次。
最差情况：发现n次
平均情况：发现N/2次
在实际中，一般情况侧重于算法的最坏情况，所以在数组中搜索数据的时间复杂度为O(N)。
示例2
//计算func2的时间复杂度？void func 2(int N){ int count=0；for(int k=0；k ^ 2 * N；k){ count；} int M=10while((M-)0){ count；} system . out . println(count)；}
示例3
//计算func3的时间复杂度？void func3(int N，int M){ int count=0；for(int k=0；k M；k){ count；} for(int k=0；k N；k){ count；} system . out . println(count)；}
实例4
//计算func4的时间复杂度？void func 4(int N){ int count=0；for(int k=0；k 100k){ count；} system . out . println(count)；}
实例5
//计算bubbleSort的时间复杂度？无效气泡
leSort(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; } }}
例子六
// 计算binarySearch的时间复杂度？int binarySearch(int[] array, int value) { int begin = 0; int end = array.length - 1; while (begin <= end) { int mid = begin + ((end-begin) / 2); if (array[mid] < value) begin = mid + 1; else if (array[mid] > value) end = mid - 1; else return mid; } return -1; }
例子七
// 计算阶乘递归factorial的时间复杂度？long factorial(int N) { return N < 2 ? N : factorial(N-1) * N; }
空间复杂度
空间复杂度是对一个算法在运行过程中 临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少 bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数（额外变量个数）。空间复杂度计算规则基本跟时间复杂度 类似。也使用 大 O 渐进表示法 。
例子一
// 计算bubbleSort的空间复杂度？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; } }}
例子二
// 计算fibonacci的空间复杂度？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; }
例子三
// 计算阶乘递归Factorial的空间复杂度？long factorial(int N) { return N < 2 ? N : factorial(N-1)*N; }
小结
这篇文章讲的都是一些简单的时间复杂度和空间复杂度的计算，如果有什么不正确的地方，欢迎大家指出来。
到此这篇关于Java数据结构通关时间复杂度和空间复杂度的文章就介绍到这了,更多相关Java时间复杂度 内容请搜索盛行IT以前的文章或继续浏览下面的相关文章希望大家以后多多支持盛行IT！
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。