Changes between Version 6 and Version 7 of FAQ/AlgorithmicComplexity


Ignore:
Timestamp:
02/03/06 08:02:25 (16 years ago)
Author:
JoelSherrill
Comment:

/* =GAVL */ Formatting

Legend:

Unmodified
Added
Removed
Modified
  • FAQ/AlgorithmicComplexity

    v6 v7  
    1616
    1717When priority ordering of messages is used, the insertion is into a simple list and is O(n) where n is the number of messages pending.
    18 == GAVL===
     18== Pavel Pisa's Sugestion ==
    1919
    20 From Pavel Pisa as posted to the RTEMS ML (http://www.rtems.com/ml/rtems-users/2006/february/msg00006.html).
     20Posted to the RTEMS ML (http://www.rtems.com/ml/rtems-users/2006/february/msg00006.html).
    2121
    2222GAVL can solve this
    2323
     24{{{
    2425insert    = search O(log(n)),
    2526            max one re-ballance O(1) with max O(log(n)) heights update.
     
    4041            The +1 one in GAVL is cost  for zero re-balanced
    4142            cut first operation.
     43}}}
    4244
    4345More about this code is on my page: http://cmp.felk.cvut.cz/~pisa/#ulut
     
    6668
    6769Timers are managed as a delta chain.  Insertion is O(n) where n is the number of timers on the chain (e.g. active).
    68 
    69  ==Pavel Pisa's Suggestion====
     70== Pavel Pisa's Suggestion ==
    7071
    7172http://www.rtems.com/ml/rtems-users/2006/february/msg00006.html