jlearning.cn

《数据结构与算法分析》(1)——算法分析

数学理论

  • $\exists$正常数$c$和$n_0$使得当$N \geq n_0$时,$T(N)\leq cf(N)$,则记为$T(N)=O(f(N))$。
  • $\exists$正常数$c$和$n_0$使得当$N \geq n_0$时,$T(N)\geq cf(N)$,则记为$T(N)=\Omega(f(N))$。
  • $T(N) = \Theta(h(N))$当且仅当$T(N)=O(f(N))$且$T(N)=\Omega(f(N))$。
  • 如果$T(N)=O(f(N))$且$T(N)\not=\Omega(f(N))$,则$T(N)=o(f(N))$。

如何评估时间复杂度

***

一个炸裂的例子

​ 求最大的子序列和——时间复杂度从$O(N^3)$到$O(N^2)$到$O(Nlog(N))$到$O(N)$

算法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private static int msss1(int[] sequence, int N) {
int ThisSum, MaxSum, i, j, k;
MaxSum = 0;
for(i=0;i<N;i++){
for(j=i;j<N;j++){
ThisSum = 0;
for(k=i;k<=j;k++){
ThisSum+=sequence[k];
}
if(ThisSum>MaxSum){
MaxSum = ThisSum;
}
}
}
return MaxSum;
}

时间复杂度:$O(N^3)$

最直接的暴力解法。有很多重复计算,比如说1+……+N1+……+N+N+1只需要加上一个N+1前面的部分不需要重复计算。所以有了算法二。

算法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private static int msss2(int[] sequence, int N) {
int ThisSum, MaxSum, i, j, k;
MaxSum = 0;
for(i=0;i<N;i++){
ThisSum = 0;
for(j=i;j<N;j++){
ThisSum+=sequence[j];
if(ThisSum>MaxSum){
MaxSum = ThisSum;
}
}
}
return MaxSum;
}

时间复杂度:$O(N^2)$

算法三

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private static int msss4(int[] A, int N) {
int ThisSum, MaxSum, j;
ThisSum = MaxSum = 0;
for(j=0;j<N;j++){
ThisSum+=A[j];
if(ThisSum>MaxSum)
MaxSum = ThisSum;
else if(ThisSum<0)
ThisSum = 0;
}
return MaxSum;
}

时间复杂度:$O(N)$

有DP算法的影子,用Maxsum储存到j点的最大序列和。如果$A[j]$是正的,就加上,如果是负的,就不变。因为初始值是0,和小于零,就为0。

算法四

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
private static int msss3(int[] A, int left, int right) {
int MaxLeftSum, MaxRightSum;
int MaxLeftBorderSum, MaxRightBorderSum;
int LeftBorderSum, RightBorderSum;
int Center,i;
if(left==right)
if(A[left]>0)
return A[left];
else
return 0;
Center = (left+right)/2;
MaxLeftSum = msss3(A,left,Center);
MaxRightSum = msss3(A,Center+1,right);
MaxLeftBorderSum = 0;
LeftBorderSum = 0;
for(i = Center;i>=left;i--){
LeftBorderSum+=A[i];
if(LeftBorderSum>MaxLeftBorderSum)
MaxLeftBorderSum = LeftBorderSum;
}
MaxRightBorderSum = 0;
RightBorderSum = 0;
for(i = Center+1;i<=right;i++){
RightBorderSum+=A[i];
if(RightBorderSum>MaxRightBorderSum)
MaxRightBorderSum = RightBorderSum;
}
return Max3(MaxLeftBorderSum+MaxRightBorderSum,MaxLeftSum,MaxRightSum);
}

秀分治算法。代码复杂,程序消耗了大量时间初始化变量,赋值等操作。

时间复杂度:$O(NlogN)$

评估欧几里德算法的时间复杂度

算法如下:

1
2
3
4
5
6
7
8
9
10
private static int Gcd(int M, int N) {
// TODO Auto-generated method stub
int rem;
while(N>0){
rem = M % N;
M = N;
N = rem;
}
return M;
}

$\because M mod N<M/2$

迭代次数最多是$2logN$,时间复杂度为$O(logN)$。

评估幂运算的时间复杂度

算法如下:

1
2
3
4
5
6
7
8
Pow(int x,int N){
if(N==0)
return 1;
if(IsEven(N))
return Pow(x*x,N/2);
else
return Pow(x*x,N/2)*x;
}

if语句里,第一种情况用了一个乘法,第二钟情况用了两个乘法。所以最多执行了$2logN$次乘法。

时间复杂度:$O(logN)$

另外一种方法:将Pow(x*x,N/2)替换为Pow(x,N/2)*Pow(x,N/2),求时间复杂度。

$T(0)=1$

$T(N)=2*T(N/2)+1$

$T(2) = 2*T(1)+1=3$

$T(4)=2*T(2)+1=7$

$T(8)=2*T(4)+1=15$

$T(2^k) = 2^{k+1}-1$

$N = 2^k$

$T(N)=2^{logN+1}-1=2N-1=O(N)$

粗心的使用递归的后果

幂运算时,不能用Pow(Pow(x,2),N/2)来递归,因为如果N=2那么会产生一个无限循环。


一个小问题:

在测试算法过程中写了一段这样的代码:

1
2
3
4
5
6
long starTime = System.nanoTime();
long endTime1 = System.nanoTime();
long endTime2 = System.nanoTime();
System.out.println("algorithm1 cost time: "+(endTime1-starTime));
System.out.println("algorithm2 cost time: "+(endTime2-endTime1));

输出不确定:

1
2
algorithm1 cost time: 892
algorithm2 cost time: 0
1
2
algorithm1 cost time: 446
algorithm2 cost time: 0
1
2
algorithm1 cost time: 0
algorithm2 cost time: 446
1
2
3
//这种情况比较少出现
algorithm1 cost time: 446
algorithm2 cost time: 447

Why?

还有,发现System.out.println消耗的时间比一个算法消耗的时间大很多,而且第二次调用System.out.println要比第一次少一个数量级(少数情况出现比第一次还多的情况)。