擅长:python、mysql、java
<p>这个算法为列表中的每个元素返回一次<code>O(n)</code>,然后它还实现了一个二等分搜索<code>O(log n)</code>,因此,<code>O(n log n)</code></p>
<blockquote>
<p>But I can't figure out why? I struggle to figure the last row where we use recursion, I know that it's cutting the length of the list in half each time so its O(log n), but it add's to each iteration the other recursion which is also O(log n) each time so I though its O(log n log n) but unfortunately its not.</p>
</blockquote>
<p><code>O(log n) + O(log n)</code>=<code>O(log n)</code></p>
<p>在这上面添加一两个print语句会有很大帮助:</p>
<pre><code>def foo(x):
n = len(x)
print(x)
if n <= 1:
print("return")
return 17
return foo(x[:n//2]) + foo(x[n//2:])
>>> foo([1,2,3,4,5,6,7,8])
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4]
[1, 2]
[1]
Return
[2]
Return
[3, 4]
[3]
Return
[4]
Return
[5, 6, 7, 8]
[5, 6]
[5]
Return
[6]
Return
[7, 8]
[7]
Return
[8]
Return
</code></pre>
<p>这显然是为列表中的每个元素返回一次,这使得它至少是<code>O(n)</code>。另外,要在对分搜索类型方法中拆分列表,需要<code>O(log n)</code></p>