全面解读其常见算法常见算法的时间空间复杂度( 二 ) _生活知识

对于「条件判断语句」，总的时间复杂度等于其中时间复杂度最大的路径的时间复杂度。当n >= 0分支的复杂度最大，即总复杂度为O(n^2)
deffun(n):ifn>=0:#第1部分复杂度为O(n^2)count=0foriinrange(n):forjinrange(n):count+=1else:#第2部分复杂度为O(n)foriinrange(n):count+=2returncount「
如何计算空间复杂度我们在写代码时，完全可以用空间来换取时间，比如字典树，哈希等都是这个原理。算法在运行过程中临时占用的存储空间随算法的不同而异，有的算法只需要占用少量的临时工作单元，而且「不随问题规模的大小而改变」，我们称这种算法是“就地”进行的，是节省存储的算法，空间复杂度为O(1)，注意这并不是说仅仅定义一个临时变量；有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元，例如将快速排序和归并排序算法就属于这种情况。
如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1) 。如下代码中的 i、j、t 所分配的空间都不随着处理数据量变化，因此它的空间复杂度为O(1) 。
i=0j=1t=i+j这段代码中，第一行定义了一个列表，这个列表的长度随着n的规模不同，会不一样，这里空间复杂度为O(n) 。
deffun(n):temp=[]foriinrange(n):temp.append(i)对于一个算法，其时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时，可能会使空间复杂度的性能变差，即可能导致占用较多的存储空间；反之，追求一个较好的空间复杂度时，可能会使时间复杂度的性能变差，即可能导致占用较长的运行时间。另外，算法的所有性能之间都存在着或多或少的相互影响。因此，当设计一个算法(特别是大型算法)时，要综合考虑算法的各项性能，算法的使用频率，算法处理的数据量的大小，算法描述语言的特性，算法运行的机器系统环境等各方面因素，才能够设计出比较好的算法。
常见数据结构与算法的时间、空间复杂度总结数据结构堆图排序算法搜索算法Master Theorem解决递归复杂度求解Master Theorem提供了用大O符号表示许多由分治法得到的递推关系式的方法。其基本形式如下，
其中表示问题规模，为递推的子问题数量，为每个子问题的规模（假设每个子问题的规模基本一样），为递推以外进行的计算工作。
具体怎么用呢，当我们根据分析，得到算法T(n)的表达式后，则根据以下步骤确定最终的时间复杂度：