确定大O符号

一尘不染

algorithm

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

确定以下各项的大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;

阅读 430

2020-07-28

共1个答案

一尘不染

大O表示算法复杂度的顺序。

基本的东西：

a。） 只会运行一次，没有循环，这里的复杂性很小O(1)

b。） 在循环中调用n次：O(n)

c。） 在这里，我们选择分析n（因为它通常是算法中的递增变量）。呼叫数量是n-6，所以是O(n)。

d。） 在这里，假设数组的大小为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)

2020-07-28