软设之算法的效率

算法的效率分为时间复杂度和空间复杂度。

空间复杂度是指对一个算法在运行过程中临时占用存储空间大小的度量。一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小。说白了，就是空间换时间。

比如说计算从1+2+3+……+100的和。一个算法是i=(1+100)*100/2。另外一个算法是用for循环。前者只计算了1次，后者需要计算100次，前者更快。

时间复杂度指的是一种算法，以该操作的重复执行次数作为算法的时间度量。

时间复杂度用O表示。

时间复杂度是用渐进时间复杂度计算的，一个算法随着运算次数n增加，影响因素主要是n的次方决定，其他的常数影响很小。

比如单个控制语句，时间复杂度是O(1)

如果程序语句有一层循环，时间复杂度是O(n)

如果有两层嵌套循环，时间复杂度是O(n^2)

如果有a层循环，时间复杂度是O(n^a)

比如说是二叉树二分查找，时间复杂度是O(log(2)n)

比如说是堆排序，时间复杂度就是O(nlog(2)n)

比如说是判断是否包含指定子序列，最长公共子序列，钢管切割问题，动态规划法自顶向下，时间复杂度是O(2^n)