运行的算法时间，以秒

我明白了算法的运行时间在大O或大欧米加符号表达等等，但我仍然无法弄清楚秒（或毫秒）多久代码被执行。例如，n = 10^6，我们做O（n），那么我怎么知道需要多长时间？我也明白，在for循环中的其他语句也会对运行时间有所贡献，并且在不同的CPU上，时间可能会有所不同。但通常在编码竞赛中，我们会给出一个特定的时间，比如说2-5秒，在这里我不能确定我的算法是否足够高效或者让我的代码变慢。谢谢！运行的算法时间，以秒

来源

2015-10-19 Sreenidhi

你不知道需要多长时间。你只知道数字操作的数量级将发生。 – ergonaut

这不是O符号有多大的作用。它所指的是在添加'事物'时算法效率的缩放。

这不是绝对的时间，而是相对的。一个O（n）的100个物品只要10个物品就需要10倍。 O（N^2）意味着你会期望100倍的差异。（10^2 = 100,100^2 = 10,000）

而就是这样。这是表达效率的一种方式，而不是计算运行时间。你仍然需要知道一个“操作”花了多长时间，这取决于处理器/架构。

参见： What is a plain English explanation of "Big O" notation?

“大O符号是一个算法的复杂性的相对表示。”

来源

2015-10-19 17:03:33 Sobrique

谢谢！这有帮助！ – Sreenidhi

为O（n）是不是真的意味着测试时间。这更多是对可扩展性的测试。有些事情可能需要数万亿次操作，但它仍然是O（1），因为无论输入大小如何，它都需要1万亿次操作。

跨规模测试时间的唯一方法是实际运行它，看到的输入各种大小会发生什么。

来源

2015-10-19 17:06:01

O形符号的优点是，它是机器无关的，它实际上是知道的算法比别人的高效与否的最好指标。请注意，计算机每年都会变得更快，所以现在得到的秒数的具体速度测量值将随着时间而改变，但使用O-notation时，总是会清楚地知道，解决O（log n）中的问题比在上）。

但是，您仍然有很多工具来测量程序的（近似）速度执行时间。例如，在Linux中，您有time命令。尽管如此，结果还取决于许多其他变量（包括物理变量;例如，CPU温度可能会降低程序的性能）。这是不可能来衡量，因为环境的噪音的特定算法的确切时间度量（和它仍然是无用的，因为它总是取决于在它运行的计算机上）。

来源

2015-10-19 17:13:41

@Andrew谢谢！但是，在比赛中，我们是如何坚持时间限制的？ – Sreenidhi

@Sreenidhi我不确定它是如何在竞赛中工作的，但我猜测他们在同一台机器上和相同条件下运行每个人的算法，所以他们可能已经检查过，即使是“最差的可接受算法”在该机器的限制时间内运行。 –

运行的算法时间，以秒

回答

相关问题