Complexity nomenclature

Andrei Alexandrescu via Digitalmars-d digitalmars-d at puremagic.com
Fri Dec 4 05:58:50 PST 2015


On 12/03/2015 10:46 PM, Walter Bright wrote:
> On 12/3/2015 5:27 PM, Andrei Alexandrescu wrote:
>> Now this primitive may have three complexities:
>>
>> * linear in the length of r (e.g. c is a singly-linked list)
>>
>> * linear in the number of elements after r in the collection (e.g. c
>> is an array)
>>
>> * constant (c is a doubly-linked list)
>>
>> These complexities must be reflected in the name of the primitives. Or
>> perhaps
>> it's okay to conflate a couple of them. I know names are something
>> we're awfully
>> good at discussing :o). Destroy!
>
> Are you sure there are only 3 complexities? What if it's a
> self-balancing tree?
>
> I'm also not sure it is a good idea to put the complexity in the name of
> the primitive. Do any other algorithm libraries do that?

Looks exaggerated, innit? The fact of the matter is people choose 
collections based on the complexity of their operations all the time. "I 
need to insert and remove at the front, so I'll use a list here." Or: "I 
need random access, I'll use a vector" etc.

Not designing nomenclature for complexity leads to the usual design 
disasters such as providing a list with the same indexing operator as an 
array.

Turning that on its head, if we want to allow people to design 
collection-independent code and mix and match collections based only on 
their APIs, those APIs must reflect the complexity of operations.

Collection-independent code is big in my design btw.

One idea is to have the very name reflect the operation. I'm thinking 
"insert" to mean "scoot over elements at the tail and insert the new 
element in the gap" and "link" to mean "create a new node and link it 
within this collection without scooting over anything". Then the 
relative costs will be implied.

Another idea is to only classify operations as "quick" (expected O(1) up 
to O(log n)) and "not quick" (everything worse). Then we only have two 
categories, and "quick" will be in the name of the respective methods.


Andrei



More information about the Digitalmars-d mailing list