左程云算法笔记 1、认识复杂度和简单排序算法

Love The Way You Lie 2023-09-29 17:38 5阅读 0赞

课程链接[1.认识复杂度和简单排序算法\_哔哩哔哩\_bilibili][1._bilibili]

时间复杂度是在一个算法流程中，估计常数操作的一个指标

常数时间的操作

一个操作如果和样本的数据量没有关系，每次都是固定时间内完成的操作，叫做常数操作。

时间复杂度为一个算法流程中，常数操作数量的一个指标。常用O(读作big O)来表示。具体

来说，先要对一个算法流程非常熟悉，然后去写出这个算法流程中，发生了多少常数操作，

进而总结出常数操作数量的表达式。

在表达式中，只要高阶项，不要低阶项，也不要高阶项的系数，剩下的部分如果为f(N)，那

么时间复杂度为O(f(N))。

评价一个算法流程的好坏，先看时间复杂度的指标，然后再分析不同数据样本下的实际运行

时间，也就是“常数项时间

int a = a[i];//是常数操作（+-#/）位运算，一定是固定时间
    int b = list.get(i);//不是，因为链表要一个个找

1.选择排序

package class01;
    
    import java.util.Arrays;
    
    public class Code01_SelectionSort {
    
    public static void selectionSort(int[] arr) {
    if (arr == null || arr.length < 2) {
    return;
    }
    for (int i = 0; i < arr.length - 1; i++) {
    int minIndex = i;
    for (int j = i + 1; j < arr.length; j++) {
    minIndex = arr[j] < arr[minIndex] ? j : minIndex;
    }
    swap(arr, i, minIndex);
    }
    }
    
    public static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
    }
    }

2.冒泡排序 注意里面的位运算 异或运算 相同为0不同为1 也可以理解为无进位相加（ 0+1 =1 1+1 = 0） a=a^b;b=a^b;a=a^b; 之后ab值可以进行交换 不用申请额外空间，前提在内存中是两个独立的，否则会变成零（不推荐）。

1）0^N == N N^N == 0

2）异或运算满足交换律和结合率

3）不用额外变量交换两个数

package class01;
    
    import java.util.Arrays;
    
    public class Code02_BubbleSort {
    
    public static void bubbleSort(int[] arr) {
    if (arr == null || arr.length < 2) {
    return;
    }
    for (int e = arr.length - 1; e > 0; e--) {
    for (int i = 0; i < e; i++) {
    if (arr[i] > arr[i + 1]) {
    swap(arr, i, i + 1);
    }
    }
    }
    }
    
    public static void swap(int[] arr, int i, int j) {
    arr[i] = arr[i] ^ arr[j];//异或运算 相同为0不同为1
    arr[j] = arr[i] ^ arr[j];
    arr[i] = arr[i] ^ arr[j];
    }
    
    }

4）一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到这一个数

public static void printOddTimesNum1(int[] arr) {
    int eO = 0;
    for (int cur : arr) {
    eO ^= cur;
    }
    System.out.println(eO);
    }

5）一个数组中有两种数出现了奇数次，其他数都出现了偶数次，怎么找到这两个数 设这两个数是a和b 最终eor一定是a^b ~取反 提取最右侧的1

public static void printOddTimesNum2(int[] arr) {
    int eO = 0, eOhasOne = 0;
    for (int curNum : arr) {
    eO ^= curNum;
    }
    //eor=a^b
    //提取最右侧的1（重点记）
    int rightOne = eO & (~eO + 1);
    for (int cur : arr) {
    if ((cur & rightOne) != 0) {
    eOhasOne ^= cur;
    }
    }
    System.out.println(eOhasOne + " " + (eO ^ eOhasOne));
    }

位运算非常快

3.插入排序

public static void insertionSort(int[] arr) {
    if (arr == null || arr.length < 2) {
    return;
    }
    for (int i = 1; i < arr.length; i++) {
    for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
    swap(arr, j, j + 1);
    }
    }
    }
     
    public static void swap(int[] arr, int i, int j) {
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[i] ^ arr[j];
    arr[i] = arr[i] ^ arr[j];
    }

4.二分法的详解与扩展

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

//算法第四版p15
    //rank函数的一个借口，Java中的方法重载
    public static int rank(int key, int[] a)
    {
        return rank(key, a, 0, a.length - 1);
    }
    //二分查找的递归实现
    public static int rank(int key, a, int lo, int hi)
    {
        if(lo > hi)
            return -1;
        int mid = lo + (hi - lo) / 2;//防止溢出
        //位运算速度更快
        //int mid = lo + ((hi - lo)>>1);
        if (key < a[mid])
            return rank(key, a, lo, mid - 1);
        else if (key > a[mid])
            return rank(key, a, mid + 1, hi);
        else
            return mid;
    }

2）在一个有序数组中，找>=某个数最左侧的位置

//有序数组最左匹配
    public class mostleft {
        public static void main(String[] args) {
            int[] arr = {0,0,0,1,1,2,2,2,2,2,2,3,3,3,3,3,4,4,4};
            System.out.println(left_match(arr,2));//5
    
        }
        //
        public static int left_match(int[] arr,int num){
            if(arr==null || arr.length==0){
                return -1;
            }
            int l=0;
            int r=arr.length-1;
            int ans=-1;
            while (l<=r){等于r是要把所有的数都测试完
                int mid=(l+r)/2;
                if(arr[mid]>=num){
                  /* 一直二分到最后一个数如果最后一个数是>=目标值的，此时就是最左的位置如果最后一个数不是>=目标值就说明上一次记录的index是最左的位置*/
                    ans=mid;
                    r=mid-1;
                }else {
                    l=mid+1;
                }
            }
            return ans;
        }
    }

3）局部最小值问题

public static boolean exist(int[] sortedArr, int num) {
            if (sortedArr == null || sortedArr.length == 0) {
                return false;
            }
            int L = 0;
            int R = sortedArr.length - 1;
            int mid = 0;
            while (L < R) {
                mid = L + ((R - L) >> 1);
                if (sortedArr[mid] == num) {
                    return true;
                } else if (sortedArr[mid] > num) {
                    R = mid - 1;
                } else {
                    L = mid + 1;
                }
            }
            return sortedArr[L] == num;
        }

对数器的概念和使用

1，有一个你想要测的方法a

2，实现复杂度不好但是容易实现的方法b

3，实现一个随机样本产生器

4，把方法a和方法b跑相同的随机样本，看看得到的结果是否一样。

5，如果有一个随机样本使得比对结果不一致，打印样本进行人工干预，改对方法a或者

方法b

6，当样本数量很多时比对测试依然正确，可以确定方法a已经正确。

[1._bilibili]: https://www.bilibili.com/video/BV13g41157hK?p=3&vd_source=a3824dbb31246972f969bd1877241fb2