确定大O符号

Question

我可以帮助您理解/执行大O符号。我了解它的目的，但不知道如何“确定给定代码的复杂性”。 确定以下每个代码片段的大O符号

a.

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;

- user1074051

---

我不会投票关闭此问题，因为我认为即使这个问题已经被讨论过，它仍然可以被拯救成一个不错的问题。但是，您需要先发布您对这些问题的尝试。告诉我们您认为答案是什么，以及为什么您认为是那样的。 - corsiKa

当所有数据都是硬编码时，它始终是IMO O(1)。如果有一些变量，则O可能会有所不同。此外，请阅读Cormen的《算法导论》，其中的第一节是关于O、Omega和Theta符号的。 - Hauleth

我真的不知道从哪里开始，我甚至没有看到我的教授讲解这个材料，我已经读了书，但它对我来说毫无意义。我做了一些搜索，看到了这些复杂的公式，但没有看到任何类似于我教授给我的问题。 - user1074051

问题d）是两个嵌套的for循环吗？因为在C++中，如果没有{}，那么只有下一行被视为循环的一部分...这将改变答案。请重新构建您的代码以获得更好的答案 :) - mevatron

@user1074051 - 你明天考试了，但是“一点头绪都没有”？祝你好运 =) - 5StringRyan

从技术上讲，因为所有这些代码片段都指定了变量的值，它们都在常数时间内运行，因此它们都是O（1）。然而，下面的答案更符合问题的意图。 - Keith Irwin

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到0。 n * (n-1) 次操作，技术上是: O(n * 2) ，有些人近似为O(n)。两者都被称为线性时间，不同的是BigO所关心的线的斜率。

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

- AsTeR

---

常数，正如你所说的微不足道，被表示为O(1)。 - Roman Byshko

e) 应该是 O(2^n)。pow 是 (底数，指数)。 - mevatron

并且d）应该是O（n），因为它不是嵌套循环。它只是两个循环，分别对数组进行一次遍历。 - Gisli

谢谢mevatron。Gisli我考虑了d，n是10，9是n-1，如提到的那样。 - AsTeR

Answer 2

假设您不将cout视为Big-O测量的一部分。 a) O(1) 您可以在恒定时间内执行整数赋值。
b) O(n) 因为循环需要n次操作。
c) O(n - c) = O(n) 常数在Big-O中消失。
d.1) O(2*n) = O(n) 两个线性时间算法最终都是线性时间。
d.2) 如果n随着pow(2, n) = 2^n增长，则操作数为O(2^n)；但是如果n是常量，则会以O(k)增长，其中k = 2^6 = 64，这将是线性的。

- mevatron

Answer 3

这些示例相当简单。首先，您需要确定代码中的主要（简单）操作，并尝试将该操作的调用次数表达为输入的函数。

为了更具体：

a.)

这段代码始终在固定时间内运行。这个时间取决于计算机、I/O延迟等因素，但它几乎不取决于n的值。

b.)

这次循环中的一段代码将被执行多次。如果n增加了两倍，你能说出迭代次数会发生什么变化吗？

c.)

再次在循环内部编写一些代码。但是这次迭代的次数小于n。但是如果n足够大，您是否与b.)相似？

d.)

这段代码很有趣。第一个循环内的操作更加复杂，但是它仍然需要大致恒定的时间。那么它相对于 n 执行了多少次？再次与 b.) 进行比较。

第二个循环只是为了欺骗你。对于小的 n 值，它实际上可能需要比第一个循环更长的时间。然而 O(n) 表示法总是考虑高 n 值。

5.)

最后一段代码实际上非常简单。循环内的简单操作次数等于n^2。将n加1，你将得到两倍的操作。

- Tomasz Nurkiewicz

Answer 4

为了理解完整的数学定义，我建议您查阅维基百科。对于简单的目的，大O表示算法的上限，在给定长度n的情况下，一个例程在完成之前迭代多少次。我们将这个上限称为O(n)或n的大O。

在C++中，访问简单数组的成员是O(1)。无论数组大小如何，它都只需要一次操作。

通过for循环对数组进行线性迭代是O(n)。

嵌套的for循环是O(n^2)或O(n^k)，如果有多个嵌套的for循环。

使用分治递归（堆、二叉树等）的时间复杂度是O(lg n)或O(n lg n)，具体取决于操作。

- lukecampbell

Answer 5

a

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

常数时间，O(1)。这意味着随着n从1增加到无穷大，执行此语句所需的时间不会增加。每次增加n时，所需的时间不会增加。

b

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

线性时间，O(n)。这意味着随着n从1增加到无穷大，执行此语句所需的时间量会线性增加。每次增加n时，所需的额外时间量与前一次保持恒定。

c

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

线性时间，O(n)，与上面的示例2相同。

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;

线性时间，O(n)。随着n从1到无穷大的增加，执行这些语句所需的时间量呈线性增长。线性线比示例3陡峭两倍，但是大O符号不关心线有多陡峭，它只关心时间要求如何增长。两个循环需要随着n的增加而线性增长的时间量。

e

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

创建一个图表，显示在给定值n的情况下sum=sum+k被执行的次数：

n     number_of_times_in_loop
1     2^1 = 2
2     2^2 = 4
3     2^3 = 8
4     2^4 = 16
5     2^5 = 32
6     2^6 = 64

当n从1到无穷大时，请注意我们在循环中的次数呈指数级增长。2->4->8->16->32->64。如果我插入150的n会发生什么？我们在循环中的次数变得极其庞大。

这是指数时间：O(2^n)（请看这里）表示算法的增长将随着输入数据集中每个附加元素而翻倍。插入一个大型的n，你将等待几小时或几年才能完成计算，只为了处理少量的输入项。

我们为什么要关心？

作为计算机科学家，我们有兴趣正确理解BigO符号，因为我们希望能够以权威和信心说出这样的话：

“Jim用于计算行星之间距离的算法需要指数时间。如果我们想要处理20个对象，它需要太多时间，他的代码很糟糕，因为我可以用线性时间制作一个。”

更好的是，如果他们不喜欢听到的内容，你可以用数学证明它。

- Eric Leschinski