算法与数据结构

时间复杂度

数组结构:常数复杂度:+ - * / 位运算(与数据量无关)
链表结构:遍历->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