4 ms·
From the product website: >> Wish that O(n^3) algorithm could execute in real-time? Now it's possible! We encourage you to push the limits of our platform and
by daniel-levin 13y ago
From the product website:
>> Wish that O(n^3) algorithm could execute in real-time? Now it's possible! We encourage you to push the limits of our platform and disregard what was previously intractable.
One of the most important things to note about asymptotic analysis is that the speed of your computer is immaterial. An O(n^3) algorithm will experience cubic slowdown, irrespective of how it's implemented. A blazing fast, parallelised solution just reduces the constant multiple in front of the n^3, but ultimately, n^3 will outgrow that constant. I'm sure you know this, but it's disingenuous to say that you can disregard an algorithm's complexity because of your data / results. A particular algorithm with particular space complexity (also important) was run on a particular input and was much faster - granted, this is impressive - but not definitive enough to justify labels like '1000x faster' and 'disregard what was previously intractable'.
Also, O(n^3) is considered polynomial, which is absolutely not intractable. The whole point of intractable problems is that they are too complex to solve (given current best known methods). This might be very useful for applications that are currently too slow to run in real-time, but absolutely not a solution to problems of much higher order (read: non-polynomial) complexity
- Hydraulix989 13y agoRight, we're not changing the complexity itself, N-ary parallelization in the ideal case modifies the runtime s.t. C' = C_0 / N.
- daniel-levin 13y agoBy Amdahl's law, that idealisation assumes that your program is totally parallelisable. Very few real world applications actually are. Out of interest, was yours? (Or at least very close to it?)
- Hydraulix989 13y agoYes, our algorithm performed an O(N^2) loop over the graph vertices so B for us was very close to 1.
- daniel-levin 13y agoOK, but I think you mean B was close to zero then?
- Hydraulix989 13y agoFair enough.
- sanskritabelt 13y agoIf this is the Moyes algorithm which does graph clustering I think you have to ask yourself a couple of things: 1. can a parallel algorithm that optimizes each node individually get the same result as a serial algorithm that optimizes them sequentially (this is not at all obvious, and for some graph clustering algorithms the answer is "no") 2. is a O(n^3) total work algorithm really that much better than one of the multiple existing subquadratic graph clustering algorithms out there.
- sanskritabelt 13y agoI don't want to run an O(n^3) algorithm on even a medium sized graph if I can help it. (and in the new order of 'big data', even O(nlogn) algorithms can be too expensive to solve).
- ac2u 13y agoStrictly speaking, isn't the link between whether an algo is polynomial or not in time complexity only loosely related to its intractability? ie: polynomial usually correlates with tractable but not necessarily? My knowledge in this is rusty though so please correct me if that's inaccurate.