java - 这个函数的T(n)怎么写？

Question

我在 Python 交互式网站上偶然发现了这个问题，我想知道如何在 Java 中计算这一步的持续时间，以便我可以显示它的时间效率。

int i = n;
while (i > 0)
{
    int k = 2 + 2;
    i = i / 2;
}

Answer 1

假设输入 n = i = 2^x。

每一步都将 i 除以 2:因此 i = 2^x 变为 2^x-1。

重复直到 0，i。 e. 2^-1。 (*)

所以步数 = x ~ log₂n

---

*实际上，2^-1 = 1/2，但就整数除法而言，这将是 2⁰ = 1 除以 2 的最后一步，结果 0.