|
Authored by: myNym on Monday, December 31 2012 @ 07:19 PM EST |
When developing an algorithm, you ignore the constants.
So bubble sort uses the exact same algorithm to sort an
array regardless of the size of the array, and the contents
of the array.
If you add a requirement to run the algorithm in a specified
time period, then you will need to estimate what the worst
case is for bubble sort for the largest size array you
expect with the worst case initial conditions, and then
supply the hardware that will run through the algorithm in
the specified time.
The ability of a given algorithm to meet a time deadline in
the worst case input scenario is dependent on the hardware.
I used bubble sort because it's notoriously slow for large
arrays with worst-case starting values.
If we had infinitely fast machines, we would have been
satisfied with bubble sort. We don't, which is why we have
moved on to things like quick sort to handle larger arrays.
But the speed requirement is external to the algorithm.
That's a real-world hardware requirement, such as "must not
consume more than x watts per hour".
The software doesn't know time, and it doesn't know watts.
An algorithm can count clock cycles, but it cannot know
whether the clock is running at 512 MHz or at 3 GHz. The
whole concept of time and seconds is a human construct.
That's about as clear as I can make it.[ Reply to This | Parent | # ]
|
|
|
|
|