如何通过Java算法了解时间复杂度和空间复杂度

这篇文章主要介绍“如何通过Java算法了解时间复杂度和空间复杂度”，在日常操作中，相信很多人在如何通过Java算法了解时间复杂度和空间复杂度问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”如何通过Java算法了解时间复杂度和空间复杂度”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！算法效率分析分为两种：第一种是时间效率，第二种是空间效率。时间效率被称为时间复杂度，而空间效率被称作空间复杂度。 时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度主要衡量一个算法所需要的额外空间。在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。因为现在的内存不像以前那么贵，所以经常听到过牺牲空间来换取时间的说法在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。算法中的基本操作的执行次数，为算法的时间复杂度。从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，
算法中的基本操作的执行次数，为算法的时间复杂度。实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用大O的渐进表示法大O符号（Big O notation）：是用于描述函数渐进行为的数学符号(1)推导大O阶方法代码如下（示例）：所以func方法的执行次数为 1+N2+2*N+1+10我看到func的执行次数，如果当我们的N非常大时，假设N = 100，那么这里的+1和+10是不是可以忽略了，因为1002=10000,在一万面前+1和+10可以说是微乎其微了，所以+1和+10没什么区别。这就用到了前面说了推导大O阶方法，就变成了 1+N2+2*N+1+1再来看在修改后的运行次数函数中，只保留最高阶项。简化后 N2如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶这里我们的最高阶项是2，但前面没有常数所以没必要去除，如果N2前面还有个2就是2N2就要去除2变成 N2
所以使用大O的渐进表示法以后，Func的时间复杂度为 O(N2)通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数。时间复杂度是一个函数，只能大致估一下这个算法的时间复杂度。另外有些算法的时间复杂度存在最好、平均和最坏情况。(1) 最坏情况最坏情况：任意输入规模的最大运行次数(上界) 也就是 O(N)这里的N代表的是问题的规模(2)最好情况任意输入规模的最小运行次数(下界) 也就是 O(1)(3)平均情况任意输入规模的期望运行次数注意：这里的平均情况并不是最好和最坏情况相加的平均值，而是我们期望运行的次数，有时候平均情况可能和最好或者是最坏情况一样。在平常我们所说的时间复杂度一般说的都是算法的最坏情况示例1：1+2*N+1+10 通过推导大O阶方法后:时间复杂度为 O(N)示例2：时间复杂度为：O(M+N)示例3：这里的时间复杂度为 O(1),因为传进来的N并没有使用示例4：这是一个冒泡排序，我们来求一下它的最好最坏和平均情况的时间复杂度最好：O(N)
最坏：O(N2)
平均：O(N)这是一个经过优化后的冒泡排序，最好的情况就是该组数据已经是有序的了，所以只需走一遍就好了，也是是O(N).
而最坏的情况就把数组全部遍历了一遍就是 N2
我们前面说过平均情况就是我么个期望的情况，我们期望的当然就是O(N)我们知道求时间复杂度一般求的都是最坏的情况，二分查找只有当我们找最旁边那两个个数时才是最坏情况，我们就假设我们要找的就是最边边的那个数。所以二分查找的时间复杂度为 O(log2N)递归的时间复杂度 = 递归的次数*每次递归执行的操作的次数示例1：这里的的递归次数为 N 次，这里没有循环，每次执行的是一个三目操作符相当于1次。所以为 N+1次，时间复杂度就是 O(N)。示例2：这是一个递归实现的斐波那契数列斐波那契数列的递归次数其实就是一个等比数列求和，最后的执行次数为 (2n) – 1,通过通过推导大O阶方法最后的时间复杂度为 O(2N)时间复杂度只是一个大概的，当数字足够大时这里缺失的部分并不影响我们时间复杂度的计算。空间复杂度是对一个算法在运行过程中临时(额外)占用存储空间大小的量度
占用存储空间大小的量度 。
空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。
空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法(1) 冒泡排序这个冒泡排序的空间复杂度为 O(1)为什么呢？因为空间复杂度是为了解决一个问题额外申请了其他变量，这里的array数组并不是额外的它是必须的，但这里的 sorted 是额外申请的，它每循环一次就定一次为什么不是O(N)呢？因为每循环一次这个变量是不是不要了呢？所以来来回回就是这一个免费云主机域名变量。(2) 斐波那契数列这里的空间复杂度为 O(N)
这里为了求第1~N的斐波那契数列的代码，为了解决这个问题申请了一个额外的数组的空间，空间大小为 N+1。因为1是常数项，所以这个代码的空间复杂度为 O(N)(3)递归这是一个求阶层的递归，他的空间复杂度为 O(N)
因为递归在递的过程中，每递一次都会都会创建一个临时变量。到此，关于“如何通过Java算法了解时间复杂度和空间复杂度”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注百云主机网站，小编会继续努力为大家带来更多实用的文章！

相关推荐: HTML5新元素属性有哪些

本篇内容介绍了“HTML5新元素属性有哪些”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！ 　　canvas 新元素 　　canvas标签定义图形，比如图表和其他…