我发现这个算法计算 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
最佳答案
是的,绝对是。许多应聘者在编程面试中因为错过了这一点而得了不好的分数。
在 python 中切片列表会生成一个副本。
复制一半列表需要 O(n) 时间。
这个算法总共需要 O(n) 时间(你应该去弄清楚为什么它不是 O(n log n))
对于任何特定示例,您确实需要了解您的语言如何工作才能弄清楚这一点,因为某些语言提供了在不复制元素的情况下对列表进行切片的方法。在 java 中,您可以调用 list.sublist(start,end)
,例如,无需复制即可获取切片。
关于algorithm - 将数组拆分为 2 个子数组并递归求解它们仍然是 O(log(n))?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/57449839/