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

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center。
                            
                        
                    
                
                                6年前关闭。
            
                    

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

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

最佳答案

复杂度是对数的。

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

由于循环中的操作（大概是）恒定的复杂度，所以对数迭代次数直接导致对数复杂度。

关于c++ - 整数除法的渐近估计，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/16321856/