时间复杂度以及简单的排序算法

int b = list.get(i)不属于常数操作，和数据量有关

时间复杂度：

进行多少次的常数操作

有N个数要进行比较，需要看N+N-1+N-2+N-3....+....1个

需要比较N+N-1+N-2+N-3....+....1个

需要置换N次

可以得到的表达式aN2+bN+c，常数项不要，低阶项不要，最高阶系数不要 时间复杂度：O（N^2）

当两个算法的O（N）一样，只能通过实验来确定“常数项时间”

额外空间复杂度：

有限几个变量O（1）

需要开辟额外数组 O（n）

冒泡排序：O（N^2）

上面的代码跑完之后，值可以交换过来，（i和j在内存里是独立的内存）否则就会变为0

异或运算 相同为零，不同为1 无进位相加 满足交换律和结合律

提取一个数32进制最右侧的1

int righone = eor & (~eor + 1)取反加一

插入排序：O（N^2）按照最差的表现作为时间复杂度

二分法（不一定有序）O（log N）

局部最小（i-1 > i < i+1）0 1 2 3 ……N-1必存在一个最小拐点 数况 问题（特殊）

对数器：

想测的方法a 好实现但是时间复杂度不好的方法b

随机样本产生器，控制样本大小，小数测试人眼看 大数更随机跑个几千万次