Alexander Klenin schrieb:
The total order will be something between O(n^1) and O(n^2), depending on
many factors (what is "n"?...).
Huh? O(f(n)) has a precise definition, and of course we are talking worst-case
complexity here (although average complexity would be the same in this case).
n is the string length, measured in whatever units you choose.
For matrix multiplication there exist algorithms from O(N^3) downto
O(N^2.807) [Strassen] and even O(N^2.378) [Coppersmith-Winograd].
Similarly for other problems (hash tables...), where the *amortized
cost* can differ from the agnostic "worst case" assumptions.
A "worst case" IMO applies to concrete procedures only, while algorithms
or problems only have an upper limit, that can be lowered by further
research. Applied to procedures, the coder *establishes* a certain
complexity of his implementation, that may be far away from the
complexity of the problem to solve.
In any case it's essential to verify the determined complexity, in order
to detect inappropriate definitions of N or other factors, that show up
as deviations from the assumed formula.
I also doubt that UTF8char is a reasonable type for the loop variable - IMO
UTF32char were a much better choice...
I think I meant exactly the same thing (an integer holding the codepoint value),
but just named the type carelessly. In fact, I think the best name would be
something like "UnicodeChar" or even "Codepoint", to avoid association
with any particular encoding.
As outlined in another message, (Unicode) string handling IMO should be
based entirely on substrings, so that a special single-character data
type is not required anywhere. Wirth may have anticipated the problems
with character sets in his Pascal design, and did not distinguish
between string and character literals.
DoDi
_______________________________________________
fpc-devel maillist - fpc-devel@lists.freepascal.org
http://lists.freepascal.org/mailman/listinfo/fpc-devel
