On Fri, 10 Jan 2014 14:18:24 +0100 René Neumann <li...@necoro.eu> wrote: > And again: What is needed is streamlining the algorithms (discussion > on that already started as far as I could notice). An algorithm in > O(n³) is always¹ worse than O(n). The constant factor added by the
Full dependency resolution is NP-hard... If you really wanted to streamline the algorithms, you'd change the inputs slightly. Most of the complexity of doing a decent job of dependency resolution comes from dealing with crap input. > ¹ For a large enough n. ...which could be larger than the number of atoms in the universe. There are real world cases where an algorithm has an O(n^3) step that takes a day, and a O(2^n) step that takes a second for most inputs. You shouldn't be using O() to make performance comparisons. -- Ciaran McCreesh
signature.asc
Description: PGP signature
