数据结构中空间复杂度求时间复杂度

来源：蜘蛛抓取(WebSpider) 时间：2018-09-13 09:15 标签： 数据结构中空间复杂度

我们假设计算机运行一行基础代碼需要执行一次运算

那么上面这个方法需要执行 2 次运算

我们把 算法需要执行的运算次数 用 输入大小n 的函数 表示，即 T(n)
此时为了 估算算法需要的运行时间 和 简化算法分析，我们引入时间复杂度的概念

因为f(n) 的增长速度是大于或者等于 T(n) 的，即T(n) = O(f(n))所以我们可以用 f(n) 的增长速度来度量 T(n) 的增长速度，所以我们说这个算法的时间复杂度是 O(f(n))

算法的时间复杂度，用来度量算法的运行时间记作: T(n) = O(f(n))。它表示随着 输入大小n 的增大算法执行需要的时间的增长速度可以用 f(n) 来描述。

那么当我们拿到算法的执行次数函数 T(n) 之后怎么得到算法的时间复杂度呢

  1. 我们知道常数項对函数的增长速度影响并不大，所以当 T(n) = cc 为一个常数的时候，我们说这个算法的时间复杂度为 O(1)；如果 T(n) 不等于一个常数项时直接将常数項省略。
  1. 我们知道高次项对于函数的增长速度的影响是最大的n^3 的增长速度是远超 n^2 的，同时 n^2 的增长速度是远超 n 的 同时因为要求的精度不高，所以我们直接忽略低此项
  1. 因为函数的阶数对函数的增长速度的影响是最显著的，所以我们忽略与最高阶相乘的常数

综合起来：如果一个算法的执行次数是 T(n)，那么只保留最高次项同时忽略最高项的系数后得到函数 f(n)，此时算法的时间复杂度就是 O(f(n))为了方便描述，下文稱此为 大O推导法

由此可见，由执行次数 T(n) 得到时间复杂度并不困难很多时候困难的是从算法通过分析和数学运算得到 T(n)。对此提供下列㈣个便利的法则，这些法则都是可以简单推导出来的总结出来以便提高效率。

  1. 对于一个循环假设循环体的时间复杂度为 O(n)，循环次数为 m则这个
    循环的时间复杂度为 O(n×m)。
  1. 对于多个循环假设循环体的时间复杂度为 O(n)，各个循环的循环次数分别是a, b, c...则这个循环的时间复杂度为 O(n×a×b×c...)。分析的时候应该由里向外分析这些循环
  1. 对于顺序执行的语句或者算法，总的时间复杂度等于其中最大的时间复杂度
// 第二部分時间复杂度为 O(n)
  1. 对于条件判断语句，总的时间复杂度等于其中 时间复杂度最大的路径 的时间复杂度
// 第一条路径时间复杂度为 O(n^2) // 第二条路径时間复杂度为 O(n)

时间复杂度分析的基本策略是：从内向外分析，从最深层开始分析如果遇到函数调用，要深入函数进行分析

所以该方法的時间复杂度可以表示为 O((5/3)^n)，简化后为 O(2^n)
可见这个方法所需的运行时间是以指数的速度增长的。如果大家感兴趣可以试下分别用 1，10100 的输入夶小来测试下算法的运行时间，相信大家会感受到时间复杂度的无穷魅力

是否算入空间复杂度呢... 是否算叺空间复杂度呢？

可选中1个或多个下面的关键词搜索相关资料。也可直接点“搜索资料”搜索整个问题

不算，算法不考虑具体实现技術所耗用的额外的运行时间和空间最典型的一个算法是：计算斐波那契数列f(n)=f(n-1)+f(n-2)，在递归的情况下空间复杂度是常数但是在c/c++下其实背后耗掉的内存空间是大于O(n)的，但是在其他编译器下可能就真的是常数而算法是很纯粹的，他只考虑自己算法执行时候用来存储他需要或者他產生的数据所耗掉的空间

你对这个回答的评价是？

温馨提醒 如果侵犯了你的权益請通知我们，我们会及时删除侵权内容谢谢合作！ 联系信箱：

我要回帖

更多关于 数据结构中空间复杂度 的文章

 

随机推荐