擅长:python、mysql、java
<p>算法看起来好像需要的总时间与</p>
<pre><code>integral_0^N x dx = [(x^2)/2]_0^N = (N^2)/2 = O(N^2)
</code></pre>
<p>匹配<code>ab*</code>的字符串应该给出最坏情况下的行为。在</p>
<p>下面是一段代码,它在实验中演示了最坏情况下的行为。在</p>
<p>结构如下:</p>
<ol>
<li>定义<code>worstCase</code>函数,该函数构造长度为<code>N</code>的“错误”字符串</li>
<li>在这些字符串上测量函数的时间</li>
<li>创建<code>log(N)</code>与<code>log(time(N))</code>的数据集</li>
<li>拟合一条直线,试着估计直线的斜率:这是你的<code>O(N^p)</code>中的指数<code>p</code>。在</li>
</ol>
<p>代码如下:</p>
^{pr2}$
<p>以下是输出(需要一两分钟):</p>
<pre><code>4800 -> 0.057818
5760 -> 0.078123
6908 -> 0.105169
8292 -> 0.145572
9952 -> 0.197657
11940 -> 0.276103
14332 -> 0.382668
17196 -> 0.534682
20636 -> 0.747468
24764 -> 1.048267
29720 -> 1.475469
35664 -> 2.081608
42796 -> 2.939904
51356 -> 4.216063
61628 -> 5.963550
73952 -> 8.691849
88744 -> 12.126039
106492 -> 19.684188
127788 -> 24.942766
Exponent was: 1.867208
</code></pre>
<p>它估计指数为~1.86,接近2比接近3。在</p>