Day1 25/2/14 FRI

【一周刷爆LeetCode，算法大神左神（左程云）耗时100天打造算法与数据结构基础到高级全家桶教程，直击BTAJ等一线大厂必问算法面试题真题详解（马士兵）】https://www.bilibili.com/video/BV13g41157hK?p=3&vd_source=04ee94ad3f2168d7d5252c857a2bf358

目录

1、认识复杂度和简单排序算法

1.1 常数时间操作 & 时间复杂度

1.2 基础排序算法

1.2.1 选择排序

1.2.2 冒泡排序

补充：异或运算

1.2.3 插入排序

1.3 二分查找

1.4 对数器

1.5 master公式

---

笔记：

1、认识复杂度和简单排序算法

1.1 常数时间操作 & 时间复杂度

常数时间的操作：与数据量无关的操作，每次都是固定时间完成

数组查数是，链表不是？

数组是记录在案的，有目录可供直接取用，与数据量无关；而链表没有记录在案的目录，只能一个个查找，因此与数据量有关

时间复杂度：忽略最低项后只要最高项，且忽略掉系数。

忽略系数的原因，当数据量N足够大的时候，它的系数对它造不成影响。

评估一个算法流程的好坏，先比较时间复杂度指标，当指标相同时再实际运行去测哪个算法更好。

1.2 基础排序算法

选择排序&冒泡排序：都是O(N^2)，实现方式不同但本质没区别

1.2.1 选择排序

选择排序：从i=0开始++，每加一次，从arr[i]开始遍历到arr[n-1]并把最小值交换到arr[i]上。

（遍历：0到n-1、1到n-1、2到n-1等等）

1.2.2 冒泡排序

冒泡排序：两个位置间比较，慢慢把数字升序或降序

从i=0开始++，如果arr[i]大于arr[i+1]，它俩交换。这个方法每次遍历后，右边的数都是前面最大的。

（遍历：0到n-1、0到n-2、0到n-3等等）

补充：异或运算

可以理解为无进位相加，二进制中：0^0=0；1^0=0^1=1；1^1=0

N进制中：N^0=0^N=N；N^N=0

异或运算满足交换律、结合律

//使用前提：a和b各自指向的内存空间必须不同（a和b的数值可以一样，但a的地址不能等于b的地址，否则异或运算就会把a和b都抹为0）int a= 某个值;int b= 某个值;a=a^b; //（a=a^b, b=b）b=a^b; //（a=a^b, b=a^b^b=a^(b^b)=a^0=a）a=a^b; //（a=a^b^a=b, b=a）

【异或运算】例题：

（1）136. 只出现一次的数字 - 力扣（LeetCode）

描述：只有一个数字出现奇数次，找出它。

思路：用“异或 a^a=0”消除所有偶数次的数。

（2）描述：有两个数a和b都出现奇数次，找出它们两个。

思路？：先边遍历边异或得到targets=a^b，再将targets再和整个数组异或一遍，得到其中一个奇数次的数a。然后a和targets再异或得到b。

1.2.3 插入排序

插入排序：简而言之就像打扑克，按数字顺序整理好手中的牌，抽新牌后插入到对应位置上。

由于在数组中插入一个位置时，后面的数都要整体往后移，所以干脆在比较的同时就交换了位置，因此看着像冒泡排序。

从int i=1开始，因为再i=0上已经做到了有序。

数据状况不同，会导致算法流程的时间复杂度不同。

时间复杂度是按最差情况估计算法表现。

1.3 二分查找

时间复杂度：O(logN)

无论数组是否有序，都可以二分

例题：

（1）在有序数组中，找某数是否存在

（2）在有序数组中，找≥某数的最左侧位置

（3）在无序数组中，找局部最小值问题

1.4 对数器

原理：利用随机样本产生器去测试方法a和方法b，检查二者的输出和性能。修改样本大小和随机程度之后多测几次。

方法a：想测的方法

方法b：好实现但性能不太好的方法

java实现：

​Math.random()是等概率返回[0,1)区间内的一个小数。

而(int)Math.random() * N则是等概率返回[0, N-1]区间内的一个整数。

// 数组长度随机int[] arr = new int[ (maxSize+1) * (int)Math.random() ];// 数组数值随机，使用相减来概率得到负数for(int i=0; i<arr.length; i++){arr[i] = (int) ( (maxValue+1) * Math.random() - (int) ( maxValue * Math.random() );}

然后创建两个空数组分别存储调用方法a和b之后的结果，比较结果是否相同。

1.5 master公式

master公式：T(N) = a*T(N/b) + O(N^d)

log(b,a) > d，复杂度为O( N^log(b,a) )

log(b,a) = d，复杂度为O( N^d * logN )

log(b,a) < d，复杂度为O( N^d )