算法基础：复杂度、二分法、异或运算—左程云
时间复杂度
常数时间操作
-
执行时间固定的为常数时间操作，执行时间不固定不是常数操作 ·常见的算术运算（+、-、*、/、%等） ·常见的位运算（>>带符号右移、>>>不带符号右移、<<、|、&、^等） ·赋值、比较、白增、白减操作等 ·数组寻址操作
排序算法O（N^2）
选择排序
-
每次确定最小值[0-n-1]，[1-n-1]，[2-n-1]… 每个范围的前界：0，1，2… 由第一个for循环确定 i 整个范围 [i-n-1] 由第二个for循环确定——找出最小值 进行swap交换
冒泡排序
-
每次确定最值[0-n-1],[0-n-2],[0-n-3]
插入排序
-
时间复杂度与原始待排序数组的有序程度有关 完全有序与排序结果一致是O（n） 完全有序与排序结果逆序是O(n^2)
二分法
-
适用范畴 在一个有序数组中，找某个数是否存在 在一个有序数组中，找>=某个数最左侧的位置 在一个有序数组中，找<=某个数最右侧的位置 局部最小值问题
异或运算
-
异或运算：同0异1 异或运算相当于无进制相加。110 | 111 = 001 异或性质： 0^N==N N^N==0 异或运满足交换律和结合率
-
适用题目 整个数组中，只有一个数出现奇数次，其他数均出现偶数次，求取这个数。 int类型的数，提取出最右侧的“1” 整个数组中，有两种数出现奇数次，其他数均出现偶数次，求取出现奇数次的数。
-
提取出最右侧的“1” 提取出整数二进制中“1”的个数 整个数组中，有两种数出现奇数次，其他数均出现偶数次，求取出现奇数次的数。
下一篇：
二叉树的三种遍历方式