This is the mail archive of the
xsl-list@mulberrytech.com
mailing list .
Re: O(n) notation (and character padding)
- To: "Dave Gomboc" <dave at cs dot ualberta dot ca>, David Carlisle <davidc at nag dot co dot uk>
- Subject: Re: O(n) notation (and character padding)
- From: Jeni Tennison <mail at jenitennison dot com>
- Date: Fri, 17 Nov 2000 10:11:21 +0000
- CC: "XSL-List" <xsl-list at mulberrytech dot com>
- Organization: Jeni Tennison Consulting Ltd
- References: <200011161330.IAA00478@mulberrytech.com><000d01c05019$7e9396e0$d1718081@thorin>
- Reply-To: xsl-list at mulberrytech dot com
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