复杂度

复杂度(Complexity, CPX)，指的是在给定样本中不同DNA 序列的总长度，是一件事物的复杂性可以用描写这事物所需的计算机语言的长度来衡量。

常数时间的操作：一个操作如果和样本的数据没有关系，每次都是固定时间内完成的操作，叫做常数操作。
时间复杂度为一个算法流程中，常数操作数量的一个指标。常用O（读作big O）来表示。具体来说，先要对一个算法流程非常熟悉，然后去写出这个算法流程中，发生了多少常数操作，进而总结出常数操作的表达式。
在表达式中，只要高阶项，不要低阶项，也不要高阶项的系数，剩下的部分如果为f(N)，那么时间复杂度为O(f(N))。
评价一个算法流程的好坏，先看时间复杂度的指标，然后再分析不同数据样本下的实际运行时间，也就是“常数项时间”。

异或(^)实现两个数交换

  1. a = 1;
  2. b = 2;
  3. a = a ^ b;
  4. b = a ^ b;
  5. a = a ^ b;

异或的性质

异或是一种基于二进制的位运算，用符号XOR或者 ^ 表示，其运算法则是对运算符两侧数的每一个二进制位，同值取0，异值取1。它与布尔运算的区别在于，当运算符两侧均为1时，布尔运算的结果为1，异或运算的结果为0。异或是无进位相加 。
异或使用的注意事项： 使用异或交换两个数要保证 两个数在内存中是两块不同的区域。两个数的值可以一样但是内存不可以。

异或的特性

1、交换律
2、结合律（即(a^b)^c == a^(b^c)）
3、对于任何数x，都有x^x=0，x^0=x
4、自反性 A XOR B XOR B = A xor 0 = A

异或实现两个数交换的解析

第三行 a = a ^ b 第四行 因为a = 1 ^ 2，所以b = 1 ^ 2 ^ 2, 2 ^ 2 = 0, 因为任何数和0异或都等于自己，所以b = 1。第五行，因为第三行a的值为a = 1 ^ 2,第四行， b = 1 ，所以，a =1 ^ 2 ^ 1,a = 2。

异或找到数组中出现一次奇数次的数

  1.         arr = [1,1,1,1,3,3,3,2,2,2,2];
  2.         let eor = 0;
  3.         for(let i in arr){
  4.             eor^=arr[i];
  5.         }
  6.         console.log(eor);

偶数次的都异或为0了 只有奇数次剩下一个 和 0异或为奇数次的数。

异或找到数组中出现两次奇数次的数

如果一个数组只有两组数出现了奇数次，其他的都出现了偶数次。
则设这两个数为a，b其他偶数次为others，如果把数组中所有的数进行异或，则结果eor=a^b，因为是两种数，则a!=b,eor!=0,所以eor一定在某一位上不等于0。假设ero在第八位是1，说明a和b在第八位一定是不一样的，才会导致异或的结果eor第八位为1。然后定义新的eor让所有的第八位上是1的数去异或eor，得到的eor一定是a或者b。<br />因为eor=a^b,eor=a or b,所以另一个数=eor^eor`。
附上java代码：
image.png

与运算提取出某一个数最右侧的1


复杂度和简单排序算法 -20210906- - 图2

插入排序

插入排序细节的讲解与复杂度分析
时间复杂度O(N^2)，额外空间复杂度O(1)
算法流程按照最差情况来估计时间复杂度

算法步骤

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
插入排序

代码示范

  1. function insertionSort(arr) {
  2.     var len = arr.length;
  3.     var preIndex, current;
  4.     for (var i = 1; i < len; i++) {
  5.         preIndex = i - 1;
  6.         current = arr[i];
  7.         while(preIndex >= 0 && arr[preIndex] > current) {
  8.             arr[preIndex+1] = arr[preIndex];
  9.             preIndex--;
  10.         }
  11.         arr[preIndex+1] = current;
  12.     }
  13.     return arr;
  14. }

二分法的详解与扩展

1）在一个有序数组中，找某个数是否存在
通过遍历找的话，则是一个O(N)的算法，而用二分的话先找中点m，再去判断m与要找的数的关系，在找中点，看关系，找到则返回。二分法的复杂度是O(log2N)；
2）在一个有序数组中，找>=某个数最左侧的位置
先找到中点的位置，判断是否满足>=number，满足继续二分左边。
用二分法找一个数存在找到了就停了，而找>=number最左右侧则需要二分到最后。
3）局部最小值问题
在一个数组中，arr无序，且任意两个相邻的数不相等。定义一个变量叫局部最小。要求时间复杂度好于O(N)。
先单独判断0位置是不是最小，如果不是则判断N-1是不是大于N-2，则找到中点M，如果满足m-1>m<m+1,则返回m。

优化一个流程就两个方向入手，要么是数据状况特殊可以优化，要么是问题特殊可以优化。构建一种排他性的东西，就完全可以使用二分法。

对数器的概念和使用

有一个想测的方法a，把一个不追求时间复杂度优劣的，但是很好想很好写的方法叫做方法b，生成一个随机样本产生器。把样本分别在ab中各跑一遍，然后对比结果是否相同，测试次数可以控制，当发现结果不同那必定有一个或者两个是错的，因为随机样本产生器是可以控制样本大小的，所以可以先小样本，在小样本的情况下比对ab的结果，就可以人来看对不对，用人工干预的方式把ab方法改对，再把长度调整的大一点，跑几千万组，就可以确定方法a对了。
1.有一个你想要测的方法。
2.时间复杂度不好但是容易实现的方法b
3.实现一个随机样本产生器
4.把方法a和方法b跑相同的随机样本，看看得到的结果是否一样
5.如果有一个随机样本使得对比结果不一致，打印样本进行人工干预，改对方法a或者方法b
6.当样本数量很多时比对测试依然正确，可以确定方法a已经正确。

刨析递归行为和递归行为复杂度的估算

用递归方法找一个数组中的最大值，系统上到底是怎么做的？
master公式的使用
一系列符合子问题规模等规模这些行为的递归，都可以用master公式求解时间复杂度。

T(N) = a*T(N/b) + 0(N^d)

1) log(b,a) > d -> 复杂度为O(N^log(b,a))
2)log(b,a) = d -> 复杂度为O(N^d * logN)
3)log(b,a) < d -> 复杂度为O(N^d)

  1. public static int getMax(int[] arr){
  2.      return process(arr, 0, arr.length-1);   
  3. }
  4. // 求arr[L...R]范围上的最大值
  5. public static int process(int[] arr, int L, int R){
  6.      if(L == R){ // arr[L...R]范围上只有一个数，直接返回，base case
  7.     return arr[L];
  8.     }
  9.     // 10行的写法是因为（L+R）/2可能会造成溢出， 所以采用了L+(R-L)/2， 右移一位等于/2。
  10.     int mid = L + ((R - L) >> 1); // 中点
  11.     int leftMax = process(arr, L, mid);
  12.     int rightMax = process(arr, mid +1, R);
  13.     return Math.max(leftMax, rightMax);
  14. }