[XSL-LIST Mailing List Archive Home]
[By Thread]
[By Date]
RE: O(n) notation (and character padding)
Subject: RE: O(n) notation (and character padding) From: "David Bergman" <davidb@xxxxxxx> Date: Fri, 17 Nov 2000 09:00:44 -0500 |
Jenni, of course two algorithms can take considerably different times while having the same complexity. Nobody has denied that. Again, the complexity of an algorithm is the asymptotic behavior disregarding any factor of a polynomial degree lower than the complexity (I am talking non-exponential algorithms). Wow, this really cleared things up... What this means is the following: 1. The time to complete an non-exponential algorithm will for sufficiently "big" inputs be of the form 'f(x)*exp(x, n)', where x is a measure of the size of the input and f(x) is a polynomial of (maximum) degree n-1. The complexity of the algorithm is thus O(exp(x, n)). 2. The 'f(x)' can be quite big, so even the asymptotic (the "sufficiently big" part...) behavior can differ considerably. 3. It takes a while to reach those "sufficiently big inputs" (it might never happen, as is often the case for small examples). Up to that point, the complexity has little if any influence on the completion time. In the XML case, the size of the input is often just the number of characters in the file. There is a bible in algorithms and their complexity. Actually, three. They are made by Professor Donald Knuth, who is probably one of the most intelligent individuals in this IT world of ours. Have fun, David -----Original Message----- From: owner-xsl-list@xxxxxxxxxxxxxxxx [mailto:owner-xsl-list@xxxxxxxxxxxxxxxx]On Behalf Of Jeni Tennison Sent: Friday, November 17, 2000 5:11 AM To: Dave Gomboc; David Carlisle Cc: XSL-List Subject: Re: O(n) notation (and character padding) Dave and David, Thank you both for your thorough and very helpful explanations and examples. It's particularly enlightening for me to see that the relative complexity of the algorithm does not necessarily mean it's generally worse - it's always a matter of balancing different criteria for a particular problem. Indeed, I think I'm right in saying that you can have two algorithms that do the same thing in different times but with the same complexity, so Mike's point that: num[not(../num > .)][1] is still 0(n^2) is a comment about how the run-time of the XPath will increase as more nums are added: it doesn't matter how much time it takes or the fact it might stop half way through. This is one of those conceptual revisions that will take a little time to sink in for me. I'm still struggling to see why: <xsl:template match="in" mode="find-max"> <xsl:variable name="greater" select="following-sibling::in[. > current()][1]" /> <xsl:choose> <xsl:when test="$greater"> <xsl:apply-templates select="$greater" mode="find-max" /> </xsl:when> <xsl:otherwise><xsl:value-of select="." /></xsl:otherwise> </xsl:choose> </xsl:template> is 0(n^2) while: <xsl:template match="in" mode="find-max"> <xsl:variable name="max-of-rest"> <xsl:apply-templates select="following-sibling::in[1]" mode="find-max" /> </xsl:variable> <xsl:choose> <xsl:when test=". > $max-of-rest or not(string($max-of-rest))"> <xsl:value-of select="." /> </xsl:when> <xsl:otherwise> <xsl:value-of select="$max-of-rest" /> </xsl:otherwise> </xsl:choose> </xsl:template> is 0(n). You both recommend looking at a book on algorithms: do you have any good ones that you recommend particularly? Thanks again for your help, Jeni --- Jeni Tennison http://www.jenitennison.com/ XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: O(n) notation (and character pa, David Carlisle | Thread | RE: O(n) notation (and character pa, David Bergman |
RE: Splitting result into 2 or more, Linda van den Brink | Date | RE: O(n) notation (and character pa, David Bergman |
Month |