需要解释GRE Big-O符号问题

Question

因为我正在攻读GRE，所以我正在寻找这个问题的解释：

对于50号条目，算法在10秒内运行。如果算法是二次方的，如果输入的大小为100，它会在几秒钟内花费多少时间在同一台计算机上？

我看不出时间和输入之间的关系。

考虑：O(n^2) -> O(50^2) =! 10 (seconds)

此外，我想更多地了解这个主题，所以如果可以，请添加任何来源。

谢谢。

Answer 1

请注意，术语很草率，时间复杂度没有时间概念（是的，名称是欺骗）。

---

由于我们在big-O框架下工作，忽略小于O（n2）的项，二次函数可表示为

t = c * n2

给定（t，n）对具有值（10,50），我们有

10 = c * 2500 c = 1/250 = 4/1000

求得（t，100）得到

t = 4/1000 * 10000 = 40

---

有一种更快，更有洞察力的方法来解决这个问题。 受过训练的眼睛可以立即将答案发现为40。

考虑这个功能电源功能：

t = c * nk

现在让我们考虑输入m0和m1，其中m1 = a * m0是m0的（整数）倍数。 让我们比较各自的t0，t1：

t0 = c *（m0）k t1 = c *（m1）k = c * ak *（m0）k

因此，我们看到对于多项式时间函数t1 / t0 = ak，或t1 = ak * t0。

两个输出之间的比率是它们的输入与第k个功率之间的比率。

对于二次函数k = 2，因此两个输出之间的比率是两个输入之间的比率的平方。 如果输入加倍（比率= 2），则输出翻两番（比率= 22 = 4）。 如果输入三倍（比率= 3），则输出为九倍（比率= 32 = 9）。

一个好的助记符技巧是要记住输入比率与输出比率的函数与给定函数的类型相同。 我们给出了二次函数，这是输入和输出比率之间的关系：

input   output
ratio   ratio
 1       1
 2       4
 3       9
 4       16
 5       25
...      ...

问题告诉您输出加倍（从50到100个条目），因此输出必须翻两番（从10到40），因为函数是二次的。 正如您所看到的，问题的所有数据都是优雅地使用，没有任何核心计算。

---

建议外部消息来源不赞成，但在这种情况下，我不得不推荐阅读：

• Introduction to the Theory Computation - Michael Sipser

---

看看你是否可以回答这些问题：

• 如果输入现在是150个条目，需要多长时间？ 90
• 如果输入现在是30个条目，需要多长时间？ 90 / 25~4
• 如果输入现在是100个条目，但程序是在计算机上运行的速度的两倍，那么需要多长时间？ 20
• 要使程序运行至少1000秒，需要多大的输入？ 500

Answer 2

鉴于时间复杂度，您无法计算算法的确切运行时间（以秒为单位）。但是，它确实可以让您对测量时间的增长率有所了解。

在线性时间算法（O（n））中，期望时间作为输入的函数线性增加。例如，如果10,000个项目需要一秒钟来处理某个机器，那么您应该预计50,000个项目需要大约5秒钟，依此类推。在二次算法（O（n ^ 2））中不是这种情况，当输入大小较大时，它会“惩罚”你更多;输入大小增加x2将导致x4处理时间，输入大小增加x5将导致x25处理时间等（就像函数F（x）= x ^ 2表现的那样）。

您可以使用this post作为介绍，并使用this one作为更正式的解释。

Answer 3

Big-O不会告诉您条目大小和执行时间之间的确切相关性，而是告诉您条目大小增长与执行时间增长之间的近似相关性。所以：O(n)复杂性意味着条目大小和执行时间成正比（如果输入是3倍大，那么执行时间也将是3倍），O(n^2)意味着如果条目大小是3倍大，然后执行时间将延长9倍等。

在您的情况下，50号条目的初始执行时间是10秒。如果输入变为100大小的条目，那么通过简单划分，我们可以判断它的100 / 50 = 2倍大。知道算法的Big-O是O(n^2)，我们可以告诉执行时间将是2^2 = 4倍。因此，如果初始执行时间是10秒，那么较大输入的执行时间将近似为10 seconds * 4 = 40 seconds。

相关的问题：Rough estimate of running time from Big O

关于big-o的好文章：https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/