最坏和平均时间复杂度之分133算法分析数据结构Java语言描述.PPT

1.3.4 算法设计比较 【问题描述】给定一整数序列A1， A2，... An （可能有负数），求A1～An的一个子序列Ai～Aj，使得Ai到Aj的和最大。例如：整数序列 -2, 11, -4, 13, -5, 2, -5, -3, 12, -9的最大子序列的和为21（从A2到A9）；整数序列4，-3，5，-2，1，2，6，-2的最大子序列的和为11（从A1到A7）。 下面介绍四种实现方法 方法一: 穷举法(书中算法1.1) public static int maxSub_1(int[] sequence) { } int max = 0; int n= sequence.length; int sum = 0; //第一重循环执行一次则计算出长度为i的所有子序列和的最大值 for (int i = 1; i = n; i++) for (int j = 0; j n; j++) { sum = 0; for (int k = j; k j + i k n; k++) sum += sequence[k]; if (sum max) max = sum; } return max; 时间复杂度: O(n3) 详细分析见 P10 方法二: (书中算法1.2) public static int maxSub_2(int[] sequence) { } int max = 0; int n= sequence.length; int sum = 0; for (int i = 0; i n; i++) { sum = 0; for (int j = i; j n; j++) { sum += sequence[j]; //关键操作 if (sum max) max = sum; } return max; 时间复杂度: O(n2) 4 ?3 5 ?2 ?1 2 6 ?2 结果 分治 4 5 6 2 6 8 11 T (n/2 ) T ( n/2 ) O( n ) T ( n ) = 2 T( n/2 ) + n , T(1) = O(1) = 2 [2 T( n/22 ) + n/2] + n = 2k O(1) + k n 当 N/2k = 1时 = O( n log n ) Also true for N ? 2k 算法见P22/算法1.3 方法三: 分治法 时间复杂度: O(nlogn) 方法四: 动态规划法(书中算法1.4) public static int maxSub_4(int[] sequence) { } int max = 0; int n= sequence.length; int sum = 0; for (int i = 0; i n; i++) { sum += sequence[i]; if (sum max) max = sum; else if (sum 0) sum = 0; } return max; 时间复杂度: O(n) ?1 3 ?2 4 ?6 1 6 ?1 ?1 3 ?2 4 ?6 若除去数据对象的基本类型外，实现方法相同的，则可用泛型方法来描述这种基本功能。 1.使用Object表示泛型 2.使用Comparable接口类型表示泛型 1.4 Java提供的泛型方法 1.使用Object表示泛型 【例1】 两个数的置换算法（要求方法与与被置换的数据对象的类型无关） public static void swap(Object a, Object b){ Object temp=a; a=b; b=tmep; } 1.使用Object表示泛型 【注意】 1.为了访问这种对象的一个特定方法，必须首先要强制转换成正确的类型。 2.基本类型不能作为Object类进行传递。因为只有引用类型能够与Object类相容，而Java中的8种基本类型都不能。 解决方法：利用Java为这8种基本类型的每 一个所提供的