擅长:python、mysql、java
<p>你正确地识别了<strong>它是</strong>O(logn),但是你没有识别出<strong>它</strong>是什么。<strong>它</strong>是达到基本情况所需的步骤数。因为每次将列表切成两半,每次调用<code>foo</code>,您使用的是一个只有刚才列表大小一半的列表。因此,需要O(logn)步骤来达到基本情况。在</p>
<p>下一个问题是:每一步要做多少工作?在第一步中,列表被分成两半,这需要<code>n</code>个内存副本。在第二步中,<strong>两个<code>n/2</code>大小的列表被分成两半。工作量不变!从一个步骤到下一步,您要剪切的每个列表的大小(由于调用<code>foo(n//2)</code>),但是您必须为<strong>执行此操作的列表的数量加倍</strong>(因为您递归地调用了<code>foo</code>)。因此,对于每一步,你总是在做O(n)功。在</p>
<p>O(logn)步骤*O(n)每个步骤的功=O(n logn)总计。在</p>