时间复杂度和空间复杂度的精炼Java解释

对于一个算法,其时间复杂度和空间复杂度往往是相互影响的,当追求一个较好的时间复杂度时,可能会使空间复杂度的性能变差,即可能导致占用较多的存储空间,这篇文章主要给大家介绍了关于Java时间复杂度、空间复

前言：

所谓复杂度，就是衡量算法的效率。衡量计算效率有两种方法，一种叫时间复杂度，一种叫空复杂度。

一、算法效率

算法效率分析有两种:第一种是时间效率，第二种是空效率。时间效率称为时间复杂度，而空之间的效率称为空之间的复杂度。时间复杂度主要衡量一个算法的运行速度，而空时间复杂度主要衡量一个算法需要额外的空时间。在计算机发展的早期，计算机的存储容量非常小。所以我关心空的复杂度。然而，随着计算机行业的快速发展，计算机的存储容量已经达到了很高的水平。所以现在我们不需要特别关注一个算法的空之间的复杂度。

二、时间复杂度

1.时间复杂度概念

一个算法花费的时间与语句的执行次数成正比，算法中基本操作的执行次数就是算法的时间复杂度。也就是说，当我们得到一个代码，要看这个代码的时间复杂度，主要是看执行语句最多的代码被执行了多少次。

2.大O的渐进表示法

看图:

当n的值变得越来越大时，2N和10的值就可以忽略和忘记了。

其实我们在计算时间复杂度的时候，并不一定要计算精确的执行次数，只需要大概的执行次数就可以了，所以这里用的是大o的递进式表示。

大O符号:用来描述函数渐进行为的数学符号。

1.用常数1替换运行时的所有加法常数。

2.在操作次数的修正函数中，只保留最高阶项。

3.如果最高阶项存在且不为1，则移除乘以该项的常数。结果就是大O阶。

通过以上可以发现，大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了地显示了执行次数。

此外，一些算法具有最佳、平均和最差的时间复杂度:

最坏情况:任何输入标度的最大运行次数(上限)

平均情况:任何输入规模的预期运行次数。

最佳情况:任何输入规模的最小运行次数(下限)

例如，在长度为n的数组中搜索数据X。

最好的情况:找到一次。

最差情况:发现n次

平均情况:发现N/2次

在实际中，一般情况侧重于算法的最坏情况，所以在数组中搜索数据的时间复杂度为O(N)。

计算时间复杂度

示例1:

运算基本执行2N+10次，通过推导大O阶方法，时间复杂度为O(N)。

示例2:

运算基本上执行M+N次，两个未知数M和N，时间复杂度为O(N+M)

示例3:

运算基本执行100次，通过推导大O阶方法，时间复杂度为O(1)。

示例4:计算冒泡排序的时间复杂度

基本操作最好执行N次，最差执行(N*(N-1))/2次。通过推导大O阶方法+时间复杂度一般最差，时间复杂度为O (n 2)

例5:二分搜索法的时间复杂度

基本运算最好执行一次，最差O(logN)次，时间复杂度为o (O(logN) ps:logN在算法分析中表示底数为2，对数为n。有些地方会写成lgN。(建议解释一下logN是如何通过origami search计算出来的)(因为二分搜索法每次剔除一半不合适的值，一次二进制剩余:n/2两次二进制剩余:n/2/2 = n/4)

示例6:计算阶乘递归的时间复杂度

递归的时间复杂度=递归次数*每次递归次数。

通过计算分析，发现基本运算递归N次，时间复杂度为O(N)。

示例7:计算斐波那契递归的时间复杂度

通过计算分析发现，基本运算递归2 N次，时间复杂度为O (2 N)。

规则:

2^0+2^1+2^2+2^3hellip；hellip2^(n-(n-1))

几何级数求和平

A1代表第一项，Q等于2，1 (1-2 N)/-1，相当于2 N+1，所以时间复杂度为O (2 N)

三、空间复杂度

空之间的复杂度是一个算法在运行过程中临时占用存储空大小的度量。空之间的复杂度不是程序占用多少字节的空。因为这个没有太大意义，所以空之间的复杂度算变量个数。空之间复杂度的计算规则与实际复杂度基本相似，同样采用大O递进表示。

例1:计算冒泡排序的空之间的复杂度

使用恒定数量的额外空房间，因此空之间的复杂度是O(1)

例2:计算斐波那契数列空之间的复杂度

动态有n 空，空的复杂度为O(N)。

例3:计算阶乘递归的空之间的复杂度

递归调用n次，打开n个堆栈帧，每个堆栈帧使用常数空。空之间的复杂度为O(N)

总结：

简要介绍了时间复杂度和空之间的复杂度，通过简单的例子加深了对数组的理解。这就是今天的内容。如有疑问，欢迎私信我。我会积极改正文章中的任何问题。也希望你能更快的掌握自己想要的知识。让我们一起加油吧！！！！！

关于Java精化解释的时间复杂度和空之间的复杂度的文章到此为止。关于Java时间复杂度