n 大小随机减小的递归函数的时间复杂度

Question

我创建了以下伪代码，但我不确定如何计算它的复杂性：

（伪代码）

MyFunction(Q, L)
    if (Q = empty) return

    M = empty queue
    NM = empty queue

    M.Enqueue(Q.Dequeue)

    while (Q is not empty)
        pt = Q.Dequeue()
        if (pt.y > M.peek().y) M.Enqueue(pt)
        else NM.Enqueue(pt)

    L.add(M)
    if (NM is not empty) MyFunction(NM, L)

    return L;

MyFunction 接收一个包含 n 个点的集合 Q 和一个列表 L，我们将在其中保存 Q 的 k 个子集 (1<=k<=n)。当我们计算第一个子集时，我们遍历 Q 的所有 n 个点和 select 个属于第一个子集的点。对于第二个子集，我们遍历 Q 的所有 n 个点，除了那些已经在第一个子集中的点，依此类推。

因此，每次递归调用点数都会减少一个整数x，直到点数为0。这个整数x可以不同于一个递归调用另一个（它可以是1之间的任何值和 n（n 是当前点数））

那么我的算法的复杂度是多少？

我在想我的递推关系应该是这样的：

T(0) = 1

T(n) = T(n-x) + 一个

这是正确的吗？如果是，我该如何解决？

Answer 1

没有关于Q中点分布的任何信息，我们无法知道它们将如何分配到M或NM 个队列。

但是，很容易计算出算法的最坏情况复杂度。为了计算这一点，我们假设在每次递归调用时，Q 中的所有点都将在 NM 中结束，除了在进入循环之前被添加到 M 中的点。有了这个假设， x 在你的递归关系中变成 1 。你最终得到 O(n^2).

n 大小随机减小的递归函数的时间复杂度

Time complexity of a recursive function where n size reduces randomly

algorithm

recurrence

time-complexity