擅长:python、mysql、java
<blockquote>
<p>I recall that nested if result in O(N^2)</p>
</blockquote>
<p>错误,嵌套的<code>for</code>循环的复杂度为<code>O(N^2)</code>,而不是<code>if</code>。在</p>
<p>如果你有一个N大小的数组</p>
<pre><code>for i in arr:
for j in arr:
print "hello"
</code></pre>
<p>你会看到“你好”印了多少次?N^2,这就是复杂性。在</p>
<p>请注意,在循环中做什么并不重要(无论是打印、添加还是执行if语句),这都是固定成本。因此,你重新安排if语句的事实并不重要-这两种情况都有完全相同的复杂性。在</p>
<p>重要的是while循环中的代码“主体”执行的频率,这决定了复杂性。在</p>
<p>因为两个例子都有相同的复杂性,所以让我们来分解第一个:</p>
^{pr2}$
<p><code>b</code>似乎是一个自变量,所以我们可以忽略它。如果<code>x</code>是<code>True</code>,那么时间复杂度是无穷大的,因为while循环永远不会结束(至少在整数<code>a</code>溢出为负数之前)。注意,这意味着您的语句“while loop has complexity O(n)”也是错误的)。如果<code>x</code>是<code>False</code>,那么代码的时间复杂度为<code>O(a-1)</code>(或者简单地说是<code>O(a)</code>),因为它将经历<code>a-1</code>次迭代。在</p>