c - 这段代码的时间复杂度是多少？

Question

很难说出这里问的是什么。这个问题是含糊的、模糊的、不完整的、过于宽泛的或修辞性的，无法以目前的形式得到合理的回答。如需帮助澄清此问题以便重新打开它， visit the help center 。

已关闭 12 年前。

int i = 1;
while (i < n/2)
{
    i = i * 2;
    int j = i;

    while (j > 1)
        --j;
}

Answer 1

O(n):
外循环在每次迭代中运行logn次:i=1,2,4,8,...n/4(入口值)
内循环运行2*i次(入口值)
所以总的来说，你得到:2+4+8+...+n/2 = n-2 = O(n)