3 ms·
In the real world, we care about runtime as much as, if not more than, computational complexity.
by dekhn 3y ago
In the real world, we care about runtime as much as, if not more than, computational complexity.
- boomanaiden154 3y agoDefinitely more. There are lots of things that might be more optimal in terms of raw complexity but end up having abysmal performance due to things like cache locality. Anything with pointer chasing usually kills performance.
- xdavidliu 3y agofor example, matrix multiplication has all sorts of algorithms with exponent significantly less than 3, but they are nearly all curiosities. In practice, the straightforward N^3 algo is used nearly everywhere
- dekhn 3y agoI had a long discussion with Rob Pike once that ended with me saying "you know, I don't think people actually use Strassen on supercomputers" (we were discussing how somebody had managed to show an N*2.37 algorithm or something like that and "it was a new world's record").