时间递归函数，其中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收到的一组q n个点和列表L，其中我们将保存Q个k个子集（1 < = k < = n）。当我们计算第一个子集时，我们遍历Q的所有n个点并选择属于第一个子集的那些点。对于第二个子集，除了那些已经在第一个子集中的那些点外，我们会遍历所有的n个点，等等。

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

那么我的算法的复杂度是什么呢？

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

T（0）= 1

T（N）= T（N-X）+一个

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

Answer 1

没有对点Q中分布的任何信息，我们无法知道它们将如何被分派到中号或NM队列。

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