Subject: RE: O(n) notation (and character padding) From: "David Bergman" <davidb@xxxxxxx> Date: Fri, 17 Nov 2000 09:06:31 -0500 |
Oops, I forgot that the 'f(x)*exp(x,n)' should be 'f(x)+C*exp(x,n)'. Sorry. It does not affect the points made, though. Haven't had my morning coffee... /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 Bergman | Thread | XSLT link to schema, Messineo, Chris |
RE: O(n) notation (and character pa, David Bergman | Date | localization techniques and code re, Haroon Rafique |
Month |