请教关于median of two sorted array的时间复杂度

这个是网上看到的解法， 就是针对A和B分别二分， 然后网上说时间复杂度是log(m+n), m=len(A), n=len(B), 就想问为什么不是logm+logn? 多谢！

class Solution:
    """
    @param A: An integer array.
    @param B: An integer array.
    @return: a double whose format is *.5 or *.0
    """
    def findMedianSortedArrays(self, A, B):
        n = len(A) + len(B)
        if n % 2 == 1:
            return self.findKth(A, 0, B, 0, n // 2 + 1)
        else:
            smaller = self.findKth(A, 0, B, 0, n // 2)
            bigger = self.findKth(A, 0, B, 0, n // 2 + 1)
            return (smaller + bigger) / 2

    def findKth(self, A, index_a, B, index_b, k):
        if len(A) == index_a:
            return B[index_b  + k - 1]
        if len(B) == index_b:
            return A[index_a + k - 1]
        if k == 1:
            return min(A[index_a], B[index_b])

        a = A[index_a + k // 2 - 1] if index_a + k // 2 <= len(A) else None
        b = B[index_b + k // 2 - 1] if index_b + k // 2 <= len(B) else None

        if b is None or (a is not None and a < b):
            return self.findKth(A, index_a + k // 2, B, index_b, k - k // 2)
        return self.findKth(A, index_a, B, index_b + k // 2, k - k // 2)

这个不是分别二分，是一起二分的。就是A和B各维护一个指针index_a, index_b，然后每次各走k/2步(只要没走到结尾)，比较后舍弃其中k/2个元素（可能舍弃A的，也可能舍弃B的）。由于k=(m+n)/2，每次循环舍弃的元素个数依次为(m+n)/4, (m+n)/8, (m+n)/16....，因此理论上复杂度是log(m+n)。真实情况中，如果A B长度差别较大，复杂度会优于log(m+n)。
可以参考下这个讲解：https://leetcode.wang/leetCode-4-Median-of-Two-Sorted-Arrays.html

这两个时间复杂度是等价的：

(1) log(m + n) <= log( 2 * max{m, n} ) <= max{log2m, log2n} <= log2m + log2n ~ O(log(m) + log(n))

(2) log(m) + log(n) <  log(m + n) + log(m + n)  ~ O( log(m + n) )

综合(1) + (2)，我们有 O(log(m) + log(n)) = O(log(m + n))

明白了， 谢谢楼上的大佬们！