algorithm - 确定大O表示法

我需要帮助来理解/做大O符号。我了解它的目的，只是不知道如何“确定一段代码的复杂性”。

确定以下每个的Big O表示法

一种。

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

b。

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;

e。

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

最佳答案

大O表示算法的complexity的顺序。

基本的东西:

这种复杂性是根据条目大小

来衡量的

您选择单位操作(通常是影响或比较)

您计算此操作称为

的时间

使用复杂度时，通常会忽略常数项或常数因数，因此，如果操作数为3 * n ^ 3 + 12，则简化为n ^ 3并标记为O(n ^ 3)

a。)将只运行一次，没有循环，复杂性在这里微不足道O(1)
b。)在循环中调用n次:O(n)
。在这里，我们选择分析n(因为它通常是算法中的递增变量)。调用数量为n-6，因此为O(n)。

让我们在这里假设10(n)是数组的大小，而九(i)是数组的大小减去一。对于每个n值，我们必须从0到n，然后从n-1到0。n *(n-1)操作，从技术上讲:O(n * 2)，有人将其近似为O(n)。两者都称为线性时间，不同之处在于BigO不在乎的直线斜率。

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

关于algorithm - 确定大O表示法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/8331479/