On Oct 30, 2004, at 7:18 PM, William Squires wrote:
On Oct 30, 2004, at 1:05 PM, Theodore H.Smith wrote:
Does anyone know much about the field of string similarity?
I have a distaste for the academia, because:
1) If you look at the pioneers of modern computing, few came from
the
academia.
2) Most of what they write is over-complexified, yet impractical.
"O(N)" notations and really bad source code writing skills.
The "O(N)" notation is a simple, expressive way to describe the
asymptotic growth rate of a function. I'm happy to explain it, if
you
like.
No need to explain it, not to me as its simple enough to grasp. To me
its like bad C. C is a simple language, correct? But C can be used to
write awful things that no human should understand (obfuscated C). To
me, O(N) is just like that. Simple, but not nice looking. A step
towards obfuscation.
O(N) notation does sense and is useful, its just unnecessarily
mathematical... Why not just express it like "linear cost", or
"quadratic cost". I suppose when you have functions whose cost really
IS an equation, like n*log(n) then it makes sense, but I'd really
only use that as a last resort, if there wasn't a better way of
expressing the costs, without resorting to obfuscation.
Also, it doesn't mention the length of time that O takes. O(N) for
example, may be slower than O(N^2) for low values of N, if O in the
first case is high, but O in the second case is low.
Say what?!?
While it is true that - if O() were a pure mathematical function -
O(N) > O(N^2) | 0 < N < 1, but N can only take on integral values; how
can you have 1/2 of a data point?
Theo has the right idea; recall that to say that a function f is O(g)
means that there exist constants C and M such that f(x) < C*g(x) for
all x > M. If C or M is large, then it's certainly possible that f(x)
> g(x) for small x.
Charles Yeomans
_______________________________________________
Unsubscribe or switch delivery mode:
<http://www.realsoftware.com/support/listmanager/>
Search the archives of this list here:
<http://www.realsoftware.com/listarchives/lists.html>
|