image.png时间复杂度影响最大

时间复杂度

常数时间操作:一个操作的执行时间不以具体样本量为转移，每次执行时间都是固定时间。
常见的常数时间的操作：

  • 常见的算数运算（+、-、、/、%）（+ -比/快）
  • 常见的位运算（>>,>>>,<<,|,&,^等）(位运算比算数运算快）
  • 赋值、比较、自增、自减操作等
  • 数组寻址操作

算数运算转为位运算
n2——n<<1 n/2——n>>1(n的二进制的所有为1的值降一位）
n2+1——(n<<1)|1 n/2+1——(n>>1)|1（与1进行或运算）

image.png
image.png
image.png

排序

选择排序

时间复杂度O（N^2）
image.png

冒泡排序

时间复杂度O（N**2）
image.png
直接调数组里的方法：（也许不是冒泡原理，但省很多事）
Arrays.sort(arr);
System.out.println(Arrays.toString(arr));

选择排序

时间复杂度O（N**2）（最差情况）
image.png

额外空间复杂度

image.png

算法流程的常数项

image.png

时间复杂度排序

image.png

二分法

作用：
在一个有序数组中，找某个值是否存在
在一个有序数组中，找>=某个值最左侧的位置
在一个有序数组中，找<=某个数最右侧的位置
局部最小值问题
image.png
image.png
局部二分
image.png

异或运算^

异或运算：相同为0，不同为1
简记为：无进位相加
特性：具有交换性，偶数个0或1异或结果为0，奇数个0或1异或结果为1

题目一
如何不适用额外变量交换两个变量的值？
image.png
前提：两个变量的内存地址是独立的，不是同一个
题目二
一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这种数
方法：定义变量ero=0，用ero把数组中的所有数都异或，最终ero=这种数
（出现偶数次的数异或的结果为0）

题目三
怎么把一个int类型的数，提取出最右侧的1来
方法：N&（取反N+1）
image.png
题目四
一个数组中有两种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这两种数
方法：1.定义变量eor=a^b，则eor!=0（因为a!=b），eor必然有一个位置上是1
2.取出eor最右侧的1，假设是第2位，则a,b在第2位上一定不同，一个为1一个为0
3.根据第2位是否为1或0，把数组分为两类，其中a,b一定会分开
4，定义变量ero’，与其中一类全部异或计算，出现偶数次的数异或的结果为0，那么最后ero’=a或b
5，另一个奇数 b或a = ero^ero’
image.png
image.png
题目：数出一个二进制数的1的个数（普通方法：一个二进制数共有32位，for循环32次）
二进制异或方法：
1，取出该数最右侧的1 rightOne
2，count加1
3，把原数最右侧的1去掉，以便下次取出原数第二右的1，（N^rightOne）
image.png