数据结构chapter2-new幻灯片.PPT

2.2 Time Complexity Example 1: Selection sort a[0],a[1],…,a[n-1] Frequency for (int i=0 ; i n-1 ; i++) n { int k= i; n-1 for (int j=i+1; jn ; j++) (n2+n-2)/2 if (a[j]a[k]) k=j; =(n2-n)/2 int temp=a[i]; a[i]=a[k]; a[k]=temp; 3(n-1) } T(n) = n2+5*n-5 n---? T(n)/n2-----constants(1) T(n) = O(n2) 2.2 Time Complexity Example 2: Binary Search 0 1 2 3 4 5 6 7 8 a: -1 0 1 3 4 6 8 10 12 x = 6 public static int bonarySearch( Comparable [ ] a, Comparable x ) { int low = 0, high = a.length - 1; while( low = high ) { int mid = ( low + high ) / 2; if( a[ mid ].compareTo( x ) 0 ) low = mid + 1; else if( a[mid ].compareTo( x ) 0 ) high = mid – 1; else return mid; } return NOT-FOUND; } 最好: 一次 最坏: log2n 平均 O(log2n) 2.2 Time Complexity Example 3: MAXIMUM SUBSEQUNCE SUM PROBLEM 给定整数a1,a2,…,an(可能有负数），求∑ak的最大值。 如果所有整数均为负数，则最大子序列和为0。 j k=i 1 2 3 4 5 6 a: -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 a.length; i++ ) for ( int j = i; j a.length; j++ ) { int thisSum = 0; for ( int k = i; k = j; k++ ) thisSum += a[k]; if ( thisSum maxSum ) maxSum = thisSum; } return maxSum; } 2.2 Time Complexity analysis O(N3) 2.2 Time Complexity Algorithm 2: public static int maxSubSum2( int [ ] a ) { int maxSum = 0; for( int i = 0; i a.length; i++ ) { int thisSum =