lkml.org 
[lkml]   [2011]   [Nov]   [10]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
SubjectRe: [PATCH] perf_events: fix and improve x86 event scheduling
From
Date
On Thu, 2011-11-10 at 19:03 +0100, Robert Richter wrote:
> But this algorithm does not work for all cases and does not solve the
> problem in general.

Yeah, the problem in general is O(n!) no O(n^3) algorithm can compute
the optimal solution for n>3 or so.

I think the goal is to keep the 'normal' case O(n^2) but try and suck
less for the corner cases without degenerating into a full blown O(n!).

So I think we want an amortized O(n^2) with an upper bound well below
O(n!).


\
 
 \ /
  Last update: 2011-11-10 19:45    [W:0.096 / U:0.700 seconds]
©2003-2018 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site