可以在 1 秒内解决的输入的最大尺寸 m 是多少？
What is the largest size m on input that can be solved in 1s?
某算法A的计算复杂度为O(n*sqrt(n))。执行一个基本操作所需的时间是 1 毫秒。在 1s 内可以解决的最大输入尺寸 s 是多少。如果我们使用快 1000 倍的计算机，最大输入大小是多少倍？解释你的答案。
我运行在一本算法书上查了这个问题，应该是理论问题，但是我在书上找不到资料来帮助解决这个问题。任何人都可以提供解释或提示。
我不想编辑原始问题，但是使用 Big-Theta Ө(n*sqrt(n)) 而不是 Big-O 更有意义吗？
Big-Oh 符号在这里使用是错误的。您不知道每个 n 有多少基本运算，因为 Big-Oh 删除了所有常数因子和所有 lower-order 项。这些功能都在O(n*sqrt(n)):
f(n) = n * sqrt(n)
g(n) = 4711 * n * sqrt(n)
h(n) = n * sqrt(n) + 18 650 000 000
如果我们假设他们指的是第一个函数（一个错误的假设），那么你的第一个问题只不过是解决n的简单代数表达式：
1000 = f(n) = n * sqrt(n)
但这个问题可能是一个技巧问题，所以做出这个假设是错误的。尝试使用 g(n) 和 h(n) 求解 n，您会得到截然不同的答案。
这个问题在两个方面是假的：
渐近复杂度有一个未知的隐式乘法常数。说 "time is O(N) -> N operations are performed";
O(N) 只是一个上限，保证时间不会超过 C.N 对于某些 C。但实际上它没有告诉你实际的 运行 时间 !
现在为了让问题更容易解决，我们假设
运行时间正好是C.N√N,
即 C=1 毫秒
那么当N=100时N√N=1000，当N=10000时N√N=1000000。
如果一个算法有
O(n*sqrt(n))
时间复杂度实际上意味着执行时间是
T(n) = C*n*sqrt(n) + o(n*sqrt(n))
其中 C 是某个常数。例如，T(n) 可以是
T(n) = 1000 * n * sqrt(n) + 1e10 * n + 200 * sqrt(n) + 15 * log(n) + 1e20
当然，上面的公式有点夸张，但是，你看
问题：O(f(n)) 不是 执行时间本身 ，而只是它的 渐近 。要估计执行时间，您必须进行实验，例如如果我们有
n | T(n), ms
--------------
1 | 12
3 | 20
10 | 73
30 | 339
100 | 2010
我们可以借助最小二乘算法将 T(n) 近似为
T(n) = 2 * n * sqrt(n) + 10
有了公式就可以求解 n。在上面的例子中
2 * n * sqrt(n) + 10 = 1000
我们可以找出来
n = 495**(2/3) = 63
作为可以在 1000 毫秒内解决的问题的最大大小。
当只有 O(f(n)) 时，你不能（在 一般情况下 ）说如果你有一台更快的计算机，执行时间会发生什么，但很明显"it won't be worse"。让我们 return 到我们夸张的公式：
T(n) = 1000 * n * sqrt(n) + 1e10 * n + 200 * sqrt(n) + 15 * log(n) + 1e20
如您所见，在现实世界中，它是最后一项 - 1e20 主导所有合理的输入，这就是为什么答案将是“工作站将改变 1000 倍的速度” 无”。反之：
T(n) = 1e-1000 * n * sqrt(n) + log(n)
具有 O(n*sqrt(n)) 的复杂性，其中 log(n) 项目占主导地位 合理（即 足够小）ns; 1000 倍 CPU 性能提升将导致算法性能提升 2**1000 == 1e300。
某算法A的计算复杂度为O(n*sqrt(n))。执行一个基本操作所需的时间是 1 毫秒。在 1s 内可以解决的最大输入尺寸 s 是多少。如果我们使用快 1000 倍的计算机，最大输入大小是多少倍？解释你的答案。
我运行在一本算法书上查了这个问题，应该是理论问题，但是我在书上找不到资料来帮助解决这个问题。任何人都可以提供解释或提示。
我不想编辑原始问题，但是使用 Big-Theta Ө(n*sqrt(n)) 而不是 Big-O 更有意义吗？
Big-Oh 符号在这里使用是错误的。您不知道每个 n 有多少基本运算，因为 Big-Oh 删除了所有常数因子和所有 lower-order 项。这些功能都在O(n*sqrt(n)):
f(n) = n * sqrt(n)
g(n) = 4711 * n * sqrt(n)
h(n) = n * sqrt(n) + 18 650 000 000
如果我们假设他们指的是第一个函数（一个错误的假设），那么你的第一个问题只不过是解决n的简单代数表达式：
1000 = f(n) = n * sqrt(n)
但这个问题可能是一个技巧问题，所以做出这个假设是错误的。尝试使用 g(n) 和 h(n) 求解 n，您会得到截然不同的答案。
这个问题在两个方面是假的：
渐近复杂度有一个未知的隐式乘法常数。说 "time is O(N) -> N operations are performed";
是错误的
O(N) 只是一个上限，保证时间不会超过 C.N 对于某些 C。但实际上它没有告诉你实际的 运行 时间 !
现在为了让问题更容易解决，我们假设
运行时间正好是C.N√N,
即 C=1 毫秒
那么当N=100时N√N=1000，当N=10000时N√N=1000000。
如果一个算法有
O(n*sqrt(n))
时间复杂度实际上意味着执行时间是
T(n) = C*n*sqrt(n) + o(n*sqrt(n))
其中 C 是某个常数。例如，T(n) 可以是
T(n) = 1000 * n * sqrt(n) + 1e10 * n + 200 * sqrt(n) + 15 * log(n) + 1e20
当然，上面的公式有点夸张，但是，你看
问题：O(f(n)) 不是 执行时间本身 ，而只是它的 渐近 。要估计执行时间，您必须进行实验，例如如果我们有
n | T(n), ms
--------------
1 | 12
3 | 20
10 | 73
30 | 339
100 | 2010
我们可以借助最小二乘算法将 T(n) 近似为
T(n) = 2 * n * sqrt(n) + 10
有了公式就可以求解 n。在上面的例子中
2 * n * sqrt(n) + 10 = 1000
我们可以找出来
n = 495**(2/3) = 63
作为可以在 1000 毫秒内解决的问题的最大大小。
当只有 O(f(n)) 时，你不能（在 一般情况下 ）说如果你有一台更快的计算机，执行时间会发生什么，但很明显"it won't be worse"。让我们 return 到我们夸张的公式：
T(n) = 1000 * n * sqrt(n) + 1e10 * n + 200 * sqrt(n) + 15 * log(n) + 1e20
如您所见，在现实世界中，它是最后一项 - 1e20 主导所有合理的输入，这就是为什么答案将是“工作站将改变 1000 倍的速度” 无”。反之：
T(n) = 1e-1000 * n * sqrt(n) + log(n)
具有 O(n*sqrt(n)) 的复杂性，其中 log(n) 项目占主导地位 合理（即 足够小）ns; 1000 倍 CPU 性能提升将导致算法性能提升 2**1000 == 1e300。