算法效率

Question

7

这是我作业中的一个问题...

假设算法的效率为n³，如果算法中的一步需要1纳秒(10^-9秒)，那么处理1,000个输入所需时间是多少？

下面是我的问题：我该如何计算这个问题？请不要给出答案，帮助我学会自己解决。

- HashHazard

7

好的，我会尽力进行翻译，确保内容准确无误并易于理解。以下是需要翻译的内容：+1 Props for asking specifically NOT for the answer - Ethan

3

不使用已弃用的“homework”标签，点赞（+1）。 - BlackVegetable

谢谢大家的帮助。有人可以确认答案是1秒吗？ - HashHazard

我真的很难过，1 attosecond 的答案被删除了 :( - im so confused

1

@AK4749 确实:/ 在编辑之前，它实际上是1zeptosecond。 - mmgp

2个回答

2

n^3中的n指的是数据大小。如果输入大小为1，请将其插入到n^3中（然后乘以时间）。如果输入大小为1,000...你应该怎么做？

编辑：最初我以大O符号（例如O(n^3)）发布了这个问题，但这是有缺陷的，因为它忽略了可能使问题无法回答的固定成本。我认为我应该保留这个答案，或许主要是提醒其他人不要犯和我一样的错误。感谢您的评论。

- BlackVegetable

3

该问题显然没有使用大O符号，否则就无法按照所述方式回答。如果它是O(n^3)，那么输入大小为1的重要部分成本可能是较低阶变量成本项的固定成本，对于更大的输入大小来说就不那么重要了。 - A. Webb

没错。我会编辑我的回复，以纳入您的评论。 - BlackVegetable

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mihai Maruseac · Accepted Answer

你将n定义为1000。因此，你需要n的立方步骤，每个步骤需要1 ns。将两个数字相乘即可得出答案。

总体思路：如果一个算法需要f(n)步骤，每一步需要t时间，则该算法需要t * f(n)的时间。