[Data-modeling] Modeling datastructures

[Faye Harris]

Agreed. It depends on how deep and how detailed you want to model this 
(for example, for search, you would even break it down to best case, 
average case, and worst case scenarios if you're so inclined). I glossed 
over modeling details for an Algorithm type since it was not part of the 
original question.

The whole point of modeling algorithm together with data structure is 
that the complexity of the former depends on the latter, and the two 
types could both share and benefit from topics belonging to an 
complexity order *type* as opposed to just text strings for complexity 
orders that couldn't be reused.

-- Faye


Tim Kientzle wrote:
>> To summarize, this is what we'd have:
>>
>> Type: Big O Order (or whatever you want to name it)
>> Display: Enumerated
>> Properties:
>> 1) Data structures with this space complexity (expected type: Data
>> Structure)
>> 2) Algorithms with this runtime efficiency (expected type: Algorithm)
>> Create a topic for each common order: O(1), O(n), O(log n), O(n log  
>> n),
>> O(n^2), etc.
>>     
>
> Actually, there are at least two different complexity measures for
> each operation on a data structure.[1]
>
> So I think you'll need at least a type for operations, another for
> data structures, and a CVT which attaches a complexity to each
> combination.
>
> E.g.,
>    array <---  O(n) space ---> Merge sort
>    array <---  O(n log n) time ---> Merge sort
>    linked list <--- O(1) space ---> Merge sort
>    linked list <--- O(n log n) time ---> Merge sort
>    heap <---  O(n) space ---> inserting n items
>    heap <---  O(n log n) time ---> inserting n items
>    heap <---  O(n log n) time ---> removing first n items
>
> Of course, as David pointed out, "n" is a pretty simple case.
> Complexity often varies with several features (average link
> density, tree height, largest clique).
>
> Stepanov's STL work at SGI (http://www.sgi.com/tech/stl/)
> has resulted in a very nice hierarchy of data structures
> and operations that seems like a nice starting point for this.
>
> Tim
>
> [1] Of course, this is only if you limit yourself to big-O
> asymptotic average complexity.  There are quite a few
> other complexity measures that are of interest in various cases.
>
> _______________________________________________
> Data-modeling mailing list
> Data-modeling at freebase.com
> http://lists.freebase.com/mailman/listinfo/data-modeling
>
>