Leetcode题解 - 0、玩转算法基础 - 《算法》

基础准备

基础准备

数据规模的概念

如果想在1s之内解决问题：

O(n^2)的算法可以处理大约10^4级别的数据 O(nlogn)的算法可以处理大约10^7级别的数据 O(n)的算法可以处理大约10^8级别的数据

空间复杂度

多开一个辅助的数组：O(n)
多开一个辅助的二维数组：O(n^2)
多开常数空间：O(1)

递归调用是有空间代价的

空间复杂度O(1)

int sum1(int n){ assert(n>=0); int ret=0; for(int i=0;i<=n;i++){ ret+=i; return ret; }

空间复杂度O(n)

int sum2(int n){ assert(n>=0); if(n==0) return 0; return n+sum2(n-1);//递归(深度就是空间复杂度) }

常见的复杂度分析

O(1)

void SwapTwoInts(int &a,int &b){ int temp=a; a=b; b=temp; }

O(n)

int sum(int n){ int ret=0; for(int i=0;i<=n;i++){ ret+=i; retrn ret; }

O(n^2)

void selectSort(int arr[],int []){ for(int i=0;i int minIndex=i; for(int j;j if(arr[j] minIndex=j; swap(arr[i],arr[minIndex]); }//选择排序

(n-1)+(n-2)+(n-3)……….+0

O(logn)

int binarySearch(int arr[],int n,int target){ int l=0, r=n-1; while(l<=r){ int mid=l+(r-l)/2; if(arr[mid]=target) return mid; if(arr[mid]>target]) r=mid-1; else l=m+1; } return -1; }//二分查找算法

n->n/2->n/4……….1 n经过几次除以2操作之后会等于1

O(nlogn)

void hello(int n){ for(int sz=1;sz for(int i=1;i cout<<”Hello,Algorithm!”<}

O(sqrt(n))

bool isPrime(int n){ for(int x=2;x*x<=n;x++){ if(n%x==0){ return false; } }

复杂度试验

自以为写出了一个O(nlogn)的算法，实际上却是O(n^2)的算法

实验，观察趋势每次将数据规模提高两倍，看时间的变化

递归算法的复杂度分析

不是有递归的函数就一定是O(nlogn)！

递归中进行一次递归调用的复杂度分析

int binarySearch(int arr[ ],int l,int r,int target){ if(l>r) return -1; int mid=(l+r)/2; if(arr[mid]==target) return else if(arr[mid]>target) return binarySearch(arr,l,mid-1,target); else if(arr[mid] return binarySearch(arr,mid+1,r,target); }

时间复杂度：O(T*logn) //此处的T为1

在每个递归函数中，时间复杂度未T；

int sum(int n){ assert(n>=0); if(n==0) return 0; return n+sum(n-1);

时间复杂度：O(n)

double pow(doube x,int n){ assert(n>=0); if(n==0) return 1.0; double t=pow(x,n/2); if(n%2) return xtt; return t*t; }

递归深度：logn
时间复杂度：O(logn)

多次递归调用

int f(int n){ assert(n>=0); if(n==0){ return 1; return f(n-1)+f(n-1)

计算调用的次数

1+2+4+8=15

时间复杂度：O(2^n) //可动态规划优化

课外资料：主定理

均摊复杂度分析（Amortized Time）
动态数组（vector）：到达一定条件执行扩容操作

每n个数才会进行依次扩容操作，前面每次添加为1，n个数就是n次，然后将数据转移到新数组中，这个过程操作了n次，加起来就是2n，均摊到前面的n次操作中，就是2，也就是O（1）

数组中的问题最常见

排序：选择排序、插入排序、归并排序、快速排序
查找：二分查找法
数据结构：栈、队列、堆

二分查找法

public void  binarySearch(arr[],int n,int target){
    int l=0,r=n-1; //在[l...r]的范围内寻找target
    while(l<=r) {//当l=r的时候，区间[l...r]依然是有效区间
        int mid=(l+r)/2;
        if(arr[mid]==target)
            return mid;
        if(target>arr[mid])
            l=mid+1;
        else
            r=mid-1;
      }
    return -1;
}

注意循环不变量的问题，确保自己需要的条件是什么？明确变量的意义，循环不变量

public void  binarySearch(arr[],int n,int target){
    int l=0,r=n; //在[l...r）的范围内寻找target
    while(l<r) {//当l=r的时候，区间[l...r）依然是有效区间
       // int mid=(l+r)/2;
        int mid =l+(r-l)/2;//防止数据过大的整型溢出问题；
        if(arr[mid]==target)
            return mid;
        if(target>arr[mid])
            l=mid+1;
        else
            r=mid;
      }
    return -1;
}