TwoSugar的算法笔记

时间、空间复杂度

时间复杂度

时间复杂度是用来估计算法运行时间的一个式子（单位）
一般来说，时间复杂度高的算法比时间复杂度低的算法慢
常见的时间复杂度（按效率排序）：O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n2logn)<O(n^3)
复杂问题的时间复杂度：O(n!)、O(2^n)、O(nn)

快速判断时间复杂度的方法（简单情况）

确定问题规模n（例如：循环次数）
循环过程减半（logn）
k层关于n的循环（n^k）

复杂情况：根据算法执行过程进行判断

空间复杂度

空间复杂度：用来评估算法内存占用大小的式子
空间复杂度的表示方式与时间复杂度完全一样
- 算法使用了几个变量(O(1))
- 算法使用了几个长度为n的一维数组（O(n)）
- 算法使用了几个m行n列的二维数组(O(mn))
空间换时间

递归

递归的两个特点

调用自身
结束条件

查找

在一些元素中通过一定的方法找到与给定关键字相同的数据元素的过程

列表查找：

顺序查找
二分查找

python内置函数index()

排序

排序总览

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3YmpHV63-1637246864044)(D:\桌面\笔记\排序.jpg)]

冒泡排序、选择排序、插入排序

使用场景：

//这都不会，重开吧。

快速排序

快排的过程可以看作递归+划分

（注：为方便记忆算法，我习惯将其记作“递归+划分” ------sort（partition，sort，sort) + partition(while{while,while})）

使用场景：

    public void quickSort(int[] nums){
        sort(nums, 0, nums.length-1);
    }
	//递归
    public void sort(int[] nums, int i, int j){
        if( i >= j )return;//递归结束条件
        int p = partition(nums, i, j);
        sort(nums, i, p-1);
        sort(nums, p+1, j);
    }
	//划分
    public int partition(int[] nums, int i, int j){
        int p = nums[i];
        while( i < j ){
            while( i < j && nums[j] >= p ){
                j--;//从右往左找到第一个<p的
            }
            nums[i] = nums[j];
            while( i < j && nums[i] <= p ){
                i++;//从左往右找到第一个>p的
            }
            nums[j] = nums[i];
        }
        nums[i] = p;//最后把p放到对应位置
        return i;
    }

可以使用快排解决的问题：

堆排序

堆排序的过程可以拆解为

生成大根堆
不断将根顶取下并进行调整从而排序
调整函数

（注：为方便记忆算法，我习惯将其记作“生成大根堆+调整+排序” ------for(第一个非叶子节点){adjust()}+for(第一个叶子节点){swap(堆顶，叶子节点)，adjust}+adjust(){for(){if+if}}）

使用场景：

    public void sort(int[] nums){
        //生成大根堆
        for(int i=(nums.length-1)/2;i>=0;i--){
            adjustHeap(nums,i,nums.length);
        }
        //不断将根顶取下并进行调整从而排序
        for(int j=nums.length-1;j>0;j--){
            swap(nums,0,j);
            adjustHeap(nums,0,j);
        }
    }
    public void adjustHeap(int[] nums,int i,int length){
        int tmp=nums[i];
        for(int k=i*2+1;k<length;k=k*2+1){
            if(k+1<length&&nums[k]<nums[k+1]){
                k++;
            }
            if(nums[k]>tmp){
                nums[i]=nums[k];
                i=k;
            }else{
                break;
            }
        }
        nums[i]=tmp;
    }

    public void swap(int[] nums,int a,int b){
        int tmp=nums[a];
        nums[a]=nums[b];
        nums[b]=tmp;
    }

可以使用堆排序解决的题：

topk问题

topk问题：从arr[1, n]这n个数中，找出最大的k个数，这就是经典的TopK问题

实现方法：

冒泡排序（排k趟）O(mn)
排序后进行切片，O(nlogn)+k
堆排序O(nlogk)
1. 构建小根堆
2. 新加入元素与根顶进行比较
3. 调用调整函数

归并排序

归并排序的过程可以看作是先分解再聚合，通过将待排序目标进行分解从而达到方便排序的目标，最后通过合并函数将已经排序的两个序列进行合并

（注：为方便记忆算法，我习惯将其记作“递归+合并” ------sort（sort，sort，merge）merge（while，while，while，while））

使用场景：

import java.util.Arrays;

public class MergeSort {
    public static void main(String []args){
        int []arr = {9,8,7,6,5,4,3,2,1};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void sort(int []arr){
        int []temp = new int[arr.length];//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
        sort(arr,0,arr.length-1,temp);
    }
    private static void sort(int[] arr,int left,int right,int []temp){
        if(left<right){
            int mid = (left+right)/2;
            sort(arr,left,mid,temp);//左边归并排序，使得左子序列有序
            sort(arr,mid+1,right,temp);//右边归并排序，使得右子序列有序
            merge(arr,left,mid,right,temp);//将两个有序子数组合并操作
        }
    }
    private static void merge(int[] arr,int left,int mid,int right,int[] temp){
        int i = left;//左序列指针
        int j = mid+1;//右序列指针
        int t = 0;//临时数组指针
        while (i<=mid && j<=right){
            if(arr[i]<=arr[j]){
                temp[t++] = arr[i++];
            }else {
                temp[t++] = arr[j++];
            }
        }
        while(i<=mid){//将左边剩余元素填充进temp中
            temp[t++] = arr[i++];
        }
        while(j<=right){//将右序列剩余元素填充进temp中
            temp[t++] = arr[j++];
        }
        t = 0;
        //将temp中的元素全部拷贝到原数组中
        while(left <= right){
            arr[left++] = temp[t++];
        }
    }
}