复杂度是衡量程序运行效率的度量因素，与具体常系数无关。表示复杂度的公式为O()。例如，某个算法的复杂度为f(n)，表示为O(f(n))。在计算复杂度时，需记住三点：复杂度与具体常系数无关，多项式级复杂度相加选择高者为结果，O(1)表示特殊复杂度。

复杂度是一个关于输入数据量n的函数。复杂度分析用于判断程序解法的优劣。例如，两个解法处理相同任务，一个需要2天，另一个只需半小时，后者明显更适合实际需求。

复杂度的表示方法为O()。复杂度与具体常系数无关。例如，反转列表的复杂度为O(n)，而用for循环创建等长列表并倒序放入另一个列表的过程，复杂度同样为O(n)。

多项式级复杂度相加时，选择变化率更大的为结果。如O(n²)+O(n)复杂度，在n足够大时，n²的变化率远大于n，因此复杂度简化为O(n²)。

O(1)表示特殊复杂度，与输入数据量无关。例如，反转列表的第二种解法开辟了一个新的变量tmp，其空间复杂度为O(1)。

理解复杂度并能进行简单的分析对于开发人员而言很有必要。例如，分析如下代码的复杂度，从最内层看，为O(n)；中间层嵌套循环，复杂度变为O(n²)；最外层循环使最终复杂度为O(n³)。

即使测试工程师对复杂度要求不高，理解复杂度和进行简单分析仍然具有重要价值。

本文地址： http://www.goggeous.com/j/1/1179886

文章来源：天狐定制

版权声明：除非特别标注，否则均为本站原创文章，转载时请以链接形式注明文章出处。