给定以下重复关系:
T(n)= T(n-x)+ T(x)+ O(min({x，n-x}))
T(1)= 1
其中x可以将我们的问题按任意比例划分(它可能因调用而异-不是n的恒定函数)，在一般情况下是否有可能获得优于O(n2)的约束？
(之所以这样问，是因为我研究了一种复杂性高的算法，这是这种递归关系的一个私有(private)案例，我不得不使用有关该算法的其他事实来证明O(n log n)的复杂性。但是，我认为它是可能是一个普通的数学问题，可以在更一般的情况下解决，如我在此处介绍的那样)
最佳答案
链接的问题提供了解决此问题的一种方法，但还有另一种方法可以在最坏的情况下更直接地为您提供O(n log n)解决方案。
您可以将递归关系视为将大小为n的数组切成小块的过程。在每个步骤中，您将两块中较小的一块涂上不同的颜色。当所有数组元素都切成各自独立的片段时，您会停下来，然后询问绘制数组元素的总次数。为了了解为什么这反映了您的过程，您在每一层上所做的工作都是基于较小作品的大小，因此您可以将花在绘制较小作品上的工作视为最小项的贡献。最终，一切都以1号开始触底。
我们可以将任何单个元素绘制为lg n的次数上限。要看到这一点，请注意，每绘制一块就不能超过开始时的一半。因此，如果是第一次绘画，则它的大小必须最大为n /2。如果是第二次绘画，则其所在的数组的最大大小必须为n / 4，甚至更大。通常，如果将其绘制k次，则其所在的数组的大小最多为n / 2i。选择i = lg n会使该尺寸为1，因此每件最多被涂一次lg n次。由于总共有n件，因此涂漆的总次数最多为n lg n。因此，您的递归求解为O(n log n)。
您可以证明，在每次将阵列完美地切成两半的情况下，此边界是紧密的。第一个切口执行n / 2的工作，接下来的两个执行n / 4的工作，接下来的四个执行n / 8的工作，依此类推。将所有切口加起来得出的总功为Θ(n log n)。
希望这可以帮助!
关于math - 解决涉及min的非标准递归关系？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13345240/