确定大O符号

  • Z时代
  • 2024-01-10
  • 分类：问答

我需要帮助来理解/做大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表示算法复杂度的顺序。

基本的东西：

  • 这种复杂性是根据条目大小来衡量的

  • 您选择单位操作（通常是效果或比较）

  • 您数一下此操作被调用的时间

  • 使用复杂度时，通常会忽略常数项或常数因数，因此，如果运算数为3 * n ^ 3 + 12，则会简化为n ^ 3，并标记为O（n ^ 3）

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

在循环中调用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不在乎的是线的斜率。

循环从0到pow（2，n），从1到2 ^ n，总结为O(2^n)

以上是 确定大O符号 的全部内容， 来源链接： utcz.com/qa/409464.html

回到顶部