锐客网

  1. 首页 > 睿知 > >

全面解读其常见算法 常见算法的时间空间复杂度

睿知生活知识

前言一般来说，解决问题的方法不止一种 。我们需要学习如何比较不同算法的性能，并选择最佳算法来解决特定的问题 。一个算法的好坏，我们可以从时间和空间两个维度去衡量 。并且，一般分为两个阶段，一是算法完成前的理论分析，二是算法完成后实际分析 。

  • 「理论分析」：这种算法的效率分析是通过假设所有其他因素，如处理器的速度等是恒定的，对算法的实现没有影响 。
  • 「实际分析」：当算法实现后，我们需要考虑算法采用编程语言，然后在特定计算机上执行该算法 ， 其消耗的时间与计算机的硬件水平相关 。在此分析中 ， 我们要收集实际的统计数据，如运行时间和所需空间 。
本篇文章要讨论的主要是算法的理论分析，从常见的时间、空间复杂度入手，介绍各种时间、空间复杂度的特点，并总结一些通用数据结构、排序算法、搜索算法相关操作的时间和空间复杂度 。最后，针对递归操作，使用Master Theorem来分析其复杂度 。
时间、空间复杂度简介时间复杂度时间复杂度是指执行这个算法所需要的计算工作量 ， 其复杂度反映了程序执行时间「随输入规模增长而增长的量级」 ， 在很大程度上能很好地反映出算法的优劣与否 。一个算法花费的时间与算法中语句的「执行次数成正比」，执行次数越多 ， 花费的时间就越多 。一个算法中的执行次数称为语句频度或时间频度 ， 记为T(n)，其中n称为问题的规模，当n不断变化时 ， 它所呈现出来的规律 ， 我们称之为时间复杂度 。比如：与，虽然算法的时间频度不一样 ， 但他们的时间复杂度却是一样的，「时间复杂度只关注最高数量级，且与之系数也没有关系」 。通常一个算法由控制结构（顺序，分支，循环三种）和原操作（固有数据类型的操作）构成，而算法时间取决于两者的综合效率 。
空间复杂度空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度，所谓的临时占用存储空间指的就是代码中「辅助变量所占用的空间」，它包括为参数表中「形参变量」分配的存储空间和为在函数体中定义的「局部变量」分配的存储空间两个部分 。我们用 S(n)=O(f(n))来定义，其中n为问题的规模(或大小) 。通常来说，只要算法不涉及到动态分配的空间，以及递归、栈所需的空间，空间复杂度通常为0(1) 。一个一维数组a[n]，空间复杂度O(n)，二维数组为O(n^2) 。
大O表示法大O符号是由德国数论学家保罗·巴赫曼（Paul Bachmann）在其1892年的著作《解析数论》（Analytische Zahlentheorie）首先引入的 。算法的复杂度通常用大O符号表述，定义为T(n) = O(f(n)) 。称函数T(n)以f(n)为界或者称T(n)受限于f(n) 。如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n) 。T(n)称为这一算法的“时间复杂度” 。当输入量n逐渐加大时，时间复杂度的极限情形称为算法的“渐近时间复杂度” 。空间复杂度同理 。举个例子 ， 令， 。
时间、空间复杂度计算方法【全面解读其常见算法 常见算法的时间空间复杂度】如图展示了几种常见的复杂度形式：非常糟糕的复杂度有O(n!)，O(2^n)，O(n^2)；比较糟糕的有O(nlog n)，可以接受的有O(n) ， 还不错的有O(n)，非常好的有O(logn)和O(1) 。
如何计算时间复杂度如果算法执行所需要的临时空间不随着某个变量n的大小而变化 ， 即此算法空间复杂度为一个常量，可表示为O(1) ， 如
a=1b=2c=a+bb+=a「一个循环」，算法需要执行的运算次数用输入大小n的函数表示 ， 即 T(n)。下面这个函数，语句频度T(n) = 2 + 2*n + 1，那么时间复杂度为O(2*n + 3) = O(n)，因为时间复杂度只关注最高数量级，且与之系数也没有关系 。
deffun(n):count1=0count2=0foriinrange(n):count1+=1count2+=2returncount对于「多个循环」 ， 假设循环体的时间复杂度为O(n)，各个循环的循环次数分别是a, b, c…，则这个循环的时间复杂度为 O(n×a×b×c…) 。分析的时候应该由里向外分析这些循环 。比如下面这个函数，复杂度为O(n*n*1) = O(n^2)
deffun(n):count=0foriinrange(n):forjinrange(n):count+=1returncount对于「顺序执行的语句」或者算法，总的时间复杂度等于其中最大的时间复杂度 。比如下面这个函数，第1部分复杂度为O(n^2)，第2部分复杂度为O(n)，总复杂度为max(O(n^2), O(n)) = O(n^2)
deffun(n):#第1部分复杂度为O(n^2)count=0foriinrange(n):forjinrange(n):count+=1#第2部分复杂度为O(n)foriinrange(n):count+=2returncount

推荐阅读


上一篇：吴起“杀妻求将”的典故，吴起杀妻是真实的吗？

下一篇：人不多的看海好地方求推荐