选择排序
数组取数时间复杂度是常数
int a= arr[i]
从数组中获取第i位置的数即获取某个偏移量或距离的数 时间复杂度是一个常数
数组在内存中的地址空间是连续的 所以通过偏移量就可以获取到指定位置上的值
集合取数时间复杂度不是常数，和数据量有关
int b = list.get(i)
从list集合中获取某一个位置的值 时间复杂度不是一个常数 因为和集合中的数据量有关
集合中的数据越多 耗时越长
list集合中的元素在内存中的地址不是连续的
先找第一个元素 再找第二个元素 再找第三个元素 ，元素越多，耗时越长
选择排序的时间复杂度
第一次排序是 从0到N-1个数中找最小的值放在第一位 确定了一个最小值
第二次排序是 从1到N-1个数中找最小的值放在第二位 确定了次次小的值
第三次排序是 从2到N-1个数中找最小的值放在第三位 确定了第三小的值
第四次排序是 从3到N-1个数中找最小的值放在第四位 确定了第四小的值
要计算该过程的时间复杂度需要先看下有多少个常数操作
- 每次排序都需要遍历一下
第一次排序遍历数组中所有的值即N次 第二次排序遍历N-1次 第三次排序遍历N-2次 第四次排序遍历N-3次 - 每次遍历都需要比较一下
第一次排序比较了N-1次姑且认为N次 第二次排序比较了N-1次 第三次排序比较了N-2次 第四次排序比较了N-3次 - 把最小值找到并且放到第0下标的位置上
每一次排序都需要1次这样的操作
一共做了这么多次常数操作
因为求等差数列一定有N^2 一定有N项
所以可以写成 a N^2+b N+c
这个就是常数数量的表达式
而时间表达式就是在常数数量级的表达式中不要低级项 只要最高阶级的项 而且忽略掉高级项的系数 所剩下的
所以时间复杂度是O(N^2)的算法
小结
- 当两个时间复杂度不同的算法在评估好坏的时候 时间复杂度越小越好 比如O(N) 比 O(N^2)好
- 同样的时间复杂度比如都是O(N)就要看常数项了
虽然可以估算常数操作发生的具体数量 但每一个常数操作虽然是固定时间 但每个时间是不一样的
比如一个常数项是10 常数操作是乘法 另一个常数项是100 常数操作是位运算 此时没发估计 只能实际测试得出每个常数操作的具体时间
这两个算法 每个算法的常数操作执行O(N)次 每次都进行三个常数次操作 所以这2个算法的时间复杂度都是O(N)的 通过理论比较不出只能实际跑一下
额外空间复杂度
只需要有限几个变量就可以完成算法流程的话 就是额外空间复杂度O(1)
若必须开辟一个额外数组 这个额外数据和原来数组等规模的时候 额外的空间复杂度就是O(N)了
选择排序代码
在i到N-1范围选一个最小值 并且把最小值放到i位置上去
只用到了几个变量 i,j,minindex(每次都会释放)
所以额外空间复杂度是O(1)
冒泡排序
初始数据 3，2，5，4，3，6
下标依此是0,1,2,3,4,5
第一次排序：
0，1位置上的数据比较 谁大谁往右移动
1，2位置比较谁大谁往右移动
依此类推 最后确定位置5上的数据是6
