确定大O表示法

Question

我需要帮助理解/做大O符号.我理解它的目的,我只是不知道如何"确定给定一段代码的复杂性".

确定以下各项的Big O表示法

一个.

n=6;
cout<<n<<endl;

湾

n=16;
for (i=0; i<n; i++)
    cout<<i<<endl;

C.

i=6;
n=23;
while (i<n) {
    cout<<i-6<<endl;
    i++;
}

d.

int a[ ] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
n=10;
for (i=0; i<n; i++)
    a[i]=a[i]*2;
for (i=9; i>=0; i--)
    cout<<a[i]<<endl;

即

sum=0;
n=6;
k=pow(2,n);
for (i=0;i<k;i++)
    sum=sum+k;

Answer 1

大O表示算法复杂性的顺序.

基本的东西:

• 这种复杂性是根据条目大小来衡量的
• 你选择一个单位操作(通常是做作或比较)
• 您可以计算此操作的调用时间
• 当使用复杂度时,通常忽略常数项或常数因子,因此如果操作次数为3*n ^ 3 + 12,则将其简化为n ^ 3,也标记为O(n ^ 3)

a.)只运行一次,没有循环,复杂性在这里是微不足道的O(1)

b.)在循环中调用n次:O(n)

c.)这里我们选择分析n(因为它通常是算法中的递增变量).通话次数为n - 6,所以这是O(n).

d.)我们假设这里10(n)是你的数组的大小和9(i)这个大小减1.对于n的每个值,我们必须从0到n然后从n-1到n*(n-1)运算,技术上:O(n * 2)有些人近似为O(n).两者都称为线性时间,不同的是BigO不关心的线的斜率.

e.)循环从0到pow(2,n),即1到2 ^ n,总结为O(2^n)