算法的运行时间是多少？是 O(sqrt(n)) 还是 O(log(n))？

Question

编辑：约束值范围 [2,1000000000] 和 a<=b

 def sqrtoccurrence(a: Int, b: Int): Int = {
        val sqrtA = Math.ceil(Math.sqrt(a)).toInt
        val sqrtB = Math.floor(Math.sqrt(b)).toInt
        if(sqrtA > sqrtB) 0
        else 1 + sqrtoccurrence(sqrtA, sqrtB)      
      }

是 O(sqrt(n)) 还是 O(log(n))？我不擅长计算递归运行次。我知道它的树的深度以及调用递归函数的次数。在这种情况下，恒定工作 sqrt 会影响多少，所以是否可以忽略它？但也许我错了。有很大帮助的解释。谢谢

Answer 1

以下是我对必要的运行时间的推理。在 a > b 的最佳情况下，不需要递归，因此它是 O(1) 操作。当 a <= b 使 ceil(sqrt(a)) > floor(sqrt(b)) 成为可能的唯一方法是 a 和 b 的重复 sqrt() 将它们的差异减小到小于四舍五入错误。

在最坏的情况下，我们正在研究大 b "shrinks" 的重复 sqrt() 如何满足小 a 的终止要求].因此，我将函数在输入 n 上的运行时间描述为：

T(n) = T(sqrt(n)) + C  // where C is O(1)

为了计算必要递归的大致数量，r，我们可以在递归结束时查看 n 的重复 sqrt() 的最终值，比如说 m，建立一个等式，逻辑如下：

m is the result of applying sqrt() to n for r times

因此，

(..(m^2)^2)^2 ... )^2 = n  // `r` times of `^2`

即

m^(2^r) = n

这意味着：

2^r = log(n)     // log base `m`

r = log(log(n))  // outer log base `2`

因此，时间复杂度为O(log(log(n)))。

sqrtoccurrence(2, 10)           // 1
sqrtoccurrence(2, 100)          // 2
sqrtoccurrence(2, 1000)         // 3
sqrtoccurrence(2, 1000000)      // 4
sqrtoccurrence(2, Int.MaxValue) // 4

def log2(x: Double): Double = math.log(x) / math.log(2)

log2(log2(10))           // 1.732
log2(log2(100))          // 2.732
log2(log2(1000))         // 3.317
log2(log2(1000000))      // 4.317
log2(log2(Int.MaxValue)) // 4.954

Answer 2

从另一个答案我们有

T(n) = T(sqrt(n)) + C

现在让

2^m = n

重写

T(2^m) = T(sqrt(2^m)) + C
       = T(2^(m/2)) + C

让我们定义一个新函数

S(m) = T(2^m)

然后

S(m) = T(2^m)
     = T(2^(m/2)) + C
     = S(m/2) + 2C

我们现在知道

S(m) = O(log m)

因此

T(n) = T(2^m) = S(m) = O(log m) = O(log log n)

算法的运行时间是多少？是 O(sqrt(n)) 还是 O(log(n))？

What is the running time of the algorithm? is it O(sqrt(n)) or O(log(n))?

algorithm

performance

big-o

scala

runtime