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