3 ms·
Exponentially better than a polynomial in N is a polynomial in log N. See the abstract of [1] for the precise complexity claim about the algorithm mentioned in
by cvoss 9y ago
Exponentially better than a polynomial in N is a polynomial in log N. See the abstract of [1] for the precise complexity claim about the algorithm mentioned in the article. As good as N^3 sounds, it's still not great on enormous systems.
[1] https://arxiv.org/abs/0811.3171 https://arxiv.org/abs/0811.3171
- bradleyjg 9y agoIt's funny you put it that way. O(N^3) sounds horrific to me. Only practical for small problems and for anything else I'd need to look for approximations instead. O(2^N) meanwhile translates in my mind to completely impracticable. But I guess it all depends on what kind of Ns you are looking at.
- reacweb 9y agoI use perfect matching in go tournaments. I have tested it with 1000 players, it was less than 2 minutes -> perfectly acceptable.
- bradleyjg 9y agoOne thousand cubed is one billion. Of course it depends on what the Big-O notion is hiding, but one billion 'steps' is generally okay. But if you had tested it with ten thousand players it would go from one billion to one trillion -- which we'd expect to take more than a day on the same machine. That scaling is pretty brutal. Whereas something like sorting a list with O(N log N) would only have gone from about ten thousand to about one hundred fifty thousand. In order to hit one trillion steps we'd need to be sorting a list of nearly thirty billion items. I sometimes find myself working with ten thousand 'things', but very rarely with thirty billion.