我知道这个公式是 T(n)=3T(n/2)+O(n),通过使用主定理,我可以得到 T(n)=n^(log3),其中底数为 2。 但是我仍然不知道如何在不使用主定理的情况下得出答案。因为我从递归公式中得到的结果是 T(n)=3^(logn),其中底数为 2。 如果有人能帮助我,我将非常感激!
那是因为你们两个同时都是正确的。n^(log3) = 3^(logn) 证明: y = 3^log(n) log(y) = log(n)*log(3) log(y)/log(n) = log(3) log<sub>n</sub>y = log(3) y = n^(log3)