101
$\begingroup$

I have been wondering about this question since I was an undergraduate student. It is a general question but I will elaborate with examples below.

I have seen a lot of algorithms - for example, for maximum flow problems, I know around 3 algorithms which can solve the problem: Ford-Fulkerson, Edmonds-Karp & Dinic, with Dinic having the best complexity.

For data structures - for example, heaps - there are binary heaps, binomial heaps & Fibonacci heaps, with Fibonacci heap having the best overall complexity.

What keeps me confusing is: are there any reasons why we need to know them all? Why not just learn and get familiar with the best complexity one?

I know it is the best if we know them all, I just want to know are there any "more valid" reasons, like some problems / algorithms can only be solved by using A but not B, etc.

Improve this question
$\endgroup$
5
  • 17
    $\begingroup$ As I always say: these (usually) is no "best". Once you define explicitly what you mean by "better", the answer becomes obvious. $\endgroup$
    – Raphael ♦
    Feb 17, 2016 at 11:12
  • 2
    $\begingroup$ This is a good question, but it speaks to what I would consider a hole in your education you might look into correcting. That is practical experience, if you haven't actually written these algorithms during your education, you might consider writing them now, I suspect the answer to this question would have become quickly obvious as you tried to find uses for them. $\endgroup$
    – Sam
    Feb 18, 2016 at 16:52
  • $\begingroup$ @Sam From my experience, what I thought is that in lectures, or some textbooks, they are informative, introduce many algorithms, the analysis, etc., but not many practical cases or sample scenarios that A will outplay B. They may cover a genre of algorithms A to Z, and some homework problems, but to me they can all solved by A only, or by Z only, etc., thus the question asked. $\endgroup$
    – shole
    Feb 19, 2016 at 3:37
  • 5
    $\begingroup$ If you insist on leaving academic interest aside the best practical reason to learn less than optimal algorithms is so you can recognize them for what they are and optimize them by refactoring to the optimal ones. You can't upgrade a bow and arrow to a gun if you don't know what a bow and arrow are even for. $\endgroup$
    – candied_orange
    Feb 21, 2016 at 14:26
  • 1
    $\begingroup$ We've actually proposed a StackExchange site to specifically help with CS education questions like this one. Come support us here: area51.stackexchange.com/proposals/92460/… $\endgroup$
    – vk2015
    Jun 9, 2016 at 14:44

5 Answers 5

Reset to default
129
$\begingroup$

There's a textbook waiting to be written at some point, with the working title Data Structures, Algorithms, and Tradeoffs. Almost every algorithm or data structure which you're likely to learn at the undergraduate level has some feature which makes it better for some applications than others.

Let's take sorting as an example, since everyone is familiar with the standard sort algorithms.

First off, complexity isn't the only concern. In practice, constant factors matter, which is why (say) quick sort tends to be used more than heap sort even though quick sort has terrible worst-case complexity.

Secondly, there's always the chance that you find yourself in a situation where you're programming under strange constraints. I once had to do quantile extraction from a modest-sized (1000 or so) collection of samples as fast as possible, but it was on a small microcontroller which had very little spare read-write memory, so that ruled out most $O(n \log n)$ sort algorithms. Shell sort was the best tradeoff, since it was sub-quadratic and didn't require additional memory.

In other cases, ideas from an algorithm or data structure might be applicable to a special-purpose problem. Bubble sort seems to be always slower than insertion sort on real hardware, but the idea of performing a bubble pass is sometimes exactly what you need.

Consider, for example, some kind of 3D visualisation or video game on a modern video card, where you'd like to draw objects in order from closest-to-the-camera to furthest-from-the-camera for performance reasons, but if you don't get the order exact, the hardware will take care of it. If you're moving around the 3D environment, the relative order of objects won't change very much between frames, so performing one bubble pass every frame might be a reasonable tradeoff. (The Source engine by Valve does this for particle effects.)

There's persistence, concurrency, cache locality, scalability onto a cluster/cloud, and a host of other possible reasons why one data structure or algorithm may be more appropriate than another even given the same computational complexity for the operations that you care about.

Having said that, that doesn't mean that you should memorise a bunch of algorithms and data structures just in case. Most of the battle is realising that there is a tradeoff to be exploited in the first place, and knowing where to look if you think there might be something appropriate.

Improve this answer
$\endgroup$
14
  • 7
    $\begingroup$ Great answer with great examples! Didn't know even bubble pass has its practical use in real world... $\endgroup$
    – shole
    Feb 17, 2016 at 6:51
  • 1
    $\begingroup$ @shole I don't have a lot of experience in the game business, but all of the above are important to varying degrees. (Obviously, the sort of algorithms, data structures, and maths that you need for games are probably different from those required for databases or bioinformatics or what have you.) If I were you, I'd go here and start watching: handmadehero.org Also it may be worth lurking on gamedev.stackexchange.com $\endgroup$
    – Pseudonym ♦
    Feb 17, 2016 at 9:52
  • 2
    $\begingroup$ Cache efficiency is a big factor that is heavily underresearched (google "memory wall"). $\endgroup$
    – Raphael ♦
    Feb 17, 2016 at 11:14
  • 6
    $\begingroup$ Careful, Quicksort is much faster on average than Heapsort, but Heapsort is more consistent (it's variance of running time is less, and the worst case is much better). And Heapsort's jumping around in the array versus Quicksort's linear scans from left and right make a huge difference once cache/paging comes into play. $\endgroup$
    – vonbrand
    Feb 17, 2016 at 14:17
  • 1
    $\begingroup$ @shole What sort of game development are you interested in? There's at least two very different sub-fields, 3D graphics and gameplay (which includes AI). I only have experience with graphics, but I can say that data structures and mathematics are extremely important in graphics, and algorithms as well to a lesser-extent. If you're using an engine most of this stuff will of course be taken care of, but you should still understand the basic mathematics of 3D geometry. $\endgroup$
    – gardenhead
    Feb 17, 2016 at 16:26
52
$\begingroup$

Aside from the fact that there are myriads of cost measures (running time, memory usage, cache misses, branch mispredictions, implementation complexity, feasibility of verification...) on myriads of machine models (TM, RAM, PRAM,...), average-vs-worst-case as well as amortization considerations to weigh against each other, there are often also functional differences beyond the scope of the basic textbook specification.

Some examples:

  • Mergesort is stable where Quicksort is not.
  • Binary search trees give you in-order iteration, hashtables do not.
  • Bellman-Ford can deal with negative edge weights, Dijkstra can not.

There are also didactic considerations to make:

  • How easy is it to understand a more involved solution before simpler ones? (AVL trees (and their analysis) without BSTs; Dinic without Ford-Fulkerson; ...)
  • Do you see the same principles and patterns when you are exposed to only one solution per problem compared to being exposed to many solutions?
  • Does exposition to only one solution per problem provide enough training (towards mastery)?
  • Should you know the breadth of which solutions have been found (so as to prevent you from reinventing the wheel over and over¹)?
  • When exposed to only one solution per problem, will you understand other solutions you find in the wild (say, in a real-world programming library)?
  1. This is something we see a lot from programmer types who do not have a rich CS toolbox at their disposal.
Improve this answer
$\endgroup$
4
  • 4
    $\begingroup$ +1 for including didactic rationales! Related to several of the rationales (especially the second and third), seeing how algorithms and data structures are developed and optimized teaches development and optimization techniques and an understanding of tradeoffs (learning not just "what" but also "how" and "why"). $\endgroup$
    – user4577
    Feb 17, 2016 at 13:57
  • 2
    $\begingroup$ One further consideration is that analyzing the different alternatives offers examples of useful tools for analysis new algorithms for perhaps unusual settings. $\endgroup$
    – vonbrand
    Feb 17, 2016 at 14:24
  • 1
    $\begingroup$ Good point, @vonbrand. Amortised complexity analysis was invented to understand the behaviour of splay trees, but splay trees are rarely used in practice. Well, not splay trees as published, anyway. The Windows NT kernel famously uses splay trees to implement virtual memory maps, but it doesn't reorder on every lookup. $\endgroup$
    – Pseudonym ♦
    Feb 17, 2016 at 22:49
  • 1
    $\begingroup$ @vonbrand Yes. I would understand how somebody mostly interested in the toolbox-dimension on an algorithms class would scoff at that reason, though. $\endgroup$
    – Raphael ♦
    Feb 18, 2016 at 7:22
7
$\begingroup$

In the real world, at some point you are likely to be working on software that has been written by a team of other people. Some of this software will have been written before you were born!

So as to understand the algorithms / data structures that are used, it is very helpful to know a large number of algorithms / data structures, including options that are no longer consider “state of the art”.

You will also have to work on algorithms that are not standard and are just used in the application you are working on. When you have to improve these algorithms, you will find that your brain has been filled with useful methods to improve algorithms, as you have studied how other people have improved algorithms.

This is what sets somebody who has studied computer science apart from someone that has just learned how to program. In most jobs I have worked in, there has been time when having studied computer science I could solve a problem that a “learned from books” programmer could not, but 95% of the time I found that having studied computer science gave me no advantage over other experienced programmers.

Improve this answer
$\endgroup$
3
  • $\begingroup$ unless 95% of the things you are trying to solve are related to Machine learning. I can't see how normal programer can even have the right chance to attempt any of the problems faced by real ML problems. $\endgroup$
    – Charlie Parker
    Feb 18, 2016 at 17:52
  • 3
    $\begingroup$ Goal: get a job with a better rate than 5%. $\endgroup$
    – Raphael ♦
    Feb 18, 2016 at 19:39
  • $\begingroup$ Remember that studying CS has been a great way of gathering knowledge about algorithms&data structures. Coding is the best occupation - for coders. $\endgroup$
    – greybeard
    Feb 19, 2016 at 8:38
5
$\begingroup$

Many people have rightly mentioned that often there's no one best algorithm - it depends on the situation.

There's also the possibility that one day you'll come across an unfamiliar situation. The more algorithms you know, the more chance that you'll know one that's nearly a solution that you can use as a base.

Improve this answer
$\endgroup$
1
  • 5
    $\begingroup$ This answer only repeats points from older ones. $\endgroup$
    – Raphael ♦
    Feb 19, 2016 at 12:39
2
$\begingroup$

A lot of great answers, just something I think is missing, though Raphael's answer somewhat mentions this.

Ease of implementation is also something to take into consideration.
That's usually not an issue with sort algorithms, because most platforms/languages already have one implemented (and often better than what you could do), but more unusual algorithms might not be available.
Depending on your problem, you might not need the absolute best algorithm if the implementation time is 1 day versus 2 weeks.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.