An Interest In:
Web News this Week
- April 2, 2024
- April 1, 2024
- March 31, 2024
- March 30, 2024
- March 29, 2024
- March 28, 2024
- March 27, 2024
Speed of algorithms (with cats)
Let's see how programmers evaluate fast and slow algorithms. Since the topic is pretty boring, we'll use silly cat examples.
Constant time: O(1)
This is your best option. The algorithm speed does not depend on the number of cats.
Example
You are the lucky owner of N
cats. Every kitten knows their name. If you call "Felix!", only one will come running, and the rest of the N-1
fluffs don't care.
Logarithmic time: O(logn)
On N
cats the algorithm completes in log(N)
steps. It's fast! 1,000,000 kittens 20 operations total.
Example
Cat's bowls are arranged alphabetically. When you adopt a new cat, the place for its bowl can be found in log(N)
steps.
Linear time: O(n)
On N
cats the algorithm completes in N
steps. It means that every time you have to traverse all cats. Not great, not terrible.
Example
Your kittens rebelled and stopped responding to nicknames. Now you have to look through N
fluffs to find the right one.
Log-linear time: O(nlogn)
On N
cats the algorithm completes in N
log(N)
steps. This is slower than in linear time, but not by much (the logarithm of N
is much smaller than N
, remember?).
Example
Waiting for guests, you decided to seat kittens in the order of their size. The quick sort algorithm will handle this in N
log(N)
steps.
Next in line, we have lazy polynomial cats and snail-speed superpolynomial ones.
Quadratic time: O(n)
On N
cats the algorithm completes in N
steps. So slow.
Example
Your competitor claims that his N
kittens are smoother and happier than yours. A special commission will compare the cats in pairs and make a fair verdict. You will need ~N
comparisons.
Polynomial time: O(n)
On N
cats the algorithm completes in N
steps, N
steps, N
steps, or even longer. Ugh. Don't be like that.
Example
Photoshoot! Each of the N
kittens will be photographed in pairs with others, and the photographer takes N
pictures for each pair. N
N
N
N
steps.
Polynomial algorithms are not famous for their speed. But compared to superpolynomial ones, they are as fast as a Flash. Sadly, the only "super" part of superpolynomial algorithms is a name. Let me show you.
Exponential time: O(2)
On N
cats the algorithm completes in 2
steps. It's a long time, you're probably not gonna wait.
Example
Kittens are going to the cat show. Everyone will be weighed and rated in stars. But the cat transport can handle a maximum of X kilograms (or pounds). How to choose the most stellar cast? The answer will require 2
steps.
Factorial time: O(n!)
On N
cats the algorithm completes in N
(N-1)
(N-2)
... 1
steps. This is crazy! With 20 cats it's already a couple of quintillion operations.
Example
Kittens spread out across the apartment. You want to pet everyone, but you're lazy and don't like walking. What is the shortest route to visit all fluffs? This is ~N!
comparisons.
Summary
Here are the algorithms we've covered:
- Constant
O(1)
- Logarithmic
O(log n)
- Linear
O(n)
- Log-Linear
O(n log n)
- Quadratic
O(n)
- Polynomial
O(n)
- Exponential
O(2)
- Factorial
O(n!)
A constant algorithm is always the best option, and a logarithmic one is almost always. Linear and polynomial ones are more complex it all depends on the task with them. Sometimes it's a shame to choose O(n)
, and sometimes O(n)
is a huge success.
O(2)
and O(n!)
are insanely slow. So in practice, people often use suboptimal but fast algorithms.
Follow @ohmypy on Twitter to keep up with new posts
Original Link: https://dev.to/nalgeon/speed-of-algorithms-with-cats-2703
Dev To
An online community for sharing and discovering great ideas, having debates, and making friendsMore About this Source Visit Dev To