Problem Solving: Big O Notation
From the Specification : Big-O Notation
|
Big O Notation (also known as Big-O Notation) is a mathematical way of describing the limiting behaviours of a function. In other words, it is a way of defining how efficient an algorithm is by how "fast" it will run.
Timing edit
You can work out the time that an algorithm takes to run by timing it:
Dim timer As New Stopwatch()
timer.Start()
For x = 1 to 1000000000
'count to one billion!
Next
timer.Stop()
' Get the elapsed time as a TimeSpan value.
Dim el As TimeSpan = stopWatch.Elapsed
' Format and display the TimeSpan value.
Dim formattedTime As String = String.Format("{0}:{1}:{2}.{3}", el.Hours, el.Minutes, el.Seconds, el.Milliseconds / 10)
Console.WriteLine( "Time Elapsed: " + formattedTime)
Code Output
Time Elapsed: 0:0:21:3249
However, this isn't always suitable. What happens if you run some code on a 33 MHz processor, and some code on a 3.4 GHz processor. Timing a function tells you a lot about the speed of a computer and very little about the speed of an algorithm.
Refining algorithms edit
dim N as integer = 7483647
dim sum as double= 0
for i = 1 to N
sum = sum + i
loop
console.writeline(sum)
optimised version
dim N as integer = 7483647
dim sum as double = N * (1 + N) / 2
console.writeline(sum)
Order of Complexity edit
Notation | Name | Example |
---|---|---|
constant | Determining if a number is even or odd; using a constant-size lookup table | |
logarithmic | Finding an item in a sorted array with a binary search or a balanced search tree as well as all operations in a Binomial heap. | |
linear | Finding an item in an unsorted list or a malformed tree (worst case) or in an unsorted array; Adding two n-bit integers by ripple carry. | |
linearithmic, loglinear, or quasilinear | Performing a Fast Fourier transform; heapsort, quicksort (best and average case), or merge sort | |
quadratic | Multiplying two n-digit numbers by a simple algorithm; bubble sort (worst case or naive implementation), Shell sort, quicksort (worst case), selection sort or insertion sort | |
polynomial or algebraic | Tree-adjoining grammar parsing; maximum matching for bipartite graphs | |
exponential | Finding the (exact) solution to the travelling salesman problem using dynamic programming; determining if two logical statements are equivalent using brute-force search | |
factorial | Solving the travelling salesman problem via brute-force search; generating all unrestricted permutations of a poset; finding the determinant with expansion by minors. |