0

1) Reorder the following efficiency from smallest to largest: 2^n, n!, n^5, 10000, nlog2(n)

My Ans-> 10000 < nlog2(n) < n^5 < 2^n < n!

Correct ?

2) Efficiency of an algo. is n^3, if a step in this algo. takes 1 nanosec. (10^-9 sec.). How long does it take the algo. to process an input of size 1000?

I don't know ... Is it (1000)^3 * 10^-9 ?

4

3 回答 3

2

问题一很好。问题二，我猜你的答案就是他们要找的，但是如果 n^3 你的意思是 O(n^3)，你实际上不能回答它（除非这是使用“算法效率”我'我不熟悉）。

Big-O 复杂度给出了算法行为的渐近界。我们知道，对于“大”n，O(n^3) 大于在大小为 n 的输入上执行算法所需的时间。请注意两个警告 - “大 n”和“渐近界”。没有什么可以阻止大小为 1000 的输入所花费的时间是大小为 2000 的输入的两倍，只要存在一些 m 使得对于所有 n > m，n^3 限制运行时间。此外，没有什么可以阻止算法在每个输入上花费 1 纳秒，因为 n^3 仍然是运行时的界限——它只是非常悲观。

这就是为什么大 O 表示法在实际情况中的用途通常有限。它给出了一个公平的“最坏情况”概述，但并未涉及任何给定的使用场景。对于更实用（但经常被忽视）的复杂性类集，请在谷歌搜索“Big theta”。

于 2009-07-27T14:58:11.153 回答
1

两个答案都是正确的

于 2009-07-27T14:46:00.347 回答
1

1）是的，这是正确的。

2) 这也是正确的。维度分析：(1000^3 步) * 10^(-9) 秒/步

于 2009-07-27T14:46:19.003 回答