algorithm - 算法的运行时间？

Question

我需要找到此算法的运行时间作为 k 的函数，其中 k 是 n 中的位数。

def ff(n):
    x = 0
    while ((x+1)*(x+1) <= n):
        x+=1
    return x

我明白了，运行时间是 O(sqrt(n))，如果 n 是一个小数，我如何将它转换为 k 的函数？我不需要直接回答，非常感谢解释。

谢谢

Answer 1

如果我没记错的话上限是

• k=log2(n)
• n=2^k
• 所以:
• T(sqrt(n)) -> T(sqrt(2^k)) -> T((2^k)^0.5) -> T((2^(k/2))
• 对于 T 的混淆感到抱歉，但我来自运行时的地方习惯于使用 T 而不是 O
• O 是为复杂性保留的 (Omega)

附言。

• 你应该测量运行时间，因为在现代机器上
• 代码与它的执行看起来非常不同
• 由于多个管道、缓存、硬件功能等......
• 特别是对于有限/低 n