将数组拆分为 2 个子数组并递归求解它们仍然是 O(log(n))？

Question

我发现这个算法可以计算 https://www.geeksforgeeks.org/median-of-two-sorted-arrays/ 上 2 个排序列表的中位数。它说，它是 O(log(n))。但真的是这样吗？

我感到困惑的是：这些行将数组拆分为 2 个子数组（使用 Python 的切片）并递归求解：

if n % 2 == 0: 
   return getMedian(arr1[:int(n / 2) + 1], 
      arr2[int(n / 2) - 1:], int(n / 2) + 1) 
else: 
   return getMedian(arr1[:int(n / 2) + 1],  
      arr2[int(n / 2):], int(n / 2) + 1)

但拆分数组对我来说看起来像 O(n)。所以在我看来，整个算法一定是O(n * log n)...

在这里，你可以看到我正在谈论的算法的全部代码：

# using divide and conquer we divide 
# the 2 arrays accordingly recursively 
# till we get two elements in each  
# array, hence then we calculate median 

#condition len(arr1)=len(arr2)=n 
def getMedian(arr1, arr2, n):  

    # there is no element in any array 
    if n == 0:  
        return -1

    # 1 element in each => median of  
    # sorted arr made of two arrays will     
    elif n == 1:  
        # be sum of both elements by 2 
        return (arr1[0]+arr2[1])/2

    # Eg. [1,4] , [6,10] => [1, 4, 6, 10] 
    # median = (6+4)/2     
    elif n == 2:  
        # which implies median = (max(arr1[0], 
        # arr2[0])+min(arr1[1],arr2[1]))/2 
        return (max(arr1[0], arr2[0]) + 
                min(arr1[1], arr2[1])) / 2

    else: 
        #calculating medians      
        m1 = median(arr1, n) 
        m2 = median(arr2, n) 

        # then the elements at median  
        # position must be between the  
        # greater median and the first  
        # element of respective array and  
        # between the other median and  
        # the last element in its respective array. 
        if m1 > m2: 

            if n % 2 == 0: 
                return getMedian(arr1[:int(n / 2) + 1], 
                        arr2[int(n / 2) - 1:], int(n / 2) + 1) 
            else: 
                return getMedian(arr1[:int(n / 2) + 1],  
                        arr2[int(n / 2):], int(n / 2) + 1) 

        else: 
            if n % 2 == 0: 
                return getMedian(arr1[int(n / 2 - 1):], 
                        arr2[:int(n / 2 + 1)], int(n / 2) + 1) 
            else: 
                return getMedian(arr1[int(n / 2):],  
                        arr2[0:int(n / 2) + 1], int(n / 2) + 1) 

 # function to find median of array 
def median(arr, n): 
    if n % 2 == 0: 
        return (arr[int(n / 2)] +
                arr[int(n / 2) - 1]) / 2
    else: 
        return arr[int(n/2)] 


# Driver code 
arr1 = [1, 2, 3, 6] 
arr2 = [4, 6, 8, 10] 
n = len(arr1) 
print(int(getMedian(arr1,arr2,n))) 

# This code is contributed by 
# baby_gog9800

Answer 1

是的，绝对是。许多应聘者在编程面试中因为错过了这个而得到了不好的分数。

在 python 中分割列表进行复制。

复制一半列表需要 O(n) 时间。

这个算法总共需要 O(n) 时间（你应该去弄清楚为什么它不是 O(n log n))

您真的需要知道您的语言是如何工作的，才能为任何特定示例弄清楚这一点，因为某些语言提供了在不复制元素的情况下对列表进行切片的方法。在java中你可以调用list.sublist(start,end)，例如，得到一个切片而不复制。

Answer 2

这里的问题是您混淆了实现与算法。这个 Python 实现是 O(n) 因为它执行线性时间切片操作，但是算法本身是 O(log(n)) 因为它实际上不需要执行复制切片中元素的线性时间操作——它可以在同一个列表上操作而无需创建新列表。这使得主定理中f(n) = O(1)，使得算法的总运行时间O(log n)。您可以选择以不需要切片的方式在 Python 中实现算法（例如，类似于 GeeksForGeeks 上的 C++ 和 Java 实现），这将运行在 O(log n)时间。

算法及其实现之间的区别是为什么算法分析是在伪代码上执行的，而不是在实际编程语言中的实现。像这样的实现细节经常会引起混淆。因此，算法往往根据其要求明确说明所使用的操作及其时间复杂度（如索引、切片等）。

将数组拆分为 2 个子数组并递归求解它们仍然是 O(log(n))？

Is splitting an array into 2 subarrays and solving them recursively still O(log(n))?

algorithm

runtime

time-complexity