* Re: [gentoo-dev] Portage QOS
@ 2014-01-10 18:19 99% ` Ciaran McCreesh
0 siblings, 0 replies; 1+ results
From: Ciaran McCreesh @ 2014-01-10 18:19 UTC (permalink / raw
To: gentoo-dev
[-- Attachment #1: Type: text/plain, Size: 853 bytes --]
On Fri, 10 Jan 2014 14:18:24 +0100
René Neumann <lists@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
[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 198 bytes --]
^ permalink raw reply [relevance 99%]
Results 1-1 of 1 | reverse | options above
-- pct% links below jump to the message on this page, permalinks otherwise --
2014-01-09 7:24 [gentoo-dev] Portage QOS LTHR
2014-01-09 8:12 ` Alec Warner
2014-01-09 12:44 ` Igor
2014-01-09 14:12 ` Christopher Schwan
2014-01-09 15:26 ` Igor
2014-01-10 0:16 ` heroxbd
2014-01-10 12:30 ` Igor
2014-01-10 12:39 ` Patrick Lauer
2014-01-10 13:05 ` Igor
2014-01-10 13:18 ` René Neumann
2014-01-10 18:19 99% ` Ciaran McCreesh
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox