数据结构与算法数据结构与算法课后习题答案_数据结构与算法_算法_其他

<html xmlns="http://www.w3.org/1999/xhtml"> <head> <meta charset="utf-8"> <meta name="generator" content="pdf2htmlEX"> <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1"> <link rel="stylesheet" href="https://static.pudn.com/base/css/base.min.css"> <link rel="stylesheet" href="https://static.pudn.com/base/css/fancy.min.css"> <link rel="stylesheet" href="https://static.pudn.com/prod/directory_preview_static/627fea2cebb030486d250f97/raw.css"> <script src="https://static.pudn.com/base/js/compatibility.min.js"></script> <script src="https://static.pudn.com/base/js/pdf2htmlEX.min.js"></script> <script> try{ pdf2htmlEX.defaultViewer = new pdf2htmlEX.Viewer({}); }catch(e){} </script> <title></title> </head> <body> <div id="sidebar" style="display: none"> <div id="outline"> </div> </div> <div id="pf1" class="pf w0 h0" data-page-no="1"><div class="pc pc1 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://static.pudn.com/prod/directory_preview_static/627fea2cebb030486d250f97/bg1.jpg"><div class="t m0 x1 h2 y1 ff1 fs0 fc0 sc0 ls0 ws0">Chapter<span class="_"> </span>10:<span class="_"> </span>Algorithm<span class="_"> </span>Design<span class="_"> </span>Techniques</div><div class="t m0 x1 h3 y2 ff2 fs1 fc0 sc0 ls0 ws0">10.1<span class="_ _0"> </span>First,<span class="_ _1"> </span>we<span class="_ _2"> </span>show<span class="_ _2"> </span>that<span class="_ _2"> </span>if<span class="_ _1"> </span><span class="ff3">N</span></div><div class="t m0 x2 h4 y2 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x3 h3 y2 ff2 fs1 fc0 sc0 ls0 ws0">evenly<span class="_ _2"> </span>divides<span class="_ _2"> </span><span class="ff3">P</span></div><div class="t m0 x4 h4 y2 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x5 h3 y2 ff2 fs1 fc0 sc0 ls0 ws0">,<span class="_ _2"> </span>then<span class="_ _2"> </span>each<span class="_ _2"> </span>of</div><div class="t m0 x6 h4 y2 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">P</span></div><div class="t m0 x7 h5 y2 ff3 fs1 fc0 sc0 ls0 ws0">j</div><div class="t m0 x8 h6 y3 ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x9 h7 y3 ff2 fs2 fc0 sc0 ls0 ws0">(<span class="ff3">i</span></div><div class="t m0 xa h6 y3 ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 xb h8 y3 ff5 fs2 fc0 sc0 ls0 ws0">−<span class="ff2">1)<span class="ff3">P</span></span></div><div class="t m0 xc h6 y3 ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 xd h8 y3 ff5 fs2 fc0 sc0 ls0 ws0">+<span class="ff2">1</span></div><div class="t m0 xe h3 y2 ff2 fs1 fc0 sc0 ls0 ws0">through</div><div class="t m0 xf h4 y2 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">P</span></div><div class="t m0 x10 h5 y2 ff3 fs1 fc0 sc0 ls0 ws0">j</div><div class="t m0 x11 h9 y3 ff3 fs2 fc0 sc0 ls0 ws0">iP</div><div class="t m0 x12 h4 y3 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x13 h3 y4 ff2 fs1 fc0 sc0 ls0 ws0">must<span class="_ _2"> </span>be</div><div class="t m0 x14 h3 y5 ff2 fs1 fc0 sc0 ls0 ws0">placed<span class="_ _3"> </span>as<span class="_ _3"> </span>the<span class="_ _4"> </span><span class="ff3">i</span></div><div class="t m0 x15 h6 y6 ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x16 h9 y6 ff3 fs2 fc0 sc0 ls0 ws0">th</div><div class="t m0 x17 h4 y6 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x18 h3 y7 ff2 fs1 fc0 sc0 ls0 ws0">job<span class="_ _4"> </span>on<span class="_ _3"> </span>some<span class="_ _4"> </span>processor.<span class="_ _5"> </span>Suppose<span class="_ _3"> </span>otherwise.<span class="_ _5"> </span>Then<span class="_ _3"> </span>in<span class="_ _4"> </span>the<span class="_ _3"> </span>supposed</div><div class="t m0 x14 h3 y8 ff2 fs1 fc0 sc0 ls0 ws0">optimal<span class="_ _6"> </span>ordering,<span class="_ _6"> </span>we<span class="_ _7"> </span>must<span class="_ _6"> </span>be<span class="_ _6"> </span>able<span class="_ _7"> </span>to<span class="_ _6"> </span>ﬁnd<span class="_ _6"> </span>some<span class="_ _6"> </span>jobs</div><div class="t m0 x19 h4 y8 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">P</span></div><div class="t m0 x1a h5 y8 ff3 fs1 fc0 sc0 ls0 ws0">j</div><div class="t m0 x1b h9 y9 ff3 fs2 fc0 sc0 ls0 ws0">x</div><div class="t m0 x1c h4 y9 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x1d h3 ya ff2 fs1 fc0 sc0 ls0 ws0">and</div><div class="t m0 x1e h4 ya ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">P</span></div><div class="t m0 x1f h5 ya ff3 fs1 fc0 sc0 ls0 ws0">j</div><div class="t m0 xa h9 y9 ff3 fs2 fc0 sc0 ls0 ws0">y</div><div class="t m0 x20 h4 y9 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x21 h3 ya ff2 fs1 fc0 sc0 ls0 ws0">such<span class="_ _6"> </span>that</div><div class="t m0 x22 h4 ya ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">P</span></div><div class="t m0 x23 h5 ya ff3 fs1 fc0 sc0 ls0 ws0">j</div><div class="t m0 x24 h9 y9 ff3 fs2 fc0 sc0 ls0 ws0">x</div><div class="t m0 x25 h4 y9 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x26 h3 ya ff2 fs1 fc0 sc0 ls0 ws0">is<span class="_ _6"> </span>the<span class="_ _7"> </span><span class="ff3">t</span></div><div class="t m0 x27 h6 yb ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x28 h9 yb ff3 fs2 fc0 sc0 ls0 ws0">th</div><div class="t m0 x29 h4 yb ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x2a h3 yc ff2 fs1 fc0 sc0 ls0 ws0">job</div><div class="t m0 x14 h3 yd ff2 fs1 fc0 sc0 ls0 ws0">on<span class="_ _8"> </span>some<span class="_ _8"> </span>processor<span class="_ _6"> </span>and</div><div class="t m0 x2b h4 yd ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">P</span></div><div class="t m0 x2c h5 yd ff3 fs1 fc0 sc0 ls0 ws0">j</div><div class="t m0 x2 h9 ye ff3 fs2 fc0 sc0 ls0 ws0">y</div><div class="t m0 x2d h4 ye ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x2e h3 yf ff2 fs1 fc0 sc0 ls0 ws0">is<span class="_ _8"> </span>the<span class="_ _6"> </span><span class="ff3">t</span></div><div class="t m0 x2f h4 yf ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x30 ha yf ff5 fs1 fc0 sc0 ls0 ws0">+<span class="ff2">1</span></div><div class="t m0 x31 h9 y10 ff3 fs2 fc0 sc0 ls0 ws0">th</div><div class="t m0 x32 h4 y10 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x33 h3 y11 ff2 fs1 fc0 sc0 ls0 ws0">job<span class="_ _8"> </span>on<span class="_ _6"> </span>some<span class="_ _8"> </span>processor<span class="_ _6"> </span>but<span class="_ _8"> </span><span class="ff3">t</span></div><div class="t m0 x34 h9 ye ff3 fs2 fc0 sc0 ls0 ws0">x</div><div class="t m0 x35 h4 ye ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x36 h3 yf ff3 fs1 fc0 sc0 ls0 ws0"> <span class="ff2">></span> t</div><div class="t m0 x37 h9 ye ff3 fs2 fc0 sc0 ls0 ws0">y</div><div class="t m0 x22 h4 ye ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x38 h3 yf ff2 fs1 fc0 sc0 ls0 ws0">.<span class="_ _9"> </span>Let</div><div class="t m0 x39 h4 yf ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">P</span></div><div class="t m0 x3a h5 yf ff3 fs1 fc0 sc0 ls0 ws0">j</div><div class="t m0 x13 h9 ye ff3 fs2 fc0 sc0 ls0 ws0">z</div><div class="t m0 x3b h4 ye ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x27 h3 yf ff2 fs1 fc0 sc0 ls0 ws0">be<span class="_ _6"> </span>the</div><div class="t m0 x14 h3 y12 ff2 fs1 fc0 sc0 ls0 ws0">job<span class="_"> </span>immediately<span class="_ _7"> </span>following</div><div class="t m0 x2e h4 y12 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">P</span></div><div class="t m0 x3c h5 y12 ff3 fs1 fc0 sc0 ls0 ws0">j</div><div class="t m0 x3d h9 y13 ff3 fs2 fc0 sc0 ls0 ws0">x</div><div class="t m0 x3e h4 y13 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x3f h3 y14 ff2 fs1 fc0 sc0 ls0 ws0">.<span class="_ _a"> </span>If<span class="_"> </span>we<span class="_"> </span>swap</div><div class="t m0 x40 h4 y14 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">P</span></div><div class="t m0 x41 h5 y14 ff3 fs1 fc0 sc0 ls0 ws0">j</div><div class="t m0 x4 h9 y13 ff3 fs2 fc0 sc0 ls0 ws0">y</div><div class="t m0 x42 h4 y13 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x43 h3 y14 ff2 fs1 fc0 sc0 ls0 ws0">and</div><div class="t m0 x44 h4 y14 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">P</span></div><div class="t m0 x45 h5 y14 ff3 fs1 fc0 sc0 ls0 ws0">j</div><div class="t m0 x46 h9 y13 ff3 fs2 fc0 sc0 ls0 ws0">z</div><div class="t m0 x47 h4 y13 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x48 h3 y14 ff2 fs1 fc0 sc0 ls0 ws0">,<span class="_"> </span>it<span class="_ _7"> </span>is<span class="_"> </span>easy<span class="_"> </span>to<span class="_"> </span>check<span class="_"> </span>that<span class="_"> </span>the<span class="_"> </span>mean<span class="_"> </span>pro-</div><div class="t m0 x14 h3 y15 ff2 fs1 fc0 sc0 ls0 ws0">cessing<span class="_"> </span>time<span class="_ _7"> </span>is<span class="_ _7"> </span>unchanged<span class="_"> </span>and<span class="_ _7"> </span>thus<span class="_ _7"> </span>still<span class="_ _7"> </span>optimal.<span class="_ _a"> </span>But<span class="_ _7"> </span>now</div><div class="t m0 x49 h4 y15 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">P</span></div><div class="t m0 x6 h5 y15 ff3 fs1 fc0 sc0 ls0 ws0">j</div><div class="t m0 x4a h9 y16 ff3 fs2 fc0 sc0 ls0 ws0">y</div><div class="t m0 x1e h4 y16 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 xb h3 y17 ff2 fs1 fc0 sc0 ls0 ws0">follows</div><div class="t m0 x4b h4 y17 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">P</span></div><div class="t m0 x4c h5 y17 ff3 fs1 fc0 sc0 ls0 ws0">j</div><div class="t m0 x4d h9 y16 ff3 fs2 fc0 sc0 ls0 ws0">x</div><div class="t m0 x4e h4 y16 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x4f h3 y17 ff2 fs1 fc0 sc0 ls0 ws0">,<span class="_ _7"> </span>which<span class="_"> </span>is<span class="_ _7"> </span>impos-</div><div class="t m0 x14 h3 y18 ff2 fs1 fc0 sc0 ls0 ws0">sible<span class="_ _8"> </span>because<span class="_ _6"> </span>we<span class="_ _8"> </span>know<span class="_ _2"> </span>that<span class="_ _8"> </span>the<span class="_ _8"> </span>jobs<span class="_ _8"> </span>on<span class="_ _2"> </span>any<span class="_ _8"> </span>processor<span class="_ _6"> </span>must<span class="_ _8"> </span>be<span class="_ _8"> </span>in<span class="_ _8"> </span>sorted<span class="_ _8"> </span>order<span class="_ _6"> </span>from<span class="_ _8"> </span>the</div><div class="t m0 x14 h3 y19 ff2 fs1 fc0 sc0 ls0 ws0">results<span class="_"> </span>of<span class="_"> </span>the<span class="_"> </span>one<span class="_"> </span>processor<span class="_"> </span>case.</div><div class="t m0 x14 h3 y1a ff2 fs1 fc0 sc0 ls0 ws0">Let</div><div class="t m0 x50 h4 y1a ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">P</span></div><div class="t m0 x51 h5 y1a ff3 fs1 fc0 sc0 ls0 ws0">j</div><div class="t m0 x52 h9 y1b ff3 fs2 fc0 sc0 ls0 ws0">e</div><div class="t m0 x53 h6 y1b ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x54 h7 y1b ff2 fs2 fc0 sc0 ls0 ws0">1</div><div class="t m0 x55 h3 y1c ff2 fs1 fc0 sc0 ls0 ws0">,</div><div class="t m0 x56 h4 y1c ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">P</span></div><div class="t m0 x57 h5 y1c ff3 fs1 fc0 sc0 ls0 ws0">j</div><div class="t m0 x58 h9 y1b ff3 fs2 fc0 sc0 ls0 ws0">e</div><div class="t m0 x59 h6 y1b ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x5a h7 y1b ff2 fs2 fc0 sc0 ls0 ws0">2</div><div class="t m0 x5b h3 y1c ff2 fs1 fc0 sc0 ls0 ws0">,<span class="_ _7"> </span>...,</div><div class="t m0 x15 h4 y1c ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">P</span></div><div class="t m0 x16 h5 y1c ff3 fs1 fc0 sc0 ls0 ws0">j</div><div class="t m0 x5c h9 y1b ff3 fs2 fc0 sc0 ls0 ws0">eM</div><div class="t m0 x18 h4 y1b ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x5d h3 y1a ff2 fs1 fc0 sc0 ls0 ws0">be<span class="_ _7"> </span>the<span class="_"> </span>extra<span class="_ _7"> </span>jobs<span class="_ _7"> </span>if<span class="_ _7"> </span><span class="ff3">N</span></div><div class="t m0 x5e h4 y1a ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x5f h3 y1a ff2 fs1 fc0 sc0 ls0 ws0">does<span class="_ _7"> </span>not<span class="_ _7"> </span>evenly<span class="_ _7"> </span>divide<span class="_ _7"> </span><span class="ff3">P</span></div><div class="t m0 x60 h4 y1a ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x61 h3 y1a ff2 fs1 fc0 sc0 ls0 ws0">.<span class="_ _a"> </span>It<span class="_ _7"> </span>is<span class="_ _6"> </span>easy<span class="_"> </span>to<span class="_ _7"> </span>see<span class="_ _7"> </span>that</div><div class="t m0 x14 h3 y1d ff2 fs1 fc0 sc0 ls0 ws0">the<span class="_ _8"> </span>processing<span class="_ _6"> </span>time<span class="_ _8"> </span>for<span class="_ _8"> </span>these<span class="_ _8"> </span>jobs<span class="_ _8"> </span>depends<span class="_ _6"> </span>only<span class="_ _8"> </span>on<span class="_ _8"> </span>how<span class="_ _8"> </span>quickly<span class="_ _8"> </span>they<span class="_ _8"> </span>can<span class="_ _8"> </span>be<span class="_ _6"> </span>scheduled,</div><div class="t m0 x14 h3 y1e ff2 fs1 fc0 sc0 ls0 ws0">and<span class="_ _7"> </span>that<span class="_ _6"> </span>they<span class="_ _7"> </span>must<span class="_ _6"> </span>be<span class="_ _7"> </span>the<span class="_ _6"> </span>last<span class="_ _7"> </span>scheduled<span class="_ _7"> </span>job<span class="_ _6"> </span>on<span class="_ _6"> </span>some<span class="_ _7"> </span>processor.<span class="_ _a"> </span>It<span class="_ _6"> </span>is<span class="_ _7"> </span>easy<span class="_ _7"> </span>to<span class="_ _7"> </span>see<span class="_ _7"> </span>that<span class="_ _6"> </span>the</div><div class="t m0 x14 h3 y1f ff2 fs1 fc0 sc0 ls0 ws0">ﬁrst<span class="_ _1"> </span><span class="ff3">M</span></div><div class="t m0 x55 h4 y1f ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x56 h3 y1f ff2 fs1 fc0 sc0 ls0 ws0">processors<span class="_ _2"> </span>must<span class="_ _1"> </span>have<span class="_ _2"> </span>jobs</div><div class="t m0 x62 h4 y1f ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">P</span></div><div class="t m0 x63 h5 y1f ff3 fs1 fc0 sc0 ls0 ws0">j</div><div class="t m0 x31 h6 y20 ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x64 h7 y20 ff2 fs2 fc0 sc0 ls0 ws0">(<span class="ff3">i</span></div><div class="t m0 x32 h6 y20 ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x65 h8 y20 ff5 fs2 fc0 sc0 ls0 ws0">−<span class="ff2">1)<span class="ff3">P</span></span></div><div class="t m0 x40 h6 y20 ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x41 h8 y20 ff5 fs2 fc0 sc0 ls0 ws0">+<span class="ff2">1</span></div><div class="t m0 x66 h3 y21 ff2 fs1 fc0 sc0 ls0 ws0">through</div><div class="t m0 x1b h4 y21 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">P</span></div><div class="t m0 x67 h5 y21 ff3 fs1 fc0 sc0 ls0 ws0">j</div><div class="t m0 x1c h9 y20 ff3 fs2 fc0 sc0 ls0 ws0">iP</div><div class="t m0 x68 h6 y20 ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x69 h8 y20 ff5 fs2 fc0 sc0 ls0 ws0">+<span class="ff3">M</span></div><div class="t m0 x6a h4 y20 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x8 h3 y22 ff2 fs1 fc0 sc0 ls0 ws0">;<span class="_ _1"> </span>we<span class="_ _2"> </span>leave<span class="_ _2"> </span>the<span class="_ _2"> </span>details<span class="_ _1"> </span>to<span class="_ _2"> </span>the</div><div class="t m0 x14 h3 y23 ff2 fs1 fc0 sc0 ls0 ws0">reader.</div><div class="t m0 x1 h3 y24 ff2 fs1 fc0 sc0 ls0 ws0">10.3</div><div class="t m0 x6b h3 y25 ff2 fs1 fc0 sc0 ls0 ws0">,</div><div class="t m0 x14 h3 y26 ff2 fs1 fc0 sc0 ls0 ws0">4<span class="_ _b"> </span>7<span class="_ _b"> </span>8<span class="_ _b"> </span>9</div><div class="t m0 x6c h3 y27 ff2 fs1 fc0 sc0 ls0 ws0">0</div><div class="t m0 x62 h3 y26 ff2 fs1 fc0 sc0 ls0 ws0">1<span class="_ _b"> </span>5</div><div class="t m0 x6d h3 y27 ff2 fs1 fc0 sc0 ls0 ws0">sp</div><div class="t m0 x6e h3 y28 ff2 fs1 fc0 sc0 ls0 ws0">nl</div><div class="t m0 xc h3 y29 ff2 fs1 fc0 sc0 ls0 ws0">3<span class="_ _c"> </span>:</div><div class="t m0 x6f h3 y28 ff2 fs1 fc0 sc0 ls0 ws0">6<span class="_ _b"> </span>2</div><div class="t m0 x1 h3 y2a ff2 fs1 fc0 sc0 ls0 ws0">10.4<span class="_ _0"> </span>One<span class="_"> </span>method<span class="_"> </span>is<span class="_ _7"> </span>to<span class="_"> </span>generate<span class="_"> </span>code<span class="_"> </span>that<span class="_"> </span>can<span class="_ _d"> </span>be<span class="_"> </span>evaluated<span class="_"> </span>by<span class="_"> </span>a<span class="_"> </span>stack<span class="_ _d"> </span>machine.<span class="_ _e"> </span>The<span class="_"> </span>two<span class="_"> </span>opera-</div><div class="t m0 x14 h3 y2b ff2 fs1 fc0 sc0 ls0 ws0">tions<span class="_ _7"> </span>are<span class="_ _7"> </span><span class="ff3">Push</span></div><div class="t m0 x70 h4 y2b ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x71 h3 y2b ff2 fs1 fc0 sc0 ls0 ws0">(the<span class="_ _7"> </span>one<span class="_ _7"> </span>node<span class="_ _7"> </span>tree<span class="_ _7"> </span>corresponding<span class="_"> </span>to)<span class="_ _6"> </span>a<span class="_ _7"> </span>symbol<span class="_ _7"> </span>onto<span class="_ _6"> </span>a<span class="_"> </span>stack<span class="_ _7"> </span>and<span class="_ _7"> </span><span class="ff3">Combine,</span></div><div class="t m0 x72 h4 y2b ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x14 h3 y2c ff2 fs1 fc0 sc0 ls0 ws0">which<span class="_ _6"> </span>pops<span class="_ _6"> </span>two<span class="_ _6"> </span>trees<span class="_ _7"> </span>of<span class="_ _f"></span>f<span class="_ _7"> </span>the<span class="_ _6"> </span>stack,<span class="_ _6"> </span>merges<span class="_ _7"> </span>them,<span class="_ _6"> </span>and<span class="_ _6"> </span>pushes<span class="_ _7"> </span>the<span class="_ _6"> </span>result<span class="_ _6"> </span>back<span class="_ _7"> </span>on.<span class="_ _10"> </span>For<span class="_ _6"> </span>the</div><div class="t m0 x14 h3 y2d ff2 fs1 fc0 sc0 ls0 ws0">example<span class="_ _7"> </span>in<span class="_ _7"> </span>the<span class="_ _7"> </span>text,<span class="_ _6"> </span>the<span class="_ _7"> </span>stack<span class="_ _7"> </span>instructions<span class="_ _7"> </span>are<span class="_ _7"> </span><span class="ff3">Push(s),<span class="_ _7"> </span>Push(nl),<span class="_ _6"> </span>Combine,<span class="_ _7"> </span>Push(t),<span class="_"> </span>Com-</span></div><div class="t m0 x14 h5 y2e ff3 fs1 fc0 sc0 ls0 ws0">bine,<span class="_"> </span>Push(a),<span class="_"> </span>Combine,<span class="_"> </span>Push(e),<span class="_"> </span>Combine,<span class="_"> </span>Push(i),<span class="_"> </span>Push<span class="_"> </span>(sp),<span class="_"> </span>Combine,<span class="_"> </span>Combine.</div><div class="t m0 x14 h3 y2f ff2 fs1 fc0 sc0 ls0 ws0">By<span class="_ _6"> </span>encoding<span class="_ _7"> </span>a<span class="_ _6"> </span><span class="ff3">Combine</span></div><div class="t m0 x2c h4 y2f ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x73 h3 y2f ff2 fs1 fc0 sc0 ls0 ws0">with<span class="_ _6"> </span>a<span class="_ _7"> </span>0<span class="_ _6"> </span>and<span class="_ _6"> </span>a<span class="_ _7"> </span><span class="ff3">Push</span></div><div class="t m0 x66 h4 y2f ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x74 h3 y2f ff2 fs1 fc0 sc0 ls0 ws0">with<span class="_ _6"> </span>a<span class="_ _7"> </span>1<span class="_ _6"> </span>followed<span class="_ _7"> </span>by<span class="_ _7"> </span>the<span class="_ _6"> </span>symbol,<span class="_ _6"> </span>the<span class="_ _7"> </span>total</div><div class="t m0 x14 h3 y30 ff2 fs1 fc0 sc0 ls0 ws0">extra<span class="_ _2"> </span>space<span class="_ _8"> </span>is<span class="_ _2"> </span>2<span class="ff3">N</span></div><div class="t m0 x75 h4 y30 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x76 ha y30 ff3 fs1 fc0 sc0 ls0 ws0"> <span class="ff5">−</span> <span class="ff2">1<span class="_ _1"> </span>bits<span class="_ _2"> </span>if<span class="_ _2"> </span>all<span class="_ _2"> </span>the<span class="_ _2"> </span>symbols<span class="_ _1"> </span>are<span class="_ _8"> </span>of<span class="_ _2"> </span>equal<span class="_ _2"> </span>length.<span class="_ _11"> </span>Generating<span class="_ _8"> </span>the<span class="_ _2"> </span>stack</span></div><div class="t m0 x14 h3 y31 ff2 fs1 fc0 sc0 ls0 ws0">machine<span class="_"> </span>code<span class="_"> </span>can<span class="_ _d"> </span>be<span class="_"> </span>done<span class="_"> </span>with<span class="_"> </span>a<span class="_"> </span>simple<span class="_"> </span>recursive<span class="_ _d"> </span>procedure<span class="_ _d"> </span>and<span class="_"> </span>is<span class="_"> </span>left<span class="_"> </span>to<span class="_"> </span>the<span class="_"> </span>reader.</div><div class="t m0 x1 h3 y32 ff2 fs1 fc0 sc0 ls0 ws0">10.6<span class="_ _0"> </span>Maintain<span class="_"> </span>two<span class="_ _7"> </span>queues,<span class="_ _7"> </span><span class="ff3">Q</span></div><div class="t m0 x77 h6 y33 ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x2c h7 y33 ff2 fs2 fc0 sc0 ls0 ws0">1</div><div class="t m0 x2d h3 y34 ff2 fs1 fc0 sc0 ls0 ws0">and<span class="_"> </span><span class="ff3">Q</span></div><div class="t m0 x78 h6 y33 ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x79 h7 y33 ff2 fs2 fc0 sc0 ls0 ws0">2</div><div class="t m0 x7a h3 y34 ff2 fs1 fc0 sc0 ls0 ws0">.<span class="_ _a"> </span><span class="ff3">Q</span></div><div class="t m0 x7b h6 y33 ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x31 h7 y33 ff2 fs2 fc0 sc0 ls0 ws0">1</div><div class="t m0 x7c h3 y34 ff2 fs1 fc0 sc0 ls0 ws0">will<span class="_ _7"> </span>store<span class="_"> </span>single-node<span class="_ _7"> </span>trees<span class="_"> </span>in<span class="_ _7"> </span>sorted<span class="_"> </span>order,<span class="_"> </span>and<span class="_"> </span><span class="ff3">Q</span></div><div class="t m0 x7d h6 y33 ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x7e h7 y33 ff2 fs2 fc0 sc0 ls0 ws0">2</div><div class="t m0 x14 h3 y35 ff2 fs1 fc0 sc0 ls0 ws0">will<span class="_ _4"> </span>store<span class="_ _3"> </span>multinode<span class="_ _4"> </span>trees<span class="_ _3"> </span>in<span class="_ _4"> </span>sorted<span class="_ _4"> </span>order.<span class="_ _5"> </span>Place<span class="_ _3"> </span>the<span class="_ _4"> </span>initial<span class="_ _4"> </span>single-node<span class="_ _3"> </span>trees<span class="_ _3"> </span>on<span class="_ _4"> </span><span class="ff3">Q</span></div><div class="t m0 x7f h6 y36 ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x80 h7 y36 ff2 fs2 fc0 sc0 ls0 ws0">1</div><div class="t m0 x81 h3 y35 ff2 fs1 fc0 sc0 ls0 ws0">,</div><div class="t m0 x14 h3 y37 ff2 fs1 fc0 sc0 ls0 ws0">enqueueing<span class="_ _6"> </span>the<span class="_ _8"> </span>smallest<span class="_ _8"> </span>weight<span class="_ _8"> </span>tree<span class="_ _6"> </span>ﬁrst.<span class="_ _11"> </span>Initially,<span class="_ _8"> </span><span class="ff3">Q</span></div><div class="t m0 x1b h6 y38 ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x67 h7 y38 ff2 fs2 fc0 sc0 ls0 ws0">2</div><div class="t m0 x1d h3 y39 ff2 fs1 fc0 sc0 ls0 ws0">is<span class="_ _8"> </span>empty.<span class="_ _9"> </span>Examine<span class="_ _6"> </span>the<span class="_ _8"> </span>ﬁrst<span class="_ _2"> </span>two</div><div class="t m0 x14 h3 y3a ff2 fs1 fc0 sc0 ls0 ws0">entries<span class="_ _2"> </span>of<span class="_ _1"> </span>each<span class="_ _2"> </span>of<span class="_ _2"> </span><span class="ff3">Q</span></div><div class="t m0 x82 h6 y3b ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x83 h7 y3b ff2 fs2 fc0 sc0 ls0 ws0">1</div><div class="t m0 x84 h3 y3c ff2 fs1 fc0 sc0 ls0 ws0">and<span class="_ _2"> </span><span class="ff3">Q</span></div><div class="t m0 x85 h6 y3b ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x86 h7 y3b ff2 fs2 fc0 sc0 ls0 ws0">2</div><div class="t m0 x87 h3 y3c ff2 fs1 fc0 sc0 ls0 ws0">,<span class="_ _1"> </span>and<span class="_ _2"> </span>dequeue<span class="_ _2"> </span>the<span class="_ _2"> </span>two<span class="_ _1"> </span>smallest.<span class="_ _11"> </span>(This<span class="_ _2"> </span>requires<span class="_ _2"> </span>an<span class="_ _2"> </span>easily</div><div class="t m0 x14 h3 y3d ff2 fs1 fc0 sc0 ls0 ws0">implemented<span class="_ _7"> </span>extension<span class="_ _7"> </span>to<span class="_ _7"> </span>the<span class="_ _7"> </span>ADT.)<span class="_"> </span>Merge<span class="_ _7"> </span>the<span class="_"> </span>tree<span class="_"> </span>and<span class="_ _7"> </span>place<span class="_"> </span>the<span class="_ _7"> </span>result<span class="_"> </span>at<span class="_ _7"> </span>the<span class="_ _7"> </span>end<span class="_"> </span>of<span class="_ _7"> </span><span class="ff3">Q</span></div><div class="t m0 x7f h6 y3e ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x80 h7 y3e ff2 fs2 fc0 sc0 ls0 ws0">2</div><div class="t m0 x81 h3 y3f ff2 fs1 fc0 sc0 ls0 ws0">.</div><div class="t m0 x14 h3 y40 ff2 fs1 fc0 sc0 ls0 ws0">Continue<span class="_"> </span>this<span class="_ _7"> </span>step<span class="_"> </span>until<span class="_"> </span><span class="ff3">Q</span></div><div class="t m0 x73 h6 y41 ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x2d h7 y41 ff2 fs2 fc0 sc0 ls0 ws0">1</div><div class="t m0 x3c h3 y42 ff2 fs1 fc0 sc0 ls0 ws0">is<span class="_"> </span>empty<span class="_"> </span>and<span class="_"> </span>only<span class="_"> </span>one<span class="_"> </span>tree<span class="_"> </span>is<span class="_"> </span>left<span class="_"> </span>in<span class="_"> </span><span class="ff3">Q</span></div><div class="t m0 x88 h6 y41 ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x89 h7 y41 ff2 fs2 fc0 sc0 ls0 ws0">2</div><div class="t m0 x8a h3 y42 ff2 fs1 fc0 sc0 ls0 ws0">.</div><div class="t m0 x32 h3 y43 ff2 fs1 fc0 sc0 ls0 ws0">-54-</div></div><div class="pi" data-data='{"ctm":[1.568627,0.000000,0.000000,1.568627,0.000000,0.000000]}'></div></div> </body> </html>

<div id="pf2" class="pf w0 h0" data-page-no="2"><div class="pc pc2 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://static.pudn.com/prod/directory_preview_static/627fea2cebb030486d250f97/bg2.jpg"><div class="t m0 x1 h3 y1 ff2 fs1 fc0 sc0 ls0 ws0">10.9<span class="_ _0"> </span>To<span class="_ _6"> </span>implement<span class="_ _8"> </span>ﬁrst<span class="_ _8"> </span>ﬁt,<span class="_ _8"> </span>we<span class="_ _8"> </span>keep<span class="_ _6"> </span>track<span class="_ _6"> </span>of<span class="_ _6"> </span>bins<span class="_ _8"> </span><span class="ff3">b</span></div><div class="t m0 x8b h9 y44 ff3 fs2 fc0 sc0 ls0 ws0">i</div><div class="t m0 x8c h4 y44 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x8d h3 y45 ff2 fs1 fc0 sc0 ls0 ws0">,<span class="_ _6"> </span>which<span class="_ _6"> </span>have<span class="_ _6"> </span>more<span class="_ _6"> </span>room<span class="_ _6"> </span>than<span class="_ _8"> </span>any<span class="_ _6"> </span>of<span class="_ _6"> </span>the</div><div class="t m0 x14 h3 y46 ff2 fs1 fc0 sc0 ls0 ws0">lower<span class="_ _1"> </span>numbered<span class="_ _2"> </span>bins.<span class="_ _5"> </span>A<span class="_ _1"> </span>theoretically<span class="_ _1"> </span>easy<span class="_ _1"> </span>way<span class="_ _1"> </span>to<span class="_ _1"> </span>do<span class="_ _3"> </span>this<span class="_ _1"> </span>is<span class="_ _3"> </span>to<span class="_ _1"> </span>maintain<span class="_ _1"> </span>a<span class="_ _2"> </span>splay<span class="_ _1"> </span>tree</div><div class="t m0 x14 h3 y47 ff2 fs1 fc0 sc0 ls0 ws0">ordered<span class="_ _8"> </span>by<span class="_ _2"> </span>empty<span class="_ _8"> </span>space.<span class="_ _9"> </span>To<span class="_ _2"> </span>insert<span class="_ _8"> </span><span class="ff3">w</span></div><div class="t m0 x8e h4 y47 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x32 h3 y47 ff2 fs1 fc0 sc0 ls0 ws0">,<span class="_ _2"> </span>we<span class="_ _8"> </span>ﬁnd<span class="_ _2"> </span>the<span class="_ _8"> </span>smallest<span class="_ _2"> </span>of<span class="_ _8"> </span>these<span class="_ _8"> </span>bins,<span class="_ _2"> </span>which<span class="_ _2"> </span>has<span class="_ _8"> </span>at</div><div class="t m0 x14 h3 y48 ff2 fs1 fc0 sc0 ls0 ws0">least<span class="_"> </span><span class="ff3">w</span></div><div class="t m0 x55 h4 y48 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x8f h3 y48 ff2 fs1 fc0 sc0 ls0 ws0">empty<span class="_"> </span>space;<span class="_"> </span>after<span class="_ _d"> </span><span class="ff3">w</span></div><div class="t m0 x90 h4 y48 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x3f h3 y48 ff2 fs1 fc0 sc0 ls0 ws0">is<span class="_"> </span>added<span class="_"> </span>to<span class="_"> </span>the<span class="_"> </span>bin,<span class="_"> </span>if<span class="_ _7"> </span>the<span class="_"> </span>resulting<span class="_"> </span>amount<span class="_"> </span>of<span class="_"> </span>empty<span class="_"> </span>space<span class="_"> </span>is</div><div class="t m0 x14 h3 y49 ff2 fs1 fc0 sc0 ls0 ws0">less<span class="_ _3"> </span>than<span class="_ _4"> </span>the<span class="_ _3"> </span>inorder<span class="_ _3"> </span>predecessor<span class="_ _1"> </span>in<span class="_ _3"> </span>the<span class="_ _4"> </span>tree,<span class="_ _3"> </span>the<span class="_ _3"> </span>entry<span class="_ _3"> </span>can<span class="_ _3"> </span>be<span class="_ _3"> </span>removed;<span class="_ _3"> </span>otherwise,<span class="_ _3"> </span>a</div><div class="t m0 x14 h5 y4a ff3 fs1 fc0 sc0 ls0 ws0">DecreaseKey</div><div class="t m0 x91 h4 y4a ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x70 h3 y4a ff2 fs1 fc0 sc0 ls0 ws0">is<span class="_"> </span>performed.</div><div class="t m0 x14 h3 y4b ff2 fs1 fc0 sc0 ls0 ws0">To<span class="_ _6"> </span>implement<span class="_ _6"> </span>best<span class="_ _8"> </span>ﬁt,<span class="_ _8"> </span>we<span class="_ _6"> </span>need<span class="_ _6"> </span>to<span class="_ _6"> </span>keep<span class="_ _6"> </span>track<span class="_ _6"> </span>of<span class="_ _6"> </span>the<span class="_ _6"> </span>amount<span class="_ _6"> </span>of<span class="_ _8"> </span>empty<span class="_ _6"> </span>space<span class="_ _7"> </span>in<span class="_ _8"> </span>each<span class="_ _7"> </span>bin.</div><div class="t m0 x14 h3 y4c ff2 fs1 fc0 sc0 ls0 ws0">As<span class="_ _8"> </span>before,<span class="_ _8"> </span>a<span class="_ _2"> </span>splay<span class="_ _8"> </span>tree<span class="_ _6"> </span>can<span class="_ _8"> </span>keep<span class="_ _8"> </span>track<span class="_ _8"> </span>of<span class="_ _8"> </span>this.<span class="_ _9"> </span>To<span class="_ _2"> </span>insert<span class="_ _8"> </span>an<span class="_ _8"> </span>item<span class="_ _8"> </span>of<span class="_ _8"> </span>size<span class="_ _8"> </span><span class="ff3">w</span></div><div class="t m0 x92 h4 y4c ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x93 h3 y4c ff2 fs1 fc0 sc0 ls0 ws0">,<span class="_ _2"> </span>perform<span class="_ _6"> </span>an</div><div class="t m0 x14 h3 y4d ff2 fs1 fc0 sc0 ls0 ws0">insert<span class="_"> </span>of<span class="_"> </span><span class="ff3">w</span></div><div class="t m0 x94 h4 y4d ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x95 h3 y4d ff2 fs1 fc0 sc0 ls0 ws0">.<span class="_ _a"> </span>If<span class="_"> </span>there<span class="_"> </span>is<span class="_ _7"> </span>a<span class="_"> </span>bin<span class="_"> </span>that<span class="_ _7"> </span>can<span class="_"> </span>ﬁt<span class="_ _7"> </span>the<span class="_"> </span>item<span class="_"> </span>exactly,<span class="_ _7"> </span>the<span class="_"> </span>insert<span class="_"> </span>will<span class="_ _7"> </span>detect<span class="_"> </span>it<span class="_"> </span>and<span class="_"> </span>splay</div><div class="t m0 x14 h3 y4e ff2 fs1 fc0 sc0 ls0 ws0">it<span class="_ _7"> </span>to<span class="_ _7"> </span>the<span class="_"> </span>root;<span class="_ _7"> </span>the<span class="_"> </span>item<span class="_ _7"> </span>can<span class="_"> </span>be<span class="_"> </span>added<span class="_"> </span>and<span class="_"> </span>the<span class="_ _7"> </span>root<span class="_"> </span>deleted.<span class="_ _e"> </span>Otherwise,<span class="_"> </span>the<span class="_ _7"> </span>insert<span class="_"> </span>has<span class="_"> </span>placed</div><div class="t m0 x14 h5 y4f ff3 fs1 fc0 sc0 ls0 ws0">w</div><div class="t m0 x96 h4 y4f ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x97 h3 y4f ff2 fs1 fc0 sc0 ls0 ws0">at<span class="_ _7"> </span>the<span class="_ _7"> </span>root<span class="_ _7"> </span>(which<span class="_"> </span>eventually<span class="_ _7"> </span>needs<span class="_ _7"> </span>to<span class="_ _7"> </span>be<span class="_ _7"> </span>removed).<span class="_ _e"> </span>We<span class="_"> </span>ﬁnd<span class="_ _7"> </span>the<span class="_ _7"> </span>minimum<span class="_ _7"> </span>element<span class="_ _7"> </span><span class="ff3">M</span></div><div class="t m0 x72 h4 y4f ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x14 h3 y50 ff2 fs1 fc0 sc0 ls0 ws0">in<span class="_ _6"> </span>the<span class="_ _6"> </span>right<span class="_ _8"> </span>subtree,<span class="_ _6"> </span>which<span class="_ _6"> </span>brings<span class="_ _6"> </span><span class="ff3">M</span></div><div class="t m0 x63 h4 y50 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x98 h3 y50 ff2 fs1 fc0 sc0 ls0 ws0">to<span class="_ _6"> </span>the<span class="_ _6"> </span>right<span class="_ _6"> </span>subtree’s<span class="_ _6"> </span>root,<span class="_ _6"> </span>attach<span class="_ _7"> </span>the<span class="_ _6"> </span>left<span class="_ _6"> </span>subtree<span class="_ _6"> </span>to</div><div class="t m0 x14 h5 y51 ff3 fs1 fc0 sc0 ls0 ws0">M</div><div class="t m0 x99 h4 y51 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x9a h3 y51 ff2 fs1 fc0 sc0 ls0 ws0">,<span class="_ _7"> </span>and<span class="_ _6"> </span>delete<span class="_"> </span><span class="ff3">w</span></div><div class="t m0 x9b h4 y51 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x9c h3 y51 ff2 fs1 fc0 sc0 ls0 ws0">.<span class="_ _10"> </span>We<span class="_"> </span>then<span class="_ _7"> </span>perform<span class="_ _7"> </span>an<span class="_ _7"> </span>easily<span class="_ _7"> </span>implemented<span class="_ _7"> </span><span class="ff3">DecreaseKey</span></div><div class="t m0 x9d h4 y51 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x38 h3 y51 ff2 fs1 fc0 sc0 ls0 ws0">on<span class="_ _7"> </span><span class="ff3">M</span></div><div class="t m0 x9e h4 y51 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x3a h3 y51 ff2 fs1 fc0 sc0 ls0 ws0">to<span class="_ _7"> </span>reﬂect</div><div class="t m0 x14 h3 y52 ff2 fs1 fc0 sc0 ls0 ws0">the<span class="_"> </span>fact<span class="_"> </span>that<span class="_"> </span>the<span class="_"> </span>bin<span class="_"> </span>is<span class="_"> </span>less<span class="_"> </span>empty.</div><div class="t m0 x1 h3 y53 ff2 fs1 fc0 sc0 ls0 ws0">10.10<span class="_ _12"> </span><span class="ff3">Next<span class="_ _8"> </span>ﬁt:<span class="_ _2"> </span>12<span class="_ _2"> </span>bins<span class="_ _2"> </span></span>(.42,<span class="_ _2"> </span>.25,<span class="_ _2"> </span>.27),<span class="_ _8"> </span>(.07,<span class="_ _2"> </span>.72),<span class="_ _2"> </span>(.86,<span class="_ _8"> </span>.09),<span class="_ _2"> </span>(.44,<span class="_ _8"> </span>.50),<span class="_ _2"> </span>(.68),<span class="_ _2"> </span>(.73),<span class="_ _8"> </span>(.31),<span class="_ _8"> </span>(.78,</div><div class="t m0 x14 h3 y54 ff2 fs1 fc0 sc0 ls0 ws0">.17),<span class="_"> </span>(.79),<span class="_"> </span>(.37),<span class="_"> </span>(.73,<span class="_"> </span>.23),<span class="_ _7"> </span>(.30).</div><div class="t m0 x14 h3 y55 ff3 fs1 fc0 sc0 ls0 ws0">First<span class="_ _7"> </span>ﬁt:<span class="_ _7"> </span>10<span class="_"> </span>bins<span class="_ _7"> </span><span class="ff2">(.42,<span class="_ _7"> </span>.25,<span class="_ _7"> </span>.27),<span class="_ _7"> </span>(.07,<span class="_ _7"> </span>.72,<span class="_ _7"> </span>.09),<span class="_"> </span>(.86),<span class="_ _7"> </span>(.44,<span class="_"> </span>.50),<span class="_ _7"> </span>(.68,<span class="_"> </span>.31),<span class="_ _7"> </span>(.73,<span class="_"> </span>.17),<span class="_ _7"> </span>(.78),</span></div><div class="t m0 x14 h3 y56 ff2 fs1 fc0 sc0 ls0 ws0">(.79),<span class="_"> </span>(.37,<span class="_"> </span>.23,<span class="_ _7"> </span>.30),<span class="_"> </span>(.73).</div><div class="t m0 x14 h3 y57 ff3 fs1 fc0 sc0 ls0 ws0">Best<span class="_ _6"> </span>ﬁt:<span class="_ _7"> </span>10<span class="_ _6"> </span>bins<span class="_ _6"> </span><span class="ff2">(.42,<span class="_ _7"> </span>.25,<span class="_ _6"> </span>.27),<span class="_ _6"> </span>(.07,<span class="_ _7"> </span>.72,<span class="_ _6"> </span>.09),<span class="_ _6"> </span>(.86),<span class="_ _7"> </span>(.44,<span class="_ _6"> </span>.50),<span class="_ _7"> </span>(.68,<span class="_ _6"> </span>.31),<span class="_ _6"> </span>(.73,<span class="_ _7"> </span>.23),<span class="_ _6"> </span>(.78,</span></div><div class="t m0 x14 h3 y58 ff2 fs1 fc0 sc0 ls0 ws0">.17),<span class="_"> </span>(.79),<span class="_"> </span>(.37,<span class="_"> </span>.30<span class="_ _7"> </span>),<span class="_"> </span>(.73).</div><div class="t m0 x14 h3 y59 ff3 fs1 fc0 sc0 ls0 ws0">First<span class="_ _2"> </span>ﬁt<span class="_ _2"> </span>decreasing:<span class="_ _2"> </span>10<span class="_ _2"> </span>bins<span class="_ _2"> </span><span class="ff2">(.86,<span class="_ _2"> </span>.09),<span class="_ _2"> </span>(.79,<span class="_ _2"> </span>.17),<span class="_ _1"> </span>(.78,<span class="_ _2"> </span>.07),<span class="_ _2"> </span>(.73,<span class="_ _2"> </span>.27),<span class="_ _2"> </span>(.73,<span class="_ _2"> </span>.25),<span class="_ _2"> </span>(.72,</span></div><div class="t m0 x14 h3 y5a ff2 fs1 fc0 sc0 ls0 ws0">.23),<span class="_"> </span>(.68,<span class="_"> </span>.31),<span class="_ _7"> </span>(.50,<span class="_"> </span>.44),<span class="_"> </span>(.42,<span class="_"> </span>.37),<span class="_ _7"> </span>(.30).</div><div class="t m0 x14 h3 y5b ff3 fs1 fc0 sc0 ls0 ws0">Best<span class="_ _2"> </span>ﬁt<span class="_ _2"> </span>decreasing:<span class="_ _8"> </span>10<span class="_ _2"> </span>bins<span class="_ _2"> </span><span class="ff2">(.86,<span class="_ _2"> </span>.09),<span class="_ _8"> </span>(.79,<span class="_ _2"> </span>.17),<span class="_ _2"> </span>(.78),<span class="_ _2"> </span>(.73,<span class="_ _2"> </span>.27),<span class="_ _2"> </span>(.73,<span class="_ _2"> </span>.25),<span class="_ _8"> </span>(.72,<span class="_ _2"> </span>.23),</span></div><div class="t m0 x14 h3 y5c ff2 fs1 fc0 sc0 ls0 ws0">(.68,<span class="_"> </span>.31),<span class="_"> </span>(.50,<span class="_ _7"> </span>.44),<span class="_"> </span>(.42,<span class="_"> </span>.37,<span class="_ _7"> </span>.07),<span class="_"> </span>(.30).</div><div class="t m0 x14 h3 y5d ff2 fs1 fc0 sc0 ls0 ws0">Note<span class="_"> </span>that<span class="_"> </span>use<span class="_"> </span>of<span class="_"> </span>10<span class="_"> </span>bins<span class="_"> </span>is<span class="_ _7"> </span>optimal.</div><div class="t m0 x1 h3 y5e ff2 fs1 fc0 sc0 ls0 ws0">10.12<span class="_ _12"> </span>We<span class="_ _1"> </span>prove<span class="_ _2"> </span>the<span class="_ _3"> </span>second<span class="_ _2"> </span>case,<span class="_ _1"> </span>leaving<span class="_ _1"> </span>the<span class="_ _1"> </span>ﬁrst<span class="_ _3"> </span>and<span class="_ _2"> </span>third<span class="_ _1"> </span>(which<span class="_ _1"> </span>give<span class="_ _1"> </span>the<span class="_ _1"> </span>same<span class="_ _1"> </span>results<span class="_ _1"> </span>as</div><div class="t m0 x14 h3 y5f ff2 fs1 fc0 sc0 ls0 ws0">Theorem<span class="_"> </span>10.6)<span class="_"> </span>to<span class="_"> </span>the<span class="_"> </span>reader.<span class="_ _4"> </span>Observe<span class="_"> </span>that</div><div class="t m0 x2b h3 y60 ff2 fs1 fc0 sc0 ls0 ws0">log<span class="ff3"> </span></div><div class="t m0 x3d h9 y61 ff3 fs2 fc0 sc0 ls0 ws0">p</div><div class="t m0 x3e h4 y61 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x3f h5 y62 ff3 fs1 fc0 sc0 ls0 ws0">N</div><div class="t m0 x9f h4 y62 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 xa0 ha y62 ff3 fs1 fc0 sc0 ls0 ws0"> <span class="ff5">=</span> <span class="ff2">log</span> </div><div class="t m0 x98 h9 y61 ff3 fs2 fc0 sc0 ls0 ws0">p</div><div class="t m0 x32 h4 y61 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x65 h3 y62 ff2 fs1 fc0 sc0 ls0 ws0">(<span class="ff3">b</span></div><div class="t m0 x5e h6 y61 ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 xa1 h9 y61 ff3 fs2 fc0 sc0 ls0 ws0">m</div><div class="t m0 x40 h4 y61 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 xa2 ha y62 ff2 fs1 fc0 sc0 ls0 ws0">)<span class="ff3"> <span class="ff5">=</span> m</span></div><div class="t m0 x8d h6 y61 ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 xa3 h9 y61 ff3 fs2 fc0 sc0 ls0 ws0">p</div><div class="t m0 x44 h4 y61 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 xa4 h3 y62 ff2 fs1 fc0 sc0 ls0 ws0">log<span class="ff3"> </span></div><div class="t m0 x1a h9 y61 ff3 fs2 fc0 sc0 ls0 ws0">p</div><div class="t m0 x67 h4 y61 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 xa5 h5 y62 ff3 fs1 fc0 sc0 ls0 ws0">b</div><div class="t m0 x1d h4 y62 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x14 h3 y63 ff2 fs1 fc0 sc0 ls0 ws0">Working<span class="_"> </span>this<span class="_"> </span>through,<span class="_"> </span>Equation<span class="_"> </span>(10.9)<span class="_"> </span>becomes</div><div class="t m0 x96 h5 y64 ff3 fs1 fc0 sc0 ls0 ws0"> T</div><div class="t m0 xa6 h4 y64 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x18 h3 y64 ff2 fs1 fc0 sc0 ls0 ws0">(<span class="ff3">N</span></div><div class="t m0 xa7 h4 y64 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 xa8 ha y64 ff2 fs1 fc0 sc0 ls0 ws0">)<span class="ff3"> <span class="ff5">=</span> T</span></div><div class="t m0 xa9 h4 y64 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x90 h3 y64 ff2 fs1 fc0 sc0 ls0 ws0">(<span class="ff3">b</span></div><div class="t m0 xaa h6 y65 ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x87 h9 y65 ff3 fs2 fc0 sc0 ls0 ws0">m</div><div class="t m0 x78 h4 y65 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 xab ha y66 ff2 fs1 fc0 sc0 ls0 ws0">)<span class="ff3"> <span class="ff5">=</span> a</span></div><div class="t m0 x8e h6 y65 ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x32 h9 y65 ff3 fs2 fc0 sc0 ls0 ws0">m</div><div class="t m0 x33 h4 y65 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 xac h5 y66 ff3 fs1 fc0 sc0 ls0 ws0"> </div><div class="t m0 xad h9 y67 ff3 fs2 fc0 sc0 ls0 ws0">i</div><div class="t m0 xa1 h6 y67 ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 xae h8 y67 ff5 fs2 fc0 sc0 ls0 ws0">=<span class="ff2">0</span></div><div class="t m0 xae hb y68 ff5 fs3 fc0 sc0 ls0 ws0">Σ</div><div class="t m0 x5f h9 y69 ff3 fs2 fc0 sc0 ls0 ws0">m</div><div class="t m0 x5 h4 y66 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 xaf h4 y6a ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">B</span></div><div class="t m0 xaf h4 y66 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">C</span></div><div class="t m0 xaf h4 y6b ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">D</span></div><div class="t m0 xb0 h5 y6c ff3 fs1 fc0 sc0 ls0 ws0">a</div><div class="t m0 xb1 h5 y6d ff3 fs1 fc0 sc0 ls0 ws0">b</div><div class="t m0 xb2 h6 y6a ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x8c h9 y6a ff3 fs2 fc0 sc0 ls0 ws0">k</div><div class="t m0 xa3 h4 y6a ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 xb3 h5 y6e ff3 fs1 fc0 sc0 ls1 ws0">__<span class="_ _13"></span>_</div><div class="t m0 x45 h4 y66 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 xb4 h4 y6a ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">E</span></div><div class="t m0 xb4 h4 y66 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">F</span></div><div class="t m0 xb4 h4 y6b ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">G</span></div><div class="t m0 xb5 h9 y6f ff3 fs2 fc0 sc0 ls0 ws0">i</div><div class="t m0 xb6 h4 y6f ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 xb7 h5 y70 ff3 fs1 fc0 sc0 ls0 ws0">i</div><div class="t m0 xb8 h6 y65 ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 xb9 h9 y65 ff3 fs2 fc0 sc0 ls0 ws0">p</div><div class="t m0 xba h4 y65 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x67 h3 y66 ff2 fs1 fc0 sc0 ls0 ws0">log<span class="ff3"> </span></div><div class="t m0 xbb h9 y65 ff3 fs2 fc0 sc0 ls0 ws0">p</div><div class="t m0 x6 h4 y65 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x6a h5 y66 ff3 fs1 fc0 sc0 ls0 ws0">b</div><div class="t m0 x1f h4 y66 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x14 h3 y71 ff2 fs1 fc0 sc0 ls0 ws0">If<span class="_"> </span><span class="ff3">a</span></div><div class="t m0 xbc h4 y71 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x50 ha y71 ff3 fs1 fc0 sc0 ls0 ws0"> <span class="ff5">=</span> b</div><div class="t m0 x8f h6 y72 ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 xbd h9 y72 ff3 fs2 fc0 sc0 ls0 ws0">k</div><div class="t m0 xbe h4 y72 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x58 h3 y73 ff2 fs1 fc0 sc0 ls0 ws0">,<span class="_ _7"> </span>then</div><div class="t m0 x3d h5 y74 ff3 fs1 fc0 sc0 ls0 ws0">T</div><div class="t m0 x3f h4 y74 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x86 h3 y74 ff2 fs1 fc0 sc0 ls0 ws0">(<span class="ff3">N</span></div><div class="t m0 x79 h4 y74 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 xbf ha y74 ff2 fs1 fc0 sc0 ls0 ws0">)<span class="ff3"> <span class="ff5">=</span> a</span></div><div class="t m0 x32 h6 y75 ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x65 h9 y75 ff3 fs2 fc0 sc0 ls0 ws0">m</div><div class="t m0 xac h4 y75 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 xc0 h3 y76 ff2 fs1 fc0 sc0 ls0 ws0">log<span class="ff3"> </span></div><div class="t m0 x42 h9 y75 ff3 fs2 fc0 sc0 ls0 ws0">p</div><div class="t m0 x43 h4 y75 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x66 h5 y76 ff3 fs1 fc0 sc0 ls0 ws0">b</div><div class="t m0 xb0 h4 y76 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x8b h5 y76 ff3 fs1 fc0 sc0 ls0 ws0"> </div><div class="t m0 xc1 h9 y77 ff3 fs2 fc0 sc0 ls0 ws0">i</div><div class="t m0 xa3 h6 y77 ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 xc2 h8 y77 ff5 fs2 fc0 sc0 ls0 ws0">=<span class="ff2">0</span></div><div class="t m0 xc3 hb y78 ff5 fs3 fc0 sc0 ls0 ws0">Σ</div><div class="t m0 xc2 h9 y79 ff3 fs2 fc0 sc0 ls0 ws0">m</div><div class="t m0 xc4 h5 y76 ff3 fs1 fc0 sc0 ls0 ws0">i</div><div class="t m0 x48 h6 y75 ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 xb6 h9 y75 ff3 fs2 fc0 sc0 ls0 ws0">p</div><div class="t m0 xc5 h4 y75 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x2f ha y7a ff3 fs1 fc0 sc0 ls0 ws0"> <span class="ff5">=</span> O</div><div class="t m0 x32 h4 y7a ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x65 h3 y7a ff2 fs1 fc0 sc0 ls0 ws0">(<span class="ff3">a</span></div><div class="t m0 x5e h6 y7b ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 xa1 h9 y7b ff3 fs2 fc0 sc0 ls0 ws0">m</div><div class="t m0 x40 h4 y7b ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 xa2 h5 y7c ff3 fs1 fc0 sc0 ls0 ws0">m</div><div class="t m0 xc6 h6 y7b ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 xc7 h9 y7b ff3 fs2 fc0 sc0 ls0 ws0">p</div><div class="t m0 xb3 h6 y7b ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 xb1 h8 y7b ff5 fs2 fc0 sc0 ls0 ws0">+<span class="ff2">1</span></div><div class="t m0 x8d h3 y7c ff2 fs1 fc0 sc0 ls0 ws0">log<span class="ff3"> </span></div><div class="t m0 xc8 h9 y7b ff3 fs2 fc0 sc0 ls0 ws0">p</div><div class="t m0 xb8 h4 y7b ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 xb9 h5 y7c ff3 fs1 fc0 sc0 ls0 ws0">b</div><div class="t m0 x67 h4 y7c ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 xa5 h3 y7c ff2 fs1 fc0 sc0 ls0 ws0">)</div><div class="t m0 x14 h3 y7d ff2 fs1 fc0 sc0 ls0 ws0">Since<span class="_"> </span><span class="ff3">m</span></div><div class="t m0 x8f h4 y7d ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x56 ha y7d ff3 fs1 fc0 sc0 ls0 ws0"> <span class="ff5">=</span> <span class="ff2">log</span> N</div><div class="t m0 x9b h4 y7d ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x9c h3 y7d ff3 fs1 fc0 sc0 ls0 ws0">/<span class="ff2">log</span> b</div><div class="t m0 xc9 h4 y7d ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 xca h3 y7d ff2 fs1 fc0 sc0 ls0 ws0">,<span class="_ _6"> </span>and<span class="_"> </span><span class="ff3">a</span></div><div class="t m0 x86 h6 y7e ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 xcb h9 y7e ff3 fs2 fc0 sc0 ls0 ws0">m</div><div class="t m0 xa0 h4 y7e ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x78 ha y7f ff3 fs1 fc0 sc0 ls0 ws0"> <span class="ff5">=</span> N</div><div class="t m0 xcc h6 y7e ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x62 h9 y7e ff3 fs2 fc0 sc0 ls0 ws0">k</div><div class="t m0 x31 h4 y7e ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x64 h3 y7f ff2 fs1 fc0 sc0 ls0 ws0">,<span class="_ _7"> </span>and<span class="_"> </span><span class="ff3">b</span></div><div class="t m0 x42 h4 y7f ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x43 h3 y7f ff2 fs1 fc0 sc0 ls0 ws0">is<span class="_"> </span>a<span class="_"> </span>constant,<span class="_"> </span>we<span class="_"> </span>obtain</div><div class="t m0 xcd h5 y80 ff3 fs1 fc0 sc0 ls0 ws0">T</div><div class="t m0 xcb h4 y80 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 xaa h3 y80 ff2 fs1 fc0 sc0 ls0 ws0">(<span class="ff3">N</span></div><div class="t m0 x7a h4 y80 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 xce ha y80 ff2 fs1 fc0 sc0 ls0 ws0">)<span class="ff3"> <span class="ff5">=</span> O</span></div><div class="t m0 xcf h4 y80 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 xd0 h3 y80 ff2 fs1 fc0 sc0 ls0 ws0">(<span class="ff3">N</span></div><div class="t m0 x5f h6 y81 ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 xd1 h9 y81 ff3 fs2 fc0 sc0 ls0 ws0">k</div><div class="t m0 xa2 h4 y81 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x4 h3 y82 ff2 fs1 fc0 sc0 ls0 ws0">log<span class="ff3"> </span></div><div class="t m0 x8b h9 y81 ff3 fs2 fc0 sc0 ls0 ws0">p</div><div class="t m0 x8d h6 y81 ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 xc3 h8 y81 ff5 fs2 fc0 sc0 ls0 ws0">+<span class="ff2">1</span></div><div class="t m0 x46 h5 y82 ff3 fs1 fc0 sc0 ls0 ws0">N</div><div class="t m0 xc8 h4 y82 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 xd2 h3 y82 ff2 fs1 fc0 sc0 ls0 ws0">)</div><div class="t m0 x1 h3 y83 ff2 fs1 fc0 sc0 ls0 ws0">10.13<span class="_ _12"> </span>The<span class="_"> </span>easiest<span class="_"> </span>way<span class="_"> </span>to<span class="_"> </span>prove<span class="_"> </span>this<span class="_"> </span>is<span class="_"> </span>by<span class="_"> </span>an<span class="_"> </span>induction<span class="_"> </span>argument.</div><div class="t m0 x32 h3 y84 ff2 fs1 fc0 sc0 ls0 ws0">-55-</div></div><div class="pi" data-data='{"ctm":[1.568627,0.000000,0.000000,1.568627,0.000000,0.000000]}'></div></div>

数据结构与算法 数据结构与算法课后习题答案

数据结构与算法数据结构与算法课后习题答案