3. Algoritme-analyse

Vi skal hovedsaklig ta for oss kjøretidsutviklingen for algoritmer.

3.1 Maximum subsequence - problemet, løsning 1

int maxSubSum1( const vector<int> & a) {
 int maxSum = 0;



   for ( int i = 0; i < a.size(); i++)



    for ( int j = i; j < a.size(); j++) {



       int thisSum = 0;






         for (int k = i; k <= j; k++)



          thisSum += a[ k ];






         if ( thisSum > maxSum )



          maxSum = thisSum;



      }



   return maxSum;



}




Denne algoritmen har tre nøstede for-løkker, og hvis vi
ikke skal flikke for mye på det, kan vi si at kjøretidsutviklingen
er kubisk, dvs. O(N^3).







3.2 Maximum subsequence - problemet, løsning 2



int maxSubSum2( const vector<int> & a)



{



/* 1 */ int maxSum = 0;






/* 2 */   for (int i = 0; i < a.size(); i++)



          {



/* 3 */    int thisSum = 0;



/* 4 */      for (int j = i; j < a.size(); j++)



             {



/* 5 */       thisSum += a[ j ];






/* 6 */         if (thisSum > maxSum)



/* 7 */          maxSum = thisSum;



              }



           }



/* 8 */ return maxSum;



}

Linjene 5 - 8 utføres ca (N^2) / 2 ganger (summen av rekken 1 til
N).

O(N^2). Dette er en worst-case, men O-notasjonen skal beskrive en kjøretid
vi ikke overskrider. Denne algoritmen er likevel en enorm forbedring i
forhold til den første (1000 ganger bedre).







3.3 Maximum subsequence - problemet, løsning 3



int maxSumRec( const vector<int> & a, int left, int right )



{



 if ( left == right ) // Base case



    if ( a [ left ] > 0 )



       return a [ left ];



      else



       return 0;






   int center = ( 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 += a [ i ];



      if ( leftBorderSum > maxLeftBorderSum )



       maxLeftBorderSum = leftBorderSum;



   }






   int maxRightBorderSum = 0, rightBorderSum = 0;



   for ( int j = center + 1; j <= right; j++)



   {



    rightBorderSum += a [ j ];



      if ( rightBorderSum > maxRightBorderSum )



       maxRightBorderSum = rightBorderSum;



   }






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



}

Denne algortimen er rekursiv.

T(1)  = 1        -- hvor lang
tid tar det å kjøre denne algoritmen med ett element (base
case)

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

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

T(4)  = 2*T(2) + 4                 
= 12    = 4*2 + 4

T(8)  = 2*T(4) + 8                 
= 32    = 8*3 + 8

T(9)  = 2*T(8) + 16               
= 80    =16*4 + 16


T(N) = k * N + N

N = 2^k   --> k = log N


T(N) = N * log N + N    - kjøretiden


For å lage O-notasjon kutter vi ut leddene med lavere orden:

O(N log N)

 


3.4 Maximum subsequence - problemet, løsning 4



int maxSubSum4( const vector<int> & a )



{



 int maxSum = 0, thisSum = 0;






   for (int j = 0; j < a.size(); j++)



   {



    thisSum += a[ j ];






      if ( thisSum > maxSum )



       maxSum = thisSum;



      else if ( thisSum < 0 )



       thisSum = 0;



   }



   return maxSum;



}

Algoritmen har én for-løkke, og kjøretiden en O(N)