衡量代码运行效率的重要因素之复杂度

复杂度是衡量代码运行效率的重要的度量因素,一般而言,代码执行过程中会消耗计算时间和计算空间,这里我们需要衡量的就是时间复杂度和空间复杂度.

• 复杂度是一个关于输入数据量n的函数,O(n)表示的是复杂度与计算实例的个数n线性相关;O(logn)表示的是复杂度与计算实例的个数n对数相关.
• 复杂度与具体的常系数无关.
• 多项式级的复杂度相加的时候,选择高者作为结果.
• O(1)表示一个特殊复杂度,表示某个任务通过有限可数的资源即可完成,与输入数据量n无关.

经验结论:
1.一个顺序结构的代码,时间复杂度是O(1)
2.二分查找(二分策略),时间复杂度市O(logn)
3.一个简单的for循环,时间复杂度是O(n)
4.两个顺序执行的for循环,时间复杂度O(n) + O(n) = O(2n),其实也是O(n)
5.两个嵌套的for循环,时间复杂度是O(n²)

高效代码要采用尽可能低的时间复杂度和空间复杂度去完成开发.
1.降低时间复杂度的方法有 递归、二分法、排序算法、动态规划等。
2.降低空间复杂度通常需要围绕数据结构进行研究。

降低复杂度的经验结论:

1、暴力破解，在没有任何时间、空间约束下，完成代码任务的开发。
2、无效操作处理，将代码中的无效计算、无效存储剔除，降低时间和空间复杂度。
3、时空转换，设计合理的数据结构，完成时间复杂度向空间复杂度的转移。