确定时间频度:
分析代码中每个操作的执行次数,记为T(n),其中n是输入数据规模的大小。
化简时间频度:
去掉时间频度表达式中的常数项、低阶项和最高次项的系数,只保留最高次项。
表示时间复杂度:
使用大O表示法(O-notation)来表示化简后的时间频度,即O(f(n)),其中f(n)是最高次项的表达式。
举个例子,如果有一个算法的时间频度是T(n)= 3n² + 6n + 5,那么化简后得到的时间复杂度是O(n²),因为n²是最高次项。
O(1):常数时间复杂度,例如访问列表中的元素或执行算术运算。
O(n):线性时间复杂度,例如遍历一个列表或求列表的长度。
O(log n):对数时间复杂度,例如二分查找算法。
O(n²):平方时间复杂度,例如嵌套循环的每一层迭代次数都是n。
O(n log n):对数线性时间复杂度,例如快速排序和归并排序算法。
O(2^n):指数时间复杂度,例如穷举法求解某些组合问题。
Python内置函数的时间复杂度示例:
`list.append(value)`:O(1),因为添加元素到列表末尾通常是一个恒定时间操作。
`list.sort()`:O(n log n),因为Python内置的排序算法(Timsort)的平均和最坏情况时间复杂度都是O(n log n)。
请注意,实际运行时间也会受到电脑配置等因素的影响,因此理论上的时间复杂度分析是算法性能评估的重要部分。