kkilyy的博客

原创 时间复杂度

1 时间复杂度 常数操作 和数据量无关，是一个固定时间的操作。 数组取值，就是常数操作，和具体数组多大没关系，只需数组下标通过偏移量就可以访问。 链表取第i个的值，就不是常数操作，需要遍历，和链表数据量多少有关。 加减乘除位运算都是常数操作 选择排序 遍历0到n-1中最小的数放到0位置 遍历1到n-1中最小的数放到1位置 … 遍历n-2到n-1中最小的数放到n-2位置 每次遍历的常数操作都一样，例如第一次遍历的常数操作如下 1.取数组0到n-1个数的值，n次常数操作 2.比较0和后面每一个数的值，比较n次也