(数据结构与算法分析笔记)第二章 算法分析

java
概述

算法是为求解一个问题需要遵循的,被清楚指定的简单指令的集合。对于一个问题，一旦某种算法给定并且被确定是正确的，那么最重要的一步是确定该算法将需要多少时间和空间等资源量的问题.

数学基础

定义1：如果存在正常数$c$和$n_0$使得当$N \geq n_0$时 $T(N) \leq cf(N)$,则记为： $T(N) = O(f(N))$
定义2：如果存在正常数$c$和$n_0$使得当$N \geq n$时 $T(N) \geq cf(N)$,则记为： $T(N) = \Omega(f(N))$
定义3：$T(N) = \Theta(h(N))$当且仅当$T(N) = O(h(N))$和$T(N) = \Omega(h(N))$
定义4:如果对每一正常数$c$都存在常数$n_0$使得当$N>n_0$时$T(N) < cp(N)$,则$T(N) = o(p(N))$。有时也说如果$T(N) = O(P)$且 $T(N) \neq \Theta(N)$

一般而言，对给定的两个函数，我们需要比较的是相对增长率

法则1：如果$T_1(N) = O(f(N))$且$T_2(N) = O(g(N))$，那么$T_1(N)+T_2(N) = O(f(N))+O(g(N))$或者$T_1(N)T_2(N) = O(f(N)g(N))$
法则2：如果$T(N)$是一个k次多项式，则$T(N) = \Theta(N^k)$
法则3：对任意常数$k$，$\log^kN = O(N)$

运行时间计算

法则1：for循环—-一个for循环的运行时间至多是该for循环内部那些语句的运行时间乘以迭代的次数
法则二：嵌套for循环—-从里向外，在一组嵌套环内部的一条语句总的运行时间为该语句的运行时间乘上该组所有for循环的大小的乘积

1
2
3
4
5
for( j = 0;j<n;j++){
     for( k = 0;k<n;k++ ){
           a[k] = i;
     }
  }

法则三 : 顺序语句—-将各个语句的运行时间求和

1
2
3
4
5
6
7
8
9
for( i = 0;i<n;i++ ){
     a[i] = i;   
}

for( j = 0;j<n;j++){
   for( k = 0;k<n;k++ ){
         a[k] = i;
   }
}

法则四 : if/else语句—-一个if/else语句运行时间总不超过判断的运行时间再加上S1和S2Z中运行时间长者的总的运行时间

1
2
3
4
5
if(condition){
   S1
}else{
   S2
}

要分析的问题

分析算法的运行时间，算法最坏情形的性能最能代表对任何可能的输入的性能的一种保证

最大子序列和问题

问题：给定(可能为负)整数$A_1,A_2,A_3 \cdots AN$,求$\sum{k=i}^j A_k$的最大值，并假设所有的整数均为负数时，则最大子序列和为0
解法一：运算时间： $T(N) = O(N^3)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
  //int[] test = new int[] { 4, -3, 5, -2, -1, 2, 6, -2 };
  public static int maxSum1(int [] a){
	int max = 0;
	for(int i = 0;i<a.length;i++){
		for(int j = 0;j<a.length;j++){
			
			int childMax = 0;
			for(int k = i;k<=j;k++){
				childMax += a[k];
			}
			
			if(childMax > max){
				max = childMax;
			}
		}
	}
	
	return max;
}

解法二：运算时间： $T(N) = O(N^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//int[] test = new int[] { 4, -3, 5, -2, -1, 2, 6, -2 };
public static int maxSum2(int [] a){
		int max = 0;
		for(int i = 0;i<a.length;i++){
			int childMax = 0;
			for(int j = i;j<a.length;j++){
				childMax += a[j];
				if(childMax > max){
					max = childMax;
				}
			}
		}
		
		return max;
	}

解法三：运算时间： $T(N) = O(N \log N)$

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
36
37
38
39
40
41
42
43
44
45
46
47
48
   //int[] test = new int[] { 4, -3, 5, -2, -1, 2, 6, -2 };
   //maxSum3(test,0,test.length-1)
public static int maxSum3(int[] a, int left, int right) {
	if (left == right) {
		if (a[left] > 0) {
			return a[left];
		}
		return 0;
	}

	int center = (left + right) / 2;
	int maxLeftSum = maxSum3(a, left, center);
	int maxRightSUm = maxSum3(a, center + 1, right);

	int maxLeftBorderSum = 0;
	int LeftBorderSum = 0;
	for (int i = center; i >= left; i--) {
		LeftBorderSum += a[i];
		if (LeftBorderSum > maxLeftBorderSum) {
			maxLeftBorderSum = LeftBorderSum;
		}
	}

	int maxRightBorderSum = 0;
	int RightBorderSum = 0;
	for (int i = center + 1; i <= right; i++) {
		RightBorderSum += a[i];
		if (RightBorderSum > maxRightBorderSum) {
			maxRightBorderSum = RightBorderSum;
		}
	}

	return max3(maxLeftBorderSum, maxRightBorderSum, maxLeftBorderSum + maxRightBorderSum);

}

public static int max3(int a, int b, int c) {
	int max = a;
	if (b > max) {
		max = b;
	}

	if (c > max) {
		max = c;
	}

	return max;
}

解法四：只对数据进行一次扫面，一旦a[i]被读入并被处理就不在需要记忆。在任何时刻，算法都能对他读入的数据给予子序列问题的正确的答案，以上三种算法都不具备这个性能，具有这种特性的算法也叫做联机算法，仅需要常量的空间并以线性时间运行的联机算法几乎是完美的算法。运算时间： $T(N) = O(N)$

1
2
3
4
5
6
7
8
9
10
11
12
13
//int[] test = new int[] { 4, -3, 5, -2, -1, 2, 6, -2 };
public static int maxSum4(int[] a) {
		int max = 0;
		int childMax = 0;
		for (int i = 0; i < a.length; i++) {
			childMax += a[i];
			if (childMax > max) {
				max = childMax;
			}
		}

		return max;
	}

运行时间中的对数

如果一个算法用常数时间$O(1)$将问题的大小削减为其一部分（通常为1/2），那么该算法就是$O( \log N)$。另一方面，如果使用常数时间只是把问题减少一个常数的数量，那么这种算法就是$O(N)$

折半查找

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
public class JavaTest {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		List<BinarySearch> mdatas = new ArrayList<BinarySearch>();
		for (int i = 0; i < 1000000; i++) {
			mdatas.add(new BinarySearch(i));
		}
		System.out.println(binarySearch(mdatas, new BinarySearch(556)));
	}

	public static class BinarySearch implements Comparable {
		private int mNum = 0;

		public BinarySearch(int num) {
			mNum = num;
		}
		
		public int getNum(){
			return mNum;
		}

		@Override
		public int compareTo(Object o) {
			// TODO Auto-generated method stub
			int target = ((BinarySearch) o).getNum();
			if (target > mNum) {
				return -1;
			}
			if (target < mNum) {
				return 1;
			}
			return 0;
		}
	}

	public static <T extends Comparable> int binarySearch(List<T> datas, T data) {
		int mark = -1;
		int low = 0;
		int hight = datas.size() - 1;
		while (low <= hight) {
			int mid = (low + hight) / 2;
			if (datas.get(mid).compareTo(data) > 0) {
				hight = mid;
			} else if (datas.get(mid).compareTo(data) < 0) {
				low = mid;
			} else {
				return mid;
			}
		}
		return mark;
	}

}

欧几里得算法
欧几里得算法是计算最大公因子的算法，两个整数的最大公因子是同时整除二者的最大整数

定理： 如果M > N , 则 M mod N < M/2

1
2
3
4
5
6
7
8
9
public static long gcd(long m, long n) {
		while (n != 0) {
            long rem  = m % n;
            m = n;
            n =rem;
		}
		
		return m;
	}

幂运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static long pow(long x, int n) {
	if (n == 0) {
		return 1;
	}
	
	if(n == 1){
		return x;
	}

	if ((n % 2) == 0) {
		return pow(x * x, n / 2);
	}

	if ((n % 2) == 1) {
		return pow(x * x, n / 2) * x;
	}

	return 0L;
}

本文标题:(数据结构与算法分析笔记)第二章 算法分析

文章作者:剑客爱编程

发布时间:2016-07-08, 23:49:52

最后更新:2016-07-08, 23:49:52

原始链接:https://iskylove.github.io/2016/07/08/java_datastructures_alogorithm_1/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 概述
  2. 2. 数学基础
  3. 3. 运行时间计算
  4. 4. 要分析的问题
  5. 5. 最大子序列和问题
  6. 6. 运行时间中的对数
,