java - 类似的递归情况，不同的运行时间？

Question

第一个的运行时间是 O(log n)，我知道这是大多数递归情况的运行时间。

int happy (int n, int m) { 
   if (n < 10) return n; 
   else if (n < 100) 
      return happy (n - 2, m); 
   else 
      return happy (n/2, m); 
} 

但是，第二个递归情况的运行时间是 O(n)

int silly(int n, int m) { 
   if (n < 1) return m; 
   else if (n < 10) 
     return silly(n/2, m); 
   else 
     return silly(n - 2, m); 
} 

谁能解释一下为什么吗？我真的很感激!

Answer 1

第一个函数减少 n比第二个快得多。 happy划分n 2 直到低于 100。silly 减去 2，直到低于 10。

happy是 O(log n)，因为它需要 log_2(n) 步直到低于 100，然后最多需要 50 步才能低于 1。

silly是 O(n)，因为需要 n/2 步才能低于 100，那么最多需要 5 步才能低于 1。