大 O 和 运行 时间？
Big O and Running Time?
假设我们有两种算法可以解决同一个问题。
算法A具有O(n)运行-时间复杂度，而算法B 具有 O(n3) 运行-时间复杂度。
对于大小为1000的输入，A需要1秒，B需要3秒。
话虽如此，算法 A 和 B 需要多长时间才能输入大小为 3000 的数据？
我的猜测是：
- A 将花费 3 秒，因为它是线性的（1000 尺寸需要 1 秒）。
- B 将花费 81 秒，因为它是原始输入大小的 3 倍，需要 3 秒（因此，3*33)
第二个问题：如果我有一个 运行 时间复杂度 O(n) 的算法，并且我要提高处理器速度和内存大小为原来的两倍，算法的 运行 时间复杂度在 Big O 中是否仍然相同，即 O(n)?
请给出解释。
评论有点长
Big-oh 表示法是关于数据趋于无穷大时发生的情况。如果你有一个数据点：
n=1000, time=1 sec
您没有足够的信息来概括。这可能是：
per n, 1/1000 seconds, no overhead
per n, 1/1000000 seconds, 0.999 overhead
您也可以在实际 运行 时间中有小因素 -- 例如 sqrt(n) 或 log(n)。
而对于第二种算法，情况更加复杂。
要记住的重要一点是 big-O 是算法复杂性的 理论 度量。它不能替代在特定机器上实际分析特定算法
编辑：
从技术上讲，当此限制限制为非 NULL 值时，两个函数具有相同的“big-Oh”：
f1(n)
----- as n --> infinity
f2(n)
为方便起见，我们使用简单函数指定 big-Oh，例如 n^2、log(n)、e^n 等。
这只是关于当大小变为无穷大时会发生什么的陈述。时期。有许多复杂度低但在 real-world 问题中运行良好的算法示例。例如，快速排序的 worst-case 复杂度（因此称为“复杂度”）为 O(n^2)，但在一般情况下效果非常好，因此它通常是首选的排序算法。
所有这些复杂性声明都以您在计算中忘记的一句话开头：
There is a n0 so that for all n greater than n0 ...
由于您没有关于此 n0 值的信息，因此您无法就这两种算法的计时行为得出任何结论。
为了举例说明，请考虑输入数据集是否适合 CPU 缓存的可能性。一旦它对于缓存来说太大了，运行时间通常会大幅增加。
how long will Algorithms A and B take for input of size 3000?
如果 n==0 的 运行 时间为 0 秒，则 2 次猜测是合理的预测。
I were to ram ramp up the processor speed ... to twice of the original,
运行 次预计是一半，假设限制因素是处理器速度而不是 I/O 吞吐量等，但它不会改变 big(O)
... to memory size to twice of the original ...
还是那句话，没变大(O)。我不希望 run-time 减少，除非进程受内存限制。
假设我们有两种算法可以解决同一个问题。
算法A具有O(n)运行-时间复杂度，而算法B 具有 O(n3) 运行-时间复杂度。
对于大小为1000的输入，A需要1秒，B需要3秒。
话虽如此，算法 A 和 B 需要多长时间才能输入大小为 3000 的数据？
我的猜测是：
- A 将花费 3 秒，因为它是线性的（1000 尺寸需要 1 秒）。
- B 将花费 81 秒，因为它是原始输入大小的 3 倍，需要 3 秒（因此，3*33)
第二个问题：如果我有一个 运行 时间复杂度 O(n) 的算法，并且我要提高处理器速度和内存大小为原来的两倍，算法的 运行 时间复杂度在 Big O 中是否仍然相同，即 O(n)?
请给出解释。
评论有点长
Big-oh 表示法是关于数据趋于无穷大时发生的情况。如果你有一个数据点：
n=1000, time=1 sec
您没有足够的信息来概括。这可能是：
per n, 1/1000 seconds, no overhead
per n, 1/1000000 seconds, 0.999 overhead
您也可以在实际 运行 时间中有小因素 -- 例如 sqrt(n) 或 log(n)。
而对于第二种算法，情况更加复杂。
要记住的重要一点是 big-O 是算法复杂性的 理论 度量。它不能替代在特定机器上实际分析特定算法
编辑：
从技术上讲，当此限制限制为非 NULL 值时，两个函数具有相同的“big-Oh”：
f1(n)
----- as n --> infinity
f2(n)
为方便起见，我们使用简单函数指定 big-Oh，例如 n^2、log(n)、e^n 等。
这只是关于当大小变为无穷大时会发生什么的陈述。时期。有许多复杂度低但在 real-world 问题中运行良好的算法示例。例如，快速排序的 worst-case 复杂度（因此称为“复杂度”）为 O(n^2)，但在一般情况下效果非常好，因此它通常是首选的排序算法。
所有这些复杂性声明都以您在计算中忘记的一句话开头：
There is a
n0so that for allngreater thann0...
由于您没有关于此 n0 值的信息，因此您无法就这两种算法的计时行为得出任何结论。
为了举例说明，请考虑输入数据集是否适合 CPU 缓存的可能性。一旦它对于缓存来说太大了，运行时间通常会大幅增加。
how long will Algorithms A and B take for input of size 3000?
如果 n==0 的 运行 时间为 0 秒，则 2 次猜测是合理的预测。
I were to
ramramp up the processor speed ... to twice of the original,
运行 次预计是一半，假设限制因素是处理器速度而不是 I/O 吞吐量等，但它不会改变 big(O)
... to memory size to twice of the original ...
还是那句话，没变大(O)。我不希望 run-time 减少，除非进程受内存限制。