《数据结构chapter2-new》由会员分享，可在线阅读，更多相关《数据结构chapter2-new（46页珍藏版）》请在金锄头文库上搜索。
1、Chapter 2Algorithm Analysis An algorithm is a clearly specified set of simple instructions to be followed to solve a problem. Algorithm analysis is the amount of computer memory and time needed to run a program (algorithm)We use two approaches to determine it: performance analysis performance measur
2、ementSpace complexity: the amount of memory a program needs to run to completion Time complexity: the amount of time a program needs to run to completion2.1 Space Complexity1)components: instruction space data space (space needed for constants,simple variables,component variables) environment stack
3、space (to save information needed to resume execution of partially completed functions) 2.1 Space Complexitytwo parts:a fixed partinclude space for instructions,simple variables,fixed-size component variables,constantsa variable partinclude space for component variables,dynamical allocated space,rec
4、ursion stackS(p)=c+Sp(instance characteristics)2.1 Space Complexity 2)example: Sequential Search public static int SequentialSearch( int a , int x ) int i;for(i=0; i0 )return Rsum(a, n-1) + an-1;return 0;2.1 Space ComplexityRecursion stack space:formal parameters : a (2 byte), n(2 byte)return addres
5、s(2 byte)Depth of recursion: n+1SRsum(n)=6(n+1)2.2 Time complexityThe time taken by a program p is T(p)T(p)=compile time+run timeThe compile time does not depend on theinstance characteristicsThe run time is denoted by tp(instance characteristics)1)operation counts identify one or more key operation
6、s and determine the number of times these are performed 2.2 Time ComplexityExample 1 finding the largest number in a0:n-1public static int Max( int a, int n)/locate the largest element in a0:n-1int pos=0;for(int i=1;i1; size-) int j=Max(a,size);swap(aj,asize-1);2.2 Time ComplexityAnalysis of selecti
7、on sort1)each invocation Max(a,size)results in size-1 comparisons, so the total number of comparisons is :n-1+n-2+3+2+1=(n-1)*n/22)the number of element move is 3(n-1)2.2 Time ComplexityExample 3 bubble sort8 25 32 15 20 38 46 54 67 public static void Bubble( int a , int n)/Bubble largest element in
8、 a0:n-1 to rightfor(int i=0; iai+1)swap(ai,ai+1);2.2 Time Complexitypublic static void BubbleSort( int a, int n) /Sort a0:n-1 using a bubble sortfor(int i=n ;i1; i-)Bubble(a,i);2.2 Time ComplexityAnalysis of bubble sortthe number of element comparisons is (n-1)*n/2,as for selection sort2.2 Time Comp
9、lexityExample 4 Rank sort r: 0 2 1 4 30 1 2 3 4a: 8 25 16 30 28public static void Rank( int a, int n, int r)/Rank the n elements a0:n-1for(int i=0;i=0 while( low 0 )high = mid 1;else return mid;return NOT-FOUND; 最好: 一次 最坏: log2n 平均 O(log2n)2.2 Time ComplexityExample 3: MAXIMUM SUBSEQUNCE SUM PROBLEM
10、给定整数a1,a2,an(可能有负数），求ak的最大值。如果所有整数均为负数，则最大子序列和为0。jk=i1 2 3 4 5 6a: -2 11 -4 13 -5 -2 Algorithm 1: merely exhaustively tries all possibilities public static int maxSubSum1( int a ) int maxSum = 0;for ( int i = 0; i maxSum )maxSum = thisSum;return maxSum;2.2 Time Complexity analysis O(N3)2.2 Time Comp
11、lexity Algorithm 2: public static int maxSubSum2( int a ) int maxSum = 0;for( int i = 0; i maxSum )maxSum = thisSum;return maxSum; O( N2)2.2 Time ComplexityAlgorithm 3: recursive and relatively complicated O(Nlog N)分治法( divide-and-conquer)分阶段：把问题分成两个大致相等的子问题，然后递归 地 对它们求解。治阶段： 将两个子问题的解合并到一起，可能再做些少 量的
12、附加工作，最后得到整个问题的解。example:4 -3 5 -2 -1 2 6 -2a1 a2 a3 a4 a5 a6 a7 a8a1-a4 的最大子序列和为6, a1-a3a5-a8 的最大子序列和为8, a6-a7横跨这两部分且通过中间的最大和为：a1-a3+a4 + a5+ a6-a7 = 112.2 Time Complexityprivate static int maxSumRec( int a, int left, int right ) if ( left = = right )if ( a left 0 )return a left ;else return 0;int c
13、enter = ( left + right ) / 2;int maxLeftSum = maxSumRec( a, left, center );int maxRightSum = maxSumRec( a, center + 1, right );int maxLeftBorderSum = 0, leftBorderSum = 0;for ( int i = center; i = left; i- ) leftBorderSum += ai;if ( leftBordersum maxLeftBorderSum )maxLeftBorderSum = leftBorderSum; 2
14、.2 Time Complexityint maxRightBorderSum = 0, rightBorderSum = 0;for ( int i = center + 1; i maxRightBorderSum )maxRightBorderSum = rightBorderSum;return max3( maxLeftSum, maxRightSun, maxLeftBorderSum + maxRightBorderSum );public static int maxSubSum3( int a ) return maxSumRec( a, 0, a.length 1 ); analysis:O(N logN)2.2 Time ComplexityExample 4: Euclids Algorithm计算最大公因数(greatest common divisor)。 通过转转相除。例如 50, 15 的最大公因数是5 public static long gcd( long m, long n ) while( n != 0 ) long rem = m % n;m = n;n = rem;return m; O( log N)2.2 Time ComplexityII).Omega Notation ():
