我的代码更糟的时间复杂度是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()