第一个的运行时间是 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);
}
谁能解释一下为什么吗?我真的很感激!
最佳答案
第一个函数减少 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。
关于java - 类似的递归情况,不同的运行时间?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21324233/