Tuesday, 13 November 2012

3.1.2 Comparing Algorithms

Comparing Algorithms
Problems with different time complexities

1) Constant complexities
  • O(1)
  • Takes the same amount of time no matter how big the problem is.
  • E.g. Sorting the first 10 records in a file. Or finding if a number is odd or even.
  • IF n mod 2 = 1 THEN odd = true ELSE odd = false
  • Can have more than one action
2) Linear complexity
  • O(n)
  • As the size of the problem increases, the time taken to solve the problem grows at the same rate.
  • E.g. Cutting the grass
  • Less efficent than O(1) complexity algorithms
3) Logarithmic complexity
  • O(log n)
  • As the size of the problem grows, the time taken to solve the problem increases, but at a slower rate.
  • On sorted lists, there are faster searches than the linear search E.g. Binary search
  • Finding an item using the binary search takes on average less time than using the linear search.
4)Polynomial complexity
  • O(nk)
  • As the size of the problem increases, the time taken to solve it grows faster, but can be solved in a reasonable amount of time
  • Includes quadratic and cubic
  • Quadratic= O(n^2)
  • If a group of people need to shake hands then
                        People            Handshakes needed
                        2                    2
                        3                    3
                        4                    7
                        5                    10
                        6                    15
                        7                    21
5) Exponential complexity
  • O(kn)
  • As the size of the problem grows, the time taken to solve it grows by larger and larger amounts.
  • Only small size versions of these problems can be solved in a reasonable amount of time.
  • An example is the Emperor's Chess Board Problem
  1. The emperor was going to lose his throne to an invading army, he asked for help from a neighbouring war lord.
  2. The warlord agreed as long as the pay was good enough. Either 1/4 of China's rice crop for 5 years or the payment via a chess board
  3. On the 1st square would be one grain of rice, on the second square 2 grains of rice, on the third square 4 grains of rice and on the 4th 8 grains of rice, etc.
  4. The emperor chose the chessboard, and when the invading army was defeated the warlord went to collect his payment. The emperor started putting grains of rice on the chessboard.
  5. On the first row there was 225 grains of rice, on the second 65280 grains of rice, on the third 963040.
  6. There were several hundred times the amount of rice on the last square on the chessboard alone then there were rice produce by China.
  7. The emperor was forced to abdicate.
  • This problem although it can be solved, cannot be solved in a reasonable amount of time for anything but the smallest of inputs.



6) Factorial Complexity
  • O(n!)
  • This complexity is even slower than Exponential Complexity,
  • An example of this is the Travelling Salesman Problem
  • It cannot be solved in a reasonable amount of time.
  • The Travelling Salesman Problem uses the brute forcve method (looks at all routes for the shortest)

            Cities            Possibilities            Time taken to solve
            3                   1                           1 nanosecond
            4                   3                           3 nanosecond
            5                   12                         12 nanosecond
            6                   60                         60 nanosecond
            7                   2520                     0.001814400 seconds
            16                 181440                 11 mins
           
  • It is possible to solve the problem in an exponetial way using other methods



Agraph showing the reltionship between the size of a problem and the time taken to solve the problem



   





1 comment:

  1. I think your handshake analogy is wrong.

    https://www.youtube.com/watch?v=dIejOnMP20c

    ReplyDelete