这个方法的Big-O复杂度是多少

Question

我们如何找到以下递归函数的BigO运行时？

public int foo(int x,int k) { 
 if (x <= k)
   return 1; 
 else
   return foo(x / k, k) + 1;
}

Answer 1

看看它在做什么，问问自己：

• 一个对方法的调用会调用自己多少次
• 使其终止的参数会发生什么变化

顺便说一句，你是说你的x是int吗？如果x == 1 and k == 2呢？使用整数除法，x/k为零。