algorithm - 带有Θ（log n）的Java递归算法示例

Question

我找了很多天，我尝试了很多递归算法示例，但我找不到任何具有Θ( log n )运行时间的算法。
你知道java中有什么递归算法吗T(n) = Θ( log n )？T(n)表示算法基本操作执行次数的函数在哪里。
非常感谢任何帮助。
谢谢！

Answer 1

e作为一个例子，考虑找到一个整数的最大整数指数，m使得 m ^e | n，对于某个整数n：

findBiggestExponent(int n, int m)
{
    if(n % m == 0)
        return 1 + findBiggestExponent(n/m, m);
    else
        return 0;
}

显然e <= log n成立。并且由于递归算法计算e为一个的和，因此算法的复杂度为O(log n)。