需要解释一下 GRE Big-O notation 问题
Need explanation of GRE Big-O notation question
我正在为这个问题寻找解释，因为我正在学习 GRE：
对于大小为 50 的条目，算法在 10 秒内 运行。如果算法是二次方的，如果输入大小为 100，它在同一台计算机上大约花费多少秒？
我看不出时间和输入之间的关系。
正在考虑：O(n^2) -> O(50^2) =! 10 (seconds)
此外，我想研究更多关于这个主题的信息，所以如果可以的话请添加任何来源。
谢谢。
鉴于时间复杂度，您无法计算算法的准确 运行 时间（以秒为单位）。但是，它确实可以让您很好地了解测量时间的增长率。
在线性时间算法 (O(n)) 中，预计时间将作为输入的函数线性增加。例如，如果在某台机器上处理 10,000 个项目需要 1 秒，那么您应该预计 50,000 个项目需要大约 5 秒，依此类推。在二次算法 (O(n^2)) 中情况并非如此，随着输入大小的增加，"punishes" 你会更多；输入大小增加 x2 将导致 x4 处理时间，输入大小增加 x5 将导致 x25 处理时间等（就像函数 F(x)=x^2 的行为一样）。
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.
相关的 SO 问题：
关于 big-o 的好文章：https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/
注意这个术语很草率，时间复杂度没有时间的概念（是的，名字是骗人的）。
忽略小于 O(n2) 的项，因为我们在big-O框架，一个二次函数可以表示为
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, 或 t 1 = ak * t0.
两个输出之间的比率是它们输入之间的比率，k-th 幂。
对于二次函数k = 2，因此两个输出之间的比率是两个输入之间比率的平方。
如果输入加倍 (ratio = 2) 输出四倍 (ratio = 22 = 4).
如果输入三倍（比率 = 3），输出为 9 倍（比率 = 32 = 9）。
一个好的助记技巧是记住从输入比率到输出比率的函数与给定函数属于同一类。
我们给出了一个二次函数，因此输入和输出比率之间的关系是这样的：
input output
ratio ratio
1 1
2 4
3 9
4 16
5 25
... ...
问题告诉您输出加倍（从 50 到 100 个条目），因此输出必须翻两番（从 10 到 40），因为函数是 quadratic.
正如您所看到的，问题中的所有数据都被优雅地使用，没有任何硬核计算。
建议站外资源是不受欢迎的，但在这种情况下，我忍不住推荐阅读：
看看你是否能回答这些问题：
- 如果现在输入150条，需要多少时间？
90
- 如果现在输入30条，需要多少时间？
90/25 ~ 4
- 如果输入现在是 100 个条目，但程序在速度是原来两倍的计算机中是 运行，需要多少时间？
20
- 使程序 运行 至少运行 1000 秒需要多大的输入？
500
我正在为这个问题寻找解释，因为我正在学习 GRE：
对于大小为 50 的条目，算法在 10 秒内 运行。如果算法是二次方的，如果输入大小为 100，它在同一台计算机上大约花费多少秒？
我看不出时间和输入之间的关系。
正在考虑：O(n^2) -> O(50^2) =! 10 (seconds)
此外，我想研究更多关于这个主题的信息，所以如果可以的话请添加任何来源。
谢谢。
鉴于时间复杂度，您无法计算算法的准确 运行 时间（以秒为单位）。但是，它确实可以让您很好地了解测量时间的增长率。
在线性时间算法 (O(n)) 中，预计时间将作为输入的函数线性增加。例如，如果在某台机器上处理 10,000 个项目需要 1 秒，那么您应该预计 50,000 个项目需要大约 5 秒，依此类推。在二次算法 (O(n^2)) 中情况并非如此，随着输入大小的增加，"punishes" 你会更多；输入大小增加 x2 将导致 x4 处理时间，输入大小增加 x5 将导致 x25 处理时间等（就像函数 F(x)=x^2 的行为一样）。
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.
相关的 SO 问题：
关于 big-o 的好文章：https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/
注意这个术语很草率，时间复杂度没有时间的概念（是的，名字是骗人的）。
忽略小于 O(n2) 的项，因为我们在big-O框架，一个二次函数可以表示为
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, 或 t 1 = ak * t0.
两个输出之间的比率是它们输入之间的比率，k-th 幂。
对于二次函数k = 2，因此两个输出之间的比率是两个输入之间比率的平方。
如果输入加倍 (ratio = 2) 输出四倍 (ratio = 22 = 4).
如果输入三倍（比率 = 3），输出为 9 倍（比率 = 32 = 9）。
一个好的助记技巧是记住从输入比率到输出比率的函数与给定函数属于同一类。
我们给出了一个二次函数，因此输入和输出比率之间的关系是这样的：
input output
ratio ratio
1 1
2 4
3 9
4 16
5 25
... ...
问题告诉您输出加倍（从 50 到 100 个条目），因此输出必须翻两番（从 10 到 40），因为函数是 quadratic.
正如您所看到的，问题中的所有数据都被优雅地使用，没有任何硬核计算。
建议站外资源是不受欢迎的，但在这种情况下，我忍不住推荐阅读：
看看你是否能回答这些问题：
- 如果现在输入150条，需要多少时间？
90
- 如果现在输入30条，需要多少时间？
90/25 ~ 4
- 如果输入现在是 100 个条目，但程序在速度是原来两倍的计算机中是 运行，需要多少时间？
20
- 使程序 运行 至少运行 1000 秒需要多大的输入？
500