[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: common-lisp-object-system@SAIL.STANFORD.EDU*Subject*: Complexity of Topological Sort + single-pass treewalk tiebreaker*From*: Dick Gabriel <RPG@SAIL.STANFORD.EDU>*Date*: 28 Jan 87 1005 PST

Let n be the number of classes at or above the one for which you which to compute the CPL; let m be the sum of the number of direct superclasses at each class at or above the class of interest. You can do the tiebreaker treewalk in O(n) time; the topological sort O(n+m), so the whole thing is linear. -rpg-

- Prev by Date:
**:allocation :none** - Next by Date:
**Problem with get-function and put-function** - Previous by thread:
**Elaboration on the Non-intuitiveness of New Flavors Algorithm...** - Next by thread:
**Problem with get-function and put-function** - Index(es):