复杂度和简单排序算法_笔记01
目录
本文知识点记录自左程云 算法与数据结构基础到高级教程 图片截取自视频中
常数操作
和数据量无关的操作
+ - * / 位运算 都是常数操作;int a= arr[i]； //常数操作int b= list.get(i) //非常数操作，list是一个链表时间复杂度
常数操作的数量写成表达式，不要低阶项，除去最高项的系数剩下的。例如a*N²+b*N+c，写为O(N²)
对任何算法，估算其时间复杂度时，按照最差情况来估计，即耗费的时间最多是多少，取最大阶作为时间复杂度
当时间复杂度指标相同，需要比较不同算法流程常数项时间的时候，不需要再分析了，用具体的数据样本测试。因为虽然可以估算出常数操作数量，但是不同常数操作花费的时间不同，比较常数项时间就不能仅仅靠常数项的值的大小
加减法和位运算进行一次花费的时间是不同的
01_选择排序
时间复杂度：O(N^2)
//selection sortstatic void selectionSort(int[] arr){ for (int i = 0; i < arr.length-1; i++) { int min = arr[i]; for (int j = i+1; j < arr.length; j++) { if(arr[j] < min){ swap(arr[i],arr[j]); } } }}02_冒泡排序
时间复杂度：O(N^2)
//bubble sortstatic void bubbleSort(int[] arr){ for (int i = arr.length-1; i > 1; i--) { for (int j = 0; j < i; j++) { if(arr[j] > arr[j+1]) swap(arr[j], arr[j+1]); } }}swap() (用^运算符)
异或运算^,按位 相异为1，相同为0，可以理解为无进位相加,满足交换律、结合律，即一堆数进行^操作，与其顺序无关
为什么^满足 结果与顺序无关的性质？
根据^的无进位相加来理解：
一批数，最终结果的每一位上是0还是1，与该位上有几个1相加有关。比如，若有N个数相^，某一位上，1出现了奇数次，结果值对应的该位上，值就为1；1出现偶数次，结果值对应的该位上，值为0。显然，结果与顺序无关。
若两个数存储在两个不同的内存区域中，则可以这样交换
int a=10,b=20;void swap(int a, int b){ //若传入参数是数组元素，则两数下标不能相同a= a^b;b= a^b;a= a^b;}^的应用
剑指 Offer 56 - I. 数组中数字出现的次数
//在一个数组中，只有两个数出现了奇数次，其他数都出现了偶数次，返回这两个数class Solution { //从n右边往左，找第一个值为1的位，在该处，a与b的值是不同的，根据这一位上的值可以把a和b从nums里面分到两个区域 int GetRightOne(int n){ return n^(n&(n-1)); } public int[] singleNumbers(int[] nums) { int[] res = new int[2]; res[0] = 0; res[1] = 0; int tmp = 0; for(int i = 0; i < nums.length; ++i){ tmp ^= nums[i]; //temp=a^b(a b即是要返回的两数) } int rightone = GetRightOne(tmp); for(int i = 0; i < nums.length; ++i){ if((nums[i] & rightone) == rightone){ res[0] ^= nums[i]; }else{ res[1] ^= nums[i]; } } return res; }}03_插入排序
时间复杂度：O(N^2)
//insertion sort, method bstatic void insertionSort(int[] arr){ for (int i = 1; i < arr.length; i++) { for (int k = i; k > 0 && (arr[k] < arr[k-1]); --k) { swap(arr[k], arr[k-1]); } }}二分
二分与数组有序无序无关，不是只有有序才能用二分
- 在一个有序数组中，找某个数是否存在
O(logN) //时间复杂度,logN默认以2为底//每次对半分，找比较中间的数和要找的数的大小关系，最坏的情况：分到不能再分才找到，即进行了logN次比较- 在一个有序数组中，找 >=某个数最左侧的位置
- 局部最小值
给一个无序且互不相等的数组，求其局部最小值。局部最小值定义为：若a[0]a[n-1],n-1位置局部最小；若a[i]<a[i-1] && a[i]<a[i+1] ,i位置为局部最小。
求L和R的中点(L和R是数组索引)：
int mid = L + (R-L)>>1;这样写不容易越界（当L和R非常大时，L+R可能溢出）；
(R-L)>>1 比（R-L）/2 更快。
对数器
- 有一个想测试的方法a(复杂度更好)
- 实现复杂度不好，但是容易实现的方法b;
- 实现一个随机样本产生器
- 方法a和方法b跑相同的随机样本，看看结果是否一致
- 若有一个样本使得比对结果不一致，打印样本进行人工干预，更改方法a或方法b
- 当样本数量很多时，比对测试依然正确，可以确定方法a已经正确
为什么要有对数器？
各种OJ也是人工输入的测试用例，不排除你的算法有问题时，测试用例没有测出来（没包含进所有的情况），所以自己设计对数器，进行人工干预，这是最稳妥的测试方法，不会出现上面的错误。
对数器的实现
import java.util.Arrays;public class Test { //交换两数 static void swap(int a, int b){ int tmp = a; a = b; b = tmp; } //若确定a和b不指向同一块内存，则swap可以这样实现// static void swap(int a, int b){// a = a ^ b;// b = a ^ b;// a = a ^ b;// } //打印数组 static void print(int[] arr){ for(int a : arr) System.out.print(a+" "); } //bubble sort static void bubbleSort(int[] arr){ for (int i = arr.length-1; i > 1; i--) { for (int j = 0; j < i; j++) { if(arr[j] > arr[j+1]) swap(arr[j], arr[j+1]); } } } //selection sort, method a static void selectionSort(int[] arr){ for (int i = 0; i < arr.length-1; i++) { int min = arr[i]; for (int j = i+1; j < arr.length; j++) { if(arr[j] < min){ swap(arr[i],arr[j]); } } } } //insertion sort, method b static void insertionSort(int[] arr){ for (int i = 1; i < arr.length; i++) { for (int k = i; k > 0 && (arr[k] < arr[k-1]); --k) { swap(arr[k], arr[k-1]); } } } //generate random array public static int[] generateRandomArray(int maxsize, int maxvalue){ int[] arr = new int[(int)((maxsize+1)*Math.random())]; for(int i = 0; i < arr.length; ++i){ arr[i] = (int)((maxvalue+1)*Math.random()) -(int)((maxvalue+1)*Math.random()); } return arr; } public static void main(String[] args) { //logarithmic detector int testTime = 500000; int maxSize = 100; int maxValue = 100; boolean sign = true; for (int i = 0; i < testTime; i++) { int[] arr1 = generateRandomArray(maxSize, maxValue); int[] arr2 = Arrays.copyOf(arr1,arr1.length); selectionSort(arr1); bubbleSort(arr2); if(!Arrays.equals(arr1,arr2)){ sign = false; break; } } System.out.println(sign ? 666 : "gg"); if((sign ? 666 : "gg") == "gg"){ int[] arr1 = generateRandomArray(maxSize, maxValue); int[] arr2 = Arrays.copyOf(arr1,arr1.length); print(arr1); selectionSort(arr1); print(arr1); bubbleSort(arr2); print(arr2); } }}递归行为和递归行为时间复杂度的估算
递归行为可以理解为多叉树的遍历，每一个节点要计算值，必须依赖当前节点的子节点。由于这种依赖关系，在没执行到叶子节点前，就相当于不断把节点压入栈中（这实际上是一个递推的过程）；到了叶子节点，不再依赖其他节点就可以返回当前值了，于是相当于弹栈（相当于回溯过程）。
递归时间复杂度的估算
master公式（适用于子问题等规模的递归时间复杂度的求解）
T(N) = a*T(N/b) + O(N^d)
lo g b a<d→O( N d )log_ba<d→O(N^d ) logba<d→O(Nd)
lo g b a>d→O( N x )......x=lo g b alog_ba>d→O(N^x)......x=log_ba logba>d→O(Nx)......x=logba
lo g b a=d→O( N d ∗logN)log_ba=d→O(N^d*logN) logba=d→O(Nd∗logN)
算法的复杂度与Master定理（必看！！！）
