MOO-cows Mailing List Archive
[Subject Prev][Subject Next][Thread Prev][Thread Next][Subject Index][Thread Index]
re:hash & balanced trees
On Mon, 30 Jun 1997, Amy Bruckman wrote:
> Subject : Re: my kingdom for a hash table!
> ----- Message Text -----
> ..., something about operations increasing exponentialy, ...
The computational complexity of most algorithms over particular data
structures is provable. The computational complexity for searching a
linear list for a specified string is on the order of the number of
elements in the list and is often denoted O(n). If the list is kept in
a sorted fashion, algorithms can achieve greater efficency than O(n/2).
Of course, there is a greater cost of adding an element to a sorted list
than to an unordered list. This tradeoff, between computation required to
create and maintain a data structure and the complexity of searching for
an element, is a primary issue when considering alternative structures.
Balanced binary trees are O(log(n)) on searches, and algortithms such as AVL
trees have acceptable insertion and deletion measures. Besides, there is c
source code available.
Subject Index |