在递归函数时间复杂度在递归减小了尺寸

我估计时间解决的（复杂性）：在递归函数时间复杂度在递归减小了尺寸

// 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 
}

我首先想到的是，它应该是somwhere各地为O（n^2）。

O(2^n)

但是我认为第二个想法是错误的，因为n被递归调用之间降低：

然后我其中（根据WolframAlpha的）膨胀以想到

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

。

我也做了一些大型的基准测试。下面是结果：

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

来源

2016-01-22 peku33

这是什么语言？当然不是C++。 – SergeyA

很多时候当你降低成本在给定的时间内购买一定数量时，你会以某种形式的日志（n） – 2016-01-22 20:57:46

很难估计知道'WhatCanISolve'的工作原理。即何时可以返回null（w.r.t.列表大小）。 –

你的算法仍然是O（2 ^ñ），即使它通过每次一个项目减少了问题的规模。您的差分方程

T（N）= N + 2T（N-1）

~~不占在每个步骤中除去的物品的。但它仅删除一个项，所以该方程应当是T（N）= N + 2T（N-1） - 1.继你的例子和~~

通过使用WolframAlpha to solve this保存代数给出溶液T（Ñ）=（ç + 4）2 ^{ñ -1} - ñ - 2仍然为O（2 ^ñ）。它删除了一个项，考虑到其他因素（特别是递归），这不是一个相当大的数量。

想到的类似示例是n * n 2D矩阵。假设你只将它用于三角矩阵。即使删除一行来处理每一列，遍历每个元素仍然具有复杂度O（n ），这与使用所有元素（即方形矩阵）相同。

对于进一步的证据，我提出自己收集的运行时间数据的一个情节：

来源

2016-01-22 21:20:55 e0k

“您的差异公式并不考虑在每一步移除项目。”咦？它通过用n-1调用递归来解释它，并且完成的工作仍然是theta（n）（这也是为什么你仍然可以得到相同的结果，不论是否减1或任何其他常数）。另一方面，该图非常像n^2，这是你所期望的，因为第二次递归总是O（1）。 – Voo

为什么第二次递归总是O（1）？我们真的不知道它会做什么，因为伪代码没有指定。 – e0k

该列表不作为参数传递，而是该类的字段。显然，这是一种或另一种错误，但是查看图表，它也存在于真实的代码中。 – Voo

大概时间为二次。如果WhatCanISolve返回nullptr，当且仅当列表为空，则所有

Recursive(some other parameters 2);

会为O完成（1），因为它们与一个空表运行。这意味着，正确的公式实际上是

T(n) = C*n + T(n-1)

这意味着，T（N）=为O（n^2），其对应于井我们在图上看到的。

来源

2016-01-22 21:31:09

我们并不知道“其他参数”是什么。对代码做什么的更多说明会有所帮助。我们不知道'Recursive（）'调用中的任何一个是否必须总是返回基本情况（即在恒定时间内）。 – e0k

我们调用每次递归两次，这改变了公式。 – peku33

@ peku33在第一次递归返回之后，我们知道WhatCanISolve在第二次递归时也会返回null，这使得它成为O（1）。当然，代码中的一个错误（在共享列表上递归是......很奇怪，至少可以说，我不能想到在这种形式下有意义的任何枪战），但就目前而言，这是正确的答案。 – Voo

在递归函数时间复杂度在递归减小了尺寸

回答

相关问题