Interesting topic - I used to follow the definition not unlike given here:
Abstract data type - Wikipedia, the free encyclopedia
But somehow I'm not so sure anymore. The reason is that the separation of interface and implementation - which is a very good idea, don't get me wrong! - makes it difficult to do a thorough complexity analysis of an algorithm that uses this particular ADT.
This cannot be done correctly, unless the operations of the ADT can be analyzed in terms of their intrinsic complexity, at least aymptotically.
Obviously, this depends on the well-hidden implementation of the ADT. E. g. a "Priority Queue" can be implemented in a way that insertion and removal have a complexity of O(log n) or in a way that one of them is O(n) and the other is O(1).
This also raises the question of how to perform an average-case analysis of the surrounding algorithm - would you need to specify the average complexity of the ADT operations as well (e. g. as amortized costs).
Let me see what's around on the subject - there's a 1980 paper by Ehrig and Mahr. Just need to get a hold of it.
Until then
No comments:
Post a Comment