算法与数据结构

发表于 更新于 阅读次数： 本文字数： 3k 阅读时长 ≈ 3 分钟
时间复杂度

数组结构：常数复杂度:+ - * / 位运算（与数据量无关）
链表结构：遍历->O(n)

选择排序

aN^2+bN+c -> O(N^2): 只取最高阶项，且忽略系数 （设上限）

1
2
3
4
5
6
7
8
9
10
11
selectionsort(int[] arr){
     if(arr == NULL || arr.length<2 ) {return ;}
     for(int i=0; i < arr.length - 1;i++){
     int minindex =i;
     for(j=i+1;j < arr.length; j++)
     {
        minindex = arr[j] < arr[minindex] ? j : minindex ;
     }
     swap(arr,i,minindex);
    }
}

先看时间复杂度指标,时间复杂度一致时,需实际跑代码比较优劣。

额外空间复杂度O(1)

冒泡排序: 大的数依次向右移动 O(N^2)
1
2
3
4
5
6
7
8
9
10
11
12
13
bubblesort(int[] arr)
{
    if(arr == NULL || arr.length < 2) {return;}
    for (int e = arr.lemgth-1 ; e>0 ; e-- )
    {
        for(int i=0; i < e; i++ )
        {
            if(arr[i]>arr[i+1])
                swap(arr,i,i+1);
        }
    }

}
异或运算：对0 1两个数进行操作；相同为0；不同为1； (或二进制的无进位相加)
  • 0 ^ N = N ; N ^ N = 0
  • 满足交换律和结合律 a^b=b^a ; (a^b)^c = a^(b^c)
  • 同一组数据，异或结果与顺序无关。

Q1：在一个数组中，已知只有一种数出现奇数次，其他数出现偶数次，如何找到？
Q2：在一个数组中，已知只有两种数出现奇数次，其他数出现偶数次，如何找到？
要求时间复杂度为O(N)
A1: int eor=0 ; 提取数组的所有数，进行异或：arr[0]^arr[1]^……arr[n]=结果
A2: 先所有数组进行异或 eor=a^b，接着依次取出一个数与该结果异或，得到结果。

位运算操作(二进制)：一个数取反加1，可以都到最右侧的数。

插入排序

0-0有序->0-1有序->0-2有序…………
4,5,6,7,3,2,1 -> O(N^2)
1,2,3,4,5,6,7 -> 0(N)
时间复杂度由算法最差情况的表现决定。

1
2
3
4
5
6
7
8
9
insertsort(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); }
    }
}
二分法的详解与扩展
    1. 在一个有序数组中，找到某个数的存在
      (1)遍历 O（N）
      (2)二分 O(log2(N))
    1. 在一个有序数组中，找到>=某个数最左侧的位置
      ex: 1 2 2 2 2 3 3 3 3 4 4 4 4 4 4 4
    1. 局部最小值问题
      在一个无序数组中，任何两个相邻的数不相等，求一个局部最小的过程 在时间复杂度上好于O(N)
      A： 1 3 5 7 4 9 6 3 2
      先看0位置和n-1位置是否存在局部最小，若不，则中间必有局部最小。
      接下来继续比较运用二分法。
对数器

优秀方法(想测试的)：考虑时间复杂度，追求优解

普通方法：不考虑时间复杂度，只考虑解决问题

用随机样本产生器，对两种方法运行一遍，结果一样，则说明优秀方法正确。

剖析递归行为及其时间复杂度的估算

求一个数组的最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
process (int[] arr ,int L , int R)
{
    if (L==R)
    {
        return arr[L];
    }
    int mid = L + ((R-L)/2); // 中点，防止内存溢出，高级：mid=L+(R-L)>>1 右移一位相当于除二    
    int leftMax = process (arr,L,mid);
    int rightMax = process (arr,mid+1,R);
    return Math.max(leftMax , rightMax);
} 
调用：
getMAX(int[] arr)
{return process(arr,0,arr.length-1);}
  • master公式： T(N)=a*T(N/b)+O(N^d)
    T(N)：母问题的数据量为N级别 T(N/b):子问题的规模都是N/b a:子问题的调用次数 O(N^d):除去子问题外剩下过程的时间复杂度
  1. logb(a)<d -> O(N^d)
  2. logb(a)>d -> O(N^logb(a))
  3. logb(a)==d -> O(N^d*logN)
归并排序

中点切一半，左右各自排好序，最后组合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void mergeSort(int[] arr)
{
    if(arr == null || arr.length < 2)
    { return ;}
    process(arr, 0 , arr.length - 1);
}
void process(int[] arr, int L, int R)
{
    if(L==R){return ;}
    int mid = L + ((R-L)/2);
    process (arr,L,mid);
    process (arr,mid+1,R);
    merge(arr,L,mid,R);
}
void merge(int[] arr, int L ,int M, int R)
{
    int[] help = new int[R-L+1];
    int i=0;int p1=L;int p2 = M+1;
    while (p1<=M && p2<=R)
    { help[i++]=arr[p1]<=arr[p2]?arr[p1++]:arr[p2++];}
    while (p1<=M) { help[i++]= arr[p2++]; }
    while (p2<=R) { help[i++]= arr[p2++]; }
    for(i=0;i<help.length;i++) { arr[L+i] = help[i]; }
}

时间复杂度： T(N) = 2 * T(N/2) + O(N) —> O(N*logN)
额外空间复杂度：O(N)

  • 扩展问题：小和问题和逆序对问题

  1. 小和问题：在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和,求一个数组的小和
    ex: 1 3 4 2 5 -> 0 + 1 + 1 + 3 + 1 + 1 + 3 + 4 + 2 = 16
    另一种思想： 左边有多少个数比该数大 41+23+14+12=16

  2. 逆序对问题：在一个数组中，左边的数如果比右边的数大，则这两个数构成一个逆序对,打印所有的逆序对。

b