mardi 3 décembre 2013

Delving into Algorithm Analysis - Deducing the Mathematical Representation of a Determined Study Case (I) [Iterative Algorithms and Sigma Notation]

First of all, it is pointless to try to study a constant time algorithm (see isFibonacci() routine below), so we can skip this situation.

For example:
short isFibonacci(int number) {
      int value = 5 * number * number;
      return sqrt(value + 4) == number 
      ||     sqrt(value - 4) == number;
}

Actually, analyses become interesting when we are to manipulate iterative algorithms and recursion.
Indeed, algorithm analysis will merely help us to decide whether the solution we opted for is valid, because it is formally efficient; otherwise, we should try to persevere for extra enhancement.

For my personal experience, I came to realize that I can represent a for loop mathematically using Sigma notation, especially when the loop is regular, and is additionally incremental or subtractively decremental.

Ascending loop:
    for ( i = k ; i < n ; i += inc ) {
         /*             
          * instructions
          */           
    }
Can be transliterated like the following:


Whereas the following loop (less than or equal):
    for ( i = k ; i <= n ; i += inc ) {
         /*             
          * instructions
          */           
    }
Is accurately represented this way:



Descending loop:
    for ( i = n ; i > k ; i -= inc ) {
         /*             
          * instructions
          */           
    }
Looks like this:



While the loop above:
    for ( i = n ; i >= k ; i -= inc ) {
         /*             
          * instructions
          */           
    }
Would too be translated like the following:


A loop whose increment is an exponent (whether multiplied or divided) is called an logarithmic loop:
    for ( i = k ; i < n ; i *= m ) {
         /*             
          * instructions
          */           
    }
Would be mathematically represented like:




Again, when the less or equal is stated:
    for ( i = k ; i <= n ; i *= m ) {
         /*             
          * instructions
          */           
    }
We end up having:




The same for the other way around case:
    for ( i = n ; i > k ; i /= m) {
         /*             
          * instructions
          */           
    }
Is to be represented this way:




Doing the same when it comes to "less or equal" condition:
    for ( i = n ; i >= k ; i /= m ) {
         /*             
          * instructions
          */           
    }
We get:



This is a preliminary overview that I am sure will help to predict what is going to be covered within the next posts.
These slides from Dr. Jauhar Ali can provide further knowledge about this matter.

Aucun commentaire :

Enregistrer un commentaire