algorithm - 包含两个递归调用的算法的预期运行时间

Function(A, n)
/* A is an array of integers
/* random is a function that returns an integer between 1 and (in this case) n-1

    if(n<=1) then return (A[1])
    else
      x←0；
      for i←1 to n-1 do
         A[i]←A[i]-A[i+1]
         x←x+A[i]
      end
      k←Random(n-1)
      x←x+Function(A,k)
      x←x+Function(A,n-k)
      return(x)
    end

我不明白为什么这个算法最坏的情况是当k=1或n-1时，而最好的情况是当k=n/2时。如何保证2et（n/2）的预期运行时间小于et（n-1）？

最佳答案

您的代码具有与快速排序相同的递归结构。
所以像QuickSort一样，最坏的情况（k总是1，或者k总是n-1）是O（n^2），平均情况是O（n logn）。
最坏情况下代码的递归关系是

 T(n) = n + T(n-1)

（用望远镜解为T（n）=O（n^2）
代码预期运行时间的重复关系为：

 T(n) = n + sum(k=1..n-1)[T(k) + T(n-k)]/(n-1)

注意有一个和，它根据随机值k计算平均运行时间。
这有点棘手，但可以在这里找到分析：https://en.wikipedia.org/wiki/Quicksort#Using_recurrences

关于algorithm - 包含两个递归调用的算法的预期运行时间，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/44223411/