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
随机样本产生器,控制样本大小,小数测试人眼看 大数更随机跑个几千万次