我的代碼更糟的時間複雜度是log（n）嗎？

Question

foo得到作爲參數具有不同數目一個排序的列表，並返回所有出現的計數的方法，使得：i == list[i]（其中i是索引0 <= i <= len(list)）。

def foo_helper(lst, start, end): 

    if start > end: 
     # end of recursion 
     return 0 

    if lst[end] < end or lst[start] > start: 
     # no point checking this part of the list 
     return 0 

    # all indexes must be equal to their values 
    if abs(end - start) == lst[end] - lst[start]: 
     return end - start + 1 

    middle = (end + start) // 2 

    print(lst[start:end+1], start, middle, end) 

    if lst[middle] == middle: 
     #print("lst[" , middle , "]=", lst[middle]) 
     return 1 + foo_helper(lst, middle+1, end) + foo_helper(lst, start, middle-1) 


    elif lst[middle] < middle: 
     return foo_helper(lst, middle+1, end) 
    else: 
     return foo_helper(lst, start, middle-1) 

def foo(lst): 
    return foo_helper(lst, 0, len(lst)-1) 

我的問題是，如果這個代碼的的最壞情況複雜 =的log（n）？
如果不是，我應該做什麼不同？

Answer 1

如果您N編號，所有獨特的和已知的列表進行排序，那麼如果list[0] == 0和list[N-1] == N-1，那麼唯一性和排序屬性決定了整個列表滿足屬性，list[i] == i。這可以在O(1)時間確定 - 只需檢查第一個和最後一個列表條目。

的獨特性和排序屬性強迫任何名單有三個獨立的區域 - 一個可能是空的前綴區域，其中list[i] < i，可能爲空的中間區域，其中list[i] == i，並且可能爲空的後綴區域，其中list[i] > i]。在一般情況下，找到中間區域需要O(n)時間 - 從前面掃描找到第一個索引list[i] == i，並從後面掃描找到最後一個這樣的索引（或者您可以使用一個正向掃描進行掃描） 。一旦你找到這些，你保證唯一性和命令所有索引之間將具有相同的屬性...

編輯：正如下面@tobias_k指出的，你也可以做一個二進制搜索找到兩個終點，這將是O(log n)而不是O(n)。如果你的輸入是完全一般的，這將是更好的選擇。

Answer 2

擴大我的評論，試圖思考這個問題。考慮代表指數的身份函數圖。我們想知道這個排序列表（一個嚴格單調函數）與表示索引y = x的行相交的位置，只考慮整數位置。我認爲你應該能夠在O（n）時間內找到這個（儘管我認爲它似乎是二分搜索的交集邊界應該工作），儘管我需要更仔細地看看你的代碼，看看它在做什麼。

因爲我們有獨特的元素排序列表，我們有i == list[i]無論在任何地方

在一個地方

，或者如果有多個地方，他們必須是連續的（一旦你在線以上，你永遠不會回來）

使用210

代碼：

import numpy as np 
import matplotlib.pyplot as plt 
a = np.unique(np.random.randint(-25, 50, 50)) 
indices = range(len(a)) 
plt.scatter(indices, indices, c='b') 
plt.scatter(indices, a, c='r') 
plt.show()