page580.html

来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 61 行

HTML
61 行
字号 
<HTML><HEAD><TITLE>Running Time Analysis</TITLE></HEAD><BODY bgcolor="#FFFFFF"> <a href="../index.html" target="_top"><img src="../icons/usins.gif" alt="Logo" align=right></a><b>Data Structures and Algorithms with Object-Oriented Design Patterns in Python</b><br><A NAME="tex2html7817" HREF="page581.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7815" HREF="page578.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7811" HREF="page579.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A>  <A NAME="tex2html7819" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION0016522000000000000000">Running Time Analysis</A></H3><P>The <tt>KruskalsAlgorithm</tt> method begins by creatingan graph to hold the result spanning tree (lines&nbsp;5-7).Since a spanning tree is a sparse graphthe <tt>GraphAsLists</tt> class is used to represent it.Initially the graph contains  <IMG WIDTH=18 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70975" SRC="img2249.gif"  > vertices but no edges.The running time for lines&nbsp;5-7 is  <IMG WIDTH=43 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70999" SRC="img2255.gif"  >.<P>Next all of the edges in the input graphare inserted one-by-one into the priority queue (lines&nbsp;8-11).Since there are  <IMG WIDTH=17 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70987" SRC="img2251.gif"  > edges,the worst-case running time for a single insertion is  <IMG WIDTH=65 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71855" SRC="img2373.gif"  >.Therefore, the worst-case running time to initialize the priority queue is<P> <IMG WIDTH=315 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath71843" SRC="img2374.gif"  ><P>when adjacency lists are used, and<P> <IMG WIDTH=319 HEIGHT=19 ALIGN=BOTTOM ALT="displaymath71844" SRC="img2375.gif"  ><P>when adjacency matrices are used to represent the input graph.<P>The main loop of the method comprises lines 13-22.This loop is done at most  <IMG WIDTH=17 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70987" SRC="img2251.gif"  > times.In each iteration of the loop,one edge is removed from the priority queue (lines&nbsp;14-15).In the worst-case this takes  <IMG WIDTH=65 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71855" SRC="img2373.gif"  > time.<P>Then, two partition <em>find</em> operations are doneto determine the elements of the partitionthat contain the two end-points of the given edge (lines&nbsp;16-19).Since the partition contains at most  <IMG WIDTH=18 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70975" SRC="img2249.gif"  > elements,the running time for the find operations is  <IMG WIDTH=66 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline72317" SRC="img2453.gif"  >.If the two elements of the partition are distinct,then an edge is added to the spanning treeand a <em>join</em> operation is done to unitethe two elements of the partition (lines&nbsp;20-22).The join operation also requires  <IMG WIDTH=66 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline72317" SRC="img2453.gif"  > time in the worst-case.Therefore, the total running time for the main loopis  <IMG WIDTH=170 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline72321" SRC="img2454.gif"  >.<P>Thus, the worst-case running time for Kruskal's algorithm is<P> <IMG WIDTH=357 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath72297" SRC="img2455.gif"  ><P>when adjacency lists are used, and<P> <IMG WIDTH=360 HEIGHT=19 ALIGN=BOTTOM ALT="displaymath72298" SRC="img2456.gif"  ><P>when adjacency matrices are used to represent the input graph.<P><HR><A NAME="tex2html7817" HREF="page581.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7815" HREF="page578.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7811" HREF="page579.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A>  <A NAME="tex2html7819" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <P><ADDRESS><img src="../icons/bruno.gif" alt="Bruno" align=right><a href="../copyright.html">Copyright &#169; 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a>  All rights reserved.</ADDRESS></BODY></HTML>

page580.html - 源码说明

本页面展示了「Data Structures And Algorithms With Object-Oriented Design Patterns In Python (2003) source code and」中的 page580.html 源码文件，采用 HTML 编程语言编写，共 61 行代码。您可以在线阅读完整代码内容，也可以返回资源详情页下载完整源码包进行本地学习和开发。

虫虫下载站收录了大量与Object-Oriented相关的技术资源，包括源代码、技术文档、电路图等，是电子工程师和嵌入式开发者的专业学习平台。

⌨️ 快捷键说明

复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?