我现在正试图用主定理来解决这个关系：
T（n）=2T（n/4）+对数n
我已经计算出a=2和b=4，但是我对log n感到困惑。
我的脚本说：c（n）（这里是logn）是big o（n^d）的元素。
如果我能在这里算出我的d，我会比较a和b^d，找出我的主定理。
但是，由于这里是log n，我不确定它的大O符号。
我的意思是我可以说它是O（n1/2）的元素，这会导致第二种情况，其中a和b^d是相同的，但它也是O（n1）的元素，这又是另一种情况。
最佳答案
一个有用的事实是，对于任何ε>0，我们知道
对数n=O（nε）。
我们也知道
对数n=Ω（1）
让我们看看这是否说明了什么。我们知道，对于任何ε>0，从上到下，你的递推都是以这个为界的：
s（n）=2s（n/4）+nε
让我们使用主定理我们有a=2，b=4，d=ε我们需要解释logb a=log4 2=1/2，以及它与d=ε的关系。让ε变小-比如，选择ε=0.000001。然后我们有logb ao（nlogb a）=o（n1/2）。
接下来，考虑这个递归关系：
r（n）=2r（n/4）+1
此重复次数是重复次数的下限利用主定理，我们也知道r（n）=Ω（n1/2）。
总的来说，我们看到你的复发率是O（n1/2）和Ω（n1/2），通过上下边界你的复发率越来越大和越来越小因此，即使主定理不适用于这里，您仍然可以使用主定理来声明运行时将是（n1/2）。
希望这有帮助！