Changes between Version 6 and Version 7 of FAQ/AlgorithmicComplexity
- Timestamp:
- 02/03/06 08:02:25 (18 years ago)
Legend:
- Unmodified
- Added
- Removed
- Modified
-
FAQ/AlgorithmicComplexity
v6 v7 16 16 17 17 When 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 == 19 19 20 From Pavel Pisa as posted to the RTEMS ML (http://www.rtems.com/ml/rtems-users/2006/february/msg00006.html).20 Posted to the RTEMS ML (http://www.rtems.com/ml/rtems-users/2006/february/msg00006.html). 21 21 22 22 GAVL can solve this 23 23 24 {{{ 24 25 insert = search O(log(n)), 25 26 max one re-ballance O(1) with max O(log(n)) heights update. … … 40 41 The +1 one in GAVL is cost for zero re-balanced 41 42 cut first operation. 43 }}} 42 44 43 45 More about this code is on my page: http://cmp.felk.cvut.cz/~pisa/#ulut … … 66 68 67 69 Timers 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 == 70 71 71 72 http://www.rtems.com/ml/rtems-users/2006/february/msg00006.html