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
- 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
- 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.
- 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
2 2
3 3
4 7
5 10
6 15
7 21
- n people need 0.5( n^2 -2) handshakes
- As one increases the other increases more rapidly
http://en.wikipedia.org/wiki/File:Bubble_sort_animation.gif |
- 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
- The emperor was going to lose his throne to an invading army, he asked for help from a neighbouring war lord.
- 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
- 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.
- 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.
- On the first row there was 225 grains of rice, on the second 65280 grains of rice, on the third 963040.
- There were several hundred times the amount of rice on the last square on the chessboard alone then there were rice produce by China.
- 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 |
I think your handshake analogy is wrong.
ReplyDeletehttps://www.youtube.com/watch?v=dIejOnMP20c