如何找到递归关系，并计算归并排序代码的大定理？

Question

我试图找到这个合并排序代码的主定理，但首先我需要找到它的递归关系，但我很难做到并理解两者。我已经在这里看到了一些类似的问题，但无法理解解释，比如，首先我需要找到代码有多少操作？有人可以帮我吗？


def mergeSort(alist):
    print("Splitting ",alist)
    if len(alist)>1:
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        mergeSort(lefthalf)
        mergeSort(righthalf)

        i=0
        j=0
        k=0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                alist[k]=lefthalf[i]
                i=i+1
            else:
                alist[k]=righthalf[j]
                j=j+1
            k=k+1

        while i < len(lefthalf):
            alist[k]=lefthalf[i]
            i=i+1
            k=k+1

        while j < len(righthalf):
            alist[k]=righthalf[j]
            j=j+1
            k=k+1
    print("Merging ",alist)

alist = [54,26,93,17,77,31,44,55,20]
mergeSort(alist)
print(alist)

Answer 1

要使用主定理确定分治算法的运行时间，您需要将算法的运行时间表示为输入大小的递归函数，在表格：

T(n) = aT(n/b) + f(n)

T(n) 是我们在输入大小 n 上表达算法总运行时间的方式。

a代表算法进行的递归调用次数。

T(n/b) 表示递归调用：n/b 表示递归调用的输入大小是原始输入大小的某个特定分数（divide分而治之的一部分）。

f(n) 表示算法主体需要做的工作量，一般只是将递归调用的解决方案组合成一个整体解决方案（你可以说这是征服部分）。

这里有一个稍微重构的 mergeSort 定义：

def mergeSort(arr):
  if len(arr) <= 1: return # array size 1 or 0 is already sorted
  
  # split the array in half
  mid = len(arr)//2
  L = arr[:mid]
  R = arr[mid:]

  mergeSort(L) # sort left half
  mergeSort(R) # sort right half
  merge(L, R, arr) # merge sorted halves

我们需要确定，a、n/b和f(n)

因为每次调用 mergeSort 都会进行两次递归调用：mergeSort(L) 和 mergeSort(R)，a=2:

T(n) = 2T(n/b) + f(n)

n/b 表示进行递归调用的当前输入的分数。因为我们正在寻找中点并将输入分成两半，将当前数组的一半传递给每个递归调用，n/b = n/2 和 b=2。（如果每个递归调用得到原始数组的 1/4 b 将是 4）

T(n) = 2T(n/2) + f(n)

f(n) 表示算法除了进行递归调用之外所做的所有工作。每次我们调用 mergeSort 时，我们都会在 O(1) 时间内计算中点。我们还将数组拆分为 L 和 R，从技术上讲，创建这两个子数组副本的时间复杂度为 O(n)。然后，假设mergeSort(L)对数组的左半部分进行了排序，mergeSort(R)对数组的右半部分进行了排序，我们仍然需要将已排序的子数组合并在一起以对整个数组进行排序merge 功能。这使得 f(n) = O(1) + O(n) + complexity of merge。现在让我们来看看 merge:

def merge(L, R, arr):
  i = j = k = 0    # 3 assignments
  while i < len(L) and j < len(R): # 2 comparisons
    if L[i] < R[j]: # 1 comparison, 2 array idx
      arr[k] = L[i] # 1 assignment, 2 array idx
      i += 1        # 1 assignment
    else:
      arr[k] = R[j] # 1 assignment, 2 array idx
      j += 1        # 1 assignment
    k += 1          # 1 assignment

  while i < len(L): # 1 comparison
    arr[k] = L[i]   # 1 assignment, 2 array idx
    i += 1          # 1 assignment
    k += 1          # 1 assignment

  while j < len(R): # 1 comparison
    arr[k] = R[j]   # 1 assignment, 2 array idx
    j += 1          # 1 assignment
    k += 1          # 1 assignment

此函数还有更多功能，但我们只需要了解它的整体复杂度 class 即可准确应用主定理。我们可以计算每一个操作，即每一个比较、数组索引和赋值，或者只是更一般地推理它。一般而言，您可以说，在三个 while 循环中，我们将遍历 L 和 R 的每个成员，并将它们按顺序分配给输出数组 arr，为每个元素执行恒定量的工作。请注意，我们正在处理 L 和 R 的每个元素（总共 n 个元素）并且为每个元素做恒定量的工作就足以说明合并在 O(n) 中。

但是，如果需要，您可以对计数操作进行更具体的操作。对于第一个 while 循环，每次迭代我们进行 3 次比较、5 次数组索引和 2 次赋值（常量），然后循环运行s 直到 L 和 R 中的一个被完全处理。然后，接下来的两个 while 循环之一可能运行处理来自另一个数组的任何剩余元素，对每个元素执行 1 次比较、2 次数组索引和 3 次变量赋值（持续工作）。因此，因为 L 和 R 的 n 个总元素中的每一个都会导致在 while 循环中执行最多恒定数量的操作（根据我的计算，10 或 6，所以最多 10），并且 i=j=k=0语句只有3个常量赋值，merge在O(3 + 10*n) = O(n)中。回到整体问题，这意味着：

f(n) = O(1) + O(n) + complexity of merge
     = O(1) + O(n) + O(n)
     = O(2n + 1)
     = O(n)

T(n) = 2T(n/2) + n

应用主定理之前的最后一步：我们希望将 f(n) 写为 n^c。对于 f(n) = n = n^1, c=1。（注意：如果 f(n) = n^c*log^k(n) 而不是简单的 n^c，情况会发生轻微变化，但我们在这里不需要担心）

您现在可以应用主定理，其最基本的形式是将 a（递归调用数量增长的速度）与 b^c（工作量增长的速度）进行比较每个递归调用收缩）。有 3 种可能的情况，我试图解释其中的逻辑，但是如果它们没有帮助，您可以忽略括号中的解释：

a > b^c, T(n) = O(n^log_b(a))。（递归调用总数的增长速度快于每次调用工作量的减少速度，因此总工作量由递归树底层的调用次数决定。调用次数从 1 开始乘以 a log_b(n)次，因为log_b(n)是递归树的深度。因此，total work = a^log_b(n) = n^log_b(一个))
a = b^c, T(n) = O(f(n)*log(n))。（调用次数的增长与每次调用工作量的减少相平衡。因此，递归树每一层的工作量是恒定的，因此总工作量只是 f(n)*(树的深度) = f(n) *log_b(n) = O(f(n)*log(n))
a < b^c, T(n) = O(f(n))。（每次调用的工作量减少得比调用次数的增加快。因此，总工作量主要由递归树顶层的工作量决定，即 f(n)）

对于 mergeSort 的情况，我们已经看到 a = 2、b = 2 和 c = 1。作为 a = b^c，我们应用第二种情况：

T(n) = O(f(n)*log(n)) = O(n*log(n))

大功告成。这看起来工作量很大，但是你做的越多，推导 T(n) 就越容易，而且一旦你推导出推导式，你就可以很快地检查它属于哪种情况，这使得主定理非常有用解决更复杂 divide/conquer 重复问题的有用工具。

如何找到递归关系，并计算归并排序代码的大定理？

How to find the recurrence relation, and calculate Master Theorem of a Merge Sort Code?

python

performance

recurrence

mergesort

master-theorem