Временная сложность рекурсивной функции, где п размер уменьшает случайно

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 точек и список L, в котором мы сохраним k подмножеств Q (1 < = k < = n). Когда мы вычисляем первое подмножество, мы проходим через все n точек Q и ​​выбираем те, которые принадлежат первому подмножеству. Для второго подмножества мы проходим через все n точек Q, кроме тех, которые уже находятся в первом подмножестве и т. Д.

Таким образом, каждый рекурсивный вызов число точек будет уменьшаться на целое число x до тех пор, пока количество точек не будет 0. Это целое число x может отличаться от одного рекурсивного вызова другому (это может быть любое значение между 1 и n (n - текущее количество точек))

Какова была бы сложность моего алгоритма?

Я думал, что мое рекуррентное соотношение будет что-то вроде этого:

T (0) = 1

Т (п) = Т (п-х) + ап

Правильно ли это? и если да, то как я могу это решить?

Answer 1

без какой-либо информации о распределение точек в Q, мы не можем знать, как они будут отправлены в M или NM очередей.

Однако, вы можете легко вычислить наихудший сложность вашего алгоритма. Чтобы вычислить это, мы предполагаем, что при каждом рекурсивном вызове все точки в Q будут в конечном итоге в NM, за исключением того, который добавляется к M перед входом в цикл. С этим допущением x становится 1 в вашем рекуррентном отношении. И у вас есть O(n^2).