时间复杂度

Posted by 程序亦非猿 on 2015-12-04

时间复杂度

看了时间复杂度的故事做了点摘抄.

线性

如果它处理 N 个元素求和所花的时间是 T,那么它处理 N 2 个元素的和所花的时间就是 T 2。所以随着 N 变大,时间 T 的变大是与 N 呈「线性」关系的。

在时间复杂度中,我们用 O(N) 表示这种「线性」时间复杂度。

对数

对于类似二分法来说,输入的元素个数虽然翻倍,但是程序运行所花的时间却只增加了 1,我们把这种时间复杂度要叫「对数」时间复杂度,用 O(logN) 来表示

其他复杂度

「常数」时间复杂度,例如返回一个有序数组中的最小数,这个数因为始终在第一个位置,所以就不会受到数组大小的影响,无论数组多大,我们都可以在一个固定的时间返回结果。

「线性对数」时间复杂度,即 O(N*logN) ,这个复杂度比较常见,因为常见的高效的排序算法,都是这个时间复杂度,比如 快速排序,堆排序,归并排序等。

资料

时间复杂度的故事