给定函数的复杂性

Question

当我分析下面代码段的复杂性时,我发现它是O(n/2).但在搜索互联网时,我发现它可能是O(n).我想知道谁是对的.

void function(int n) {
    int i = 1, k = 100;
    while (i < n) {
        k++;
        i += 2;
    }
}

Answer 1

上述方法中变量k的重点是什么？无论大O符号都谈到极限行为(因为n的值接近无穷大).因此,big-O表示法与BOTH缩放因子和常量无关.也就是说,对于任何常数"c"和缩放因子"s"

O(f(n))相当于O(s*f(n)+ c)

在你的情况下,f(n)= n,s = 1/2,c = 0.所以......

O(n)= O(n/2)

Answer 2

O(n)与O(n/2)相同

big-O表示法的概念是理解算法运行的速度,因为你给它一个更大的输入.因此,例如,如果您将输入的大小加倍,程序将花费两倍的时间,还是需要4倍的时间.

由于n和n/2的行为与你改变N的值相同(即如果你将N增加10倍,则N本身和N/2的比例相同).