关于递归二分搜索的Big O Notation的问题

Question

我正在学习麻省理工学院举办的 Python 课程（2016 年秋季 6.0001），在他的一次讲座中，教授描述了 returns True 如果一个元素（ e) 在列表 (L) 中，False 否则：

def bisect_search1(L, e):
    if L == []:
        return False
    
    elif len(L) == 1:
        return L[0] == e
    
    else:
        half = len(L)//2
        if L[half] > e:
            return bisect_search1(L[:half], e)
        else:
            return bisect_search1(L[half:], e)

继续看下一张幻灯片，我知道二分搜索调用的复杂度为 O(log n)，因为每次循环或调用时输入都要减半。

我从幻灯片中仍然不明白的是以下几点：

O(n) 对于复制列表的每个二分搜索调用，这是设置每个调用的成本，所以对每个递归级别都这样做
如果我们真的很小心，请注意每次递归调用时要复制的列表的长度也会减半，结果复制的总成本为 O(n)，这占主导地位由于递归调用导致的 log n 成本

我还不明白的是：

切片列表的一部分和复制整个列表是否具有相同的大 O 复杂度 O(n)？
如果是的话，我明白为什么这个函数有O(n log n)的复杂度。但是，“ 证明复制的总成本为 O(n)，并且由于递归调用 ，这主导了 log n 成本”是什么意思？这是否意味着该函数现在具有 O(n) 复杂度？

如果之前有人问过类似的问题并且似乎是初学者，我很抱歉。

Answer 1

获取列表切片的成本为 O(m)，其中 m 是切片的大小。这是因为它必须创建一个大小为 m 的新列表并填充其条目。
在第一次调用时，切片的大小为 n/2。在第一个递归调用中，所采用的切片现在大小为 n/4。并且它在每个递归 call.The 上继续减少 1/2 切片的总成本因此是：O(n/2 + n/4 + n/8 + ...) = O(n)（取几何级数之和）。

Answer 2

切片列表所花费的时间与切片的长度成正比。如果您有一个大小为 n 的列表，并且要将其中的一半切片，则时间与 n/2 成正比，因此 O(n).

教授关于复制成本支配递归调用成本的引述只是说通常二分搜索是 O(log n)——递归调用的深度——但这里有还有一些复制，其中一些需要 O(n) 时间。您可以使用这些词来证明 O(n log n) 作为上限，但它们并不能证明确切的复杂性（实际上是 O(n)，因为每次复制的数量减半）。

关于递归二分搜索的Big O Notation的问题

Questions about Big O Notation of Recursive Bisection Search

algorithm

recursion

big-o

python-3.x