[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Complexity of Topological Sort + single-pass treewalk tiebreaker
- 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-