我正在学习关于时间复杂度的 Coursera 课程。 我在视频中遇到了这个，我认为出了什么问题。 “因此，假设我们有一个算法，其运行时间大致与 n 成正比，并且我们希望它在运行速度约为千兆赫的机器上运行。我们可以处理多大的输入，以便在一秒钟内完成计算？”（1GHZ CPU（每秒 10^9 个周期））
“如果它以大约 n 的大小运行，那么您可以处理大约十亿大小的输入，然后需要超过一秒的时间”（10^9 / 10^9）
“如果它像 n 平方一样运行，情况会更糟。你只能处理大约 30,000 个大小的输入，然后就会开始花费超过一秒的时间。” n = 30000, (30000)^2/10^9 = 0.9 秒 ~ 1 秒
“如果输入的大小为 2 到 n，则非常糟糕，您只能在一秒钟内处理大小约为 30 的输入” 2^30/10^9 ~ 1.07 秒
对于 n log(n) 复杂度，如果输入大小 n 是 10^9，那么应该需要 10^9 * log(10^9) / 10^9 = 9 秒，对吧？ 不知何故，视频中显示了 30 秒。 它还说如果n = 10^7.5那么运行时间是1秒，这也是我的计算错误的。
我用 n, n^2, 2^n 复杂度计算了每个案例，一切都是正确的，只有 nlog(n) 案例搞砸了
这是更多详细信息的照片： https://i.upanh.org/2022/04/11/nlogn.jpg[^]
链接课程视频（3:40到5:00是部分）： https://www.coursera.org/lecture/algorithmic-toolbox/asymptotic-notation-zI8dH[^]
我编辑了问题，使其就像我观看的课程视频中一样
我尝试过的：
I calculated every case with the n, n^2, 2^n complexity and everything was right, only nlog(n) case messed up
解决方案1
引用：如果输入大小 n 是 10^9，那么应该需要 10^9 * log(10^9) / 10^9 = 9 秒，对吧？
不 ！ 您不会根据 Big O 表示法计算运行时间，至少不会单独计算运行时间。
Big O 表示法告诉您算法的类别复杂性，而不是运行时间，也不是直接告诉您。
当您拥有给定数据大小的运行时时，Big O 复杂度允许您评估另一个数据大小的运行时。
对于从 20 到 10^6 的数据，您的 1 秒计时意味着您需要切换到毫秒计时才能获得有意义的计时。
解决方案2
大 O 没有给出具体的执行时间。 参见，例如 大 O 表示法 – 维基百科[^] （特性 部分， 乘以一个常数）。
解决方案3
补充一下其他人所说的，无论如何，你不能直接将时钟周期与执行时间等同起来 – 有些机器操作需要 n 个周期来执行，其他的可能是 n * 2。除此之外，现代处理器是流水线的 – 所以有些指令可能会在其他指令正在执行、缓存时启动 – 因此执行时间可能取决于上次执行指令的时间，以及其数据是否在 L1、L2 或 L3 缓存中可用、可用于执行的空闲核心的可用性，以及许多其他指令细节。
你不能只是说“我的时钟速度是 X，所以我的执行时间是 X * Y”——还有太多其他因素会影响它。
解决方案5
如果是日志的话 30 秒左右就可以了2（n）。 日志2(1000) ~= 10。
编辑：O(n log(n)) 算法通常递归地将问题一分为二，分别求解每个部分，然后组合解决方案。 这就是为什么要记录2 通常是暗示的。 归并排序就是一个很好的例子。
解决方案6
大 O 符号仅告诉您执行时间如何 改变 当问题的“大小”发生变化时，它并不能提供针对特定情况的实际估计。
换句话说，存在一个未知因素，例如 O(n2) 可能意味着
time_needed = constant * n * n
没有人告诉常量的值是什么，因此 time_needed 没有具体值。
这个例子只是告诉你，两倍大的问题需要四倍的时间才能解决。
コメント