c++ - 递归函数的时间复杂度，其中递归减少了大小

Question

我必须估计 Solve() 的时间复杂度:

// Those methods and list<Element> Elements belongs to Solver class

void Solver::Solve()
{
    while(List is not empty)
        Recursive();
}

void Solver::Recursive(some parameters)
{

    Element WhatCanISolve = WhatCanISolve(some parameters); //O(n) in List size. When called directly from Solve() - will always return valid element. When called by recursion - it may or may not return element
    if(WhatCanISolve == null)
        return;

    //We reduce GLOBAL problem size by one.
    List.remove(Element); //This is list, and Element is pointed by iterator, so O(1)

    //Some simple O(1) operations


    //Now we call recursive function twice.
    Recursive(some other parameters 1);
    Recursive(some other parameters 2);
}

//This function performs search with given parameters
Element Solver::WhatCanISolve(some parameters)
{
    //Iterates through whole List, so O(n) in List size
    //Returns first element matching parameters
    //Returns single Element or null
}

我的第一个想法是它应该在 O(n^2) 左右。

然后我想到了

T(n) = n + 2T(n-1)

(根据 wolframalpha)扩展为:

O(2^n)

但是我认为第二个想法是错误的，因为 n 在递归调用之间减少了。

我还对大型数据集进行了一些基准测试。以下是结果:

N       t(N) in ms
10000   480
20000   1884
30000   4500
40000   8870
50000   15000
60000   27000
70000   44000
80000   81285
90000   128000
100000  204380
150000  754390

Answer 1

您的算法仍然是 O(2ⁿ)，即使它每次都将问题大小减少一项。你的差分方程

T(n) = n + 2T(n-1)

不考虑在每一步中删除一个项目。但它只删除了一项，所以等式应该是 T(n) = n + 2T(n-1) - 1。按照你的例子和

使用 WolframAlpha to solve this 保存代数给出解 T(n) = (c₁ + 4) 2^n-1 - n - 2 仍然是 O(2ⁿ)。它删除了一个项，考虑到其他因素(尤其是递归)，这不是一个可观的数量。

想到的一个类似例子是 n*n 二维矩阵。假设您只将它用于三角矩阵。即使您为每一列删除一行进行处理，遍历每个元素仍然具有 O(n²) 的复杂度，这与使用所有元素一样(即方阵)。

为了进一步的证据，我提供了您自己收集的运行时间数据的图表: