c++ - 整数除法的渐近估计

Question

k = n; //integer division
while(k > 1) {
    std::cout << k; 
    k=k/2;
}

我需要找出作为 n 函数的渐近估计。

Answer 1

复杂度是对数的。

假设 K 为非负数，除以 2 相当于右移一位。因此，在变为 0 之前的最大迭代次数k是 中的位数k。更具体地说，设置的最高有效位的位置k（即 a 1）将确定循环中执行的迭代次数。

由于循环中的操作（可能）是恒定的复杂度，因此对数迭代次数直接导致对数复杂度。