時間遞歸函數，其中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)。