算法效率量化——时间复杂度

我们通常使用“时间按复杂度”来表示算法的快慢。

时间复杂度常使用O和n表示，如O(n), O(n^2)等。

标记算法的复杂度是一般不考虑n的系数，比如O(n)和O(2n)是等价的。

只考虑算式中随n增长较快的项，比如O(n^2+n)等价于O(n^2).

因为计算时间复杂度时只统计n较大的情形。

——————————————

一个例子：

从n个随机数字中查找某个特定的数，需要从第一个开始查找到最后一个，最好的情况下第一个就是，最坏的情况要第n个才能找到。所以时间复杂度就是n/2,因为不关心系数，所以写作O(n).