1

我只在理论上读过时间复杂性。有没有办法在程序中计算它们？不是通过“n”之类的假设或其他任何东西，而是通过实际值..

例如..计算合并排序和快速排序的时间复杂度..

Merge Sort= O(nlogn);// any case

Quick Sort= O(n^2);// worst case(when pivot is largest or smallest value)

nlogn 和 n^2 在数学上存在巨大差异..

所以我在我的程序中尝试了这个..

main()
    {
       long t1=System.nanoTime();
       // code of program..
       long t2=System.nanoTime();
       time taken=t2-t1;
    }

我对这两种算法都得到了答案，实际上我尝试过的任何算法大多是 20。

不够System.nanoTime()精确还是我应该使用较慢的系统？或者还有其他方法吗？

4

7 回答 7

4

有没有办法在程序中计算它们？不是通过诸如“n”之类的假设，而是通过实际值。

我认为您误解了复杂性是什么。它不是一个值。它甚至不是一系列值。它是一个公式。如果你摆脱N它作为复杂性度量是没有意义的（除了O(1)......显然）。

把这个问题放在一边，理论上可以自动化对复杂性的严格分析。然而，这是一个难题：自动定理证明很困难……尤其是如果循环中没有人来“指导”该过程。停止定理意味着不可能有一个自动定理证明器可以证明任意程序的复杂性。（当然，不可能有一个复杂性证明器适用于所有可能会或可能不会终止的程序......）

但是有一种方法可以计算具有给定输入集的程序的性能度量。你只需运行它！实际上，您进行了一系列运行，将性能与一些问题大小度量（即一个）绘制成图表......并对一个将性能和度量N相关的公式进行有根据的猜测。N或者您可以尝试将测量结果拟合到公式中。

然而 ...

  • 这只是一个猜测，并且
  • 这种方法并不总是奏效。

例如，如果您在经典的快速排序上尝试过此操作，您很可能会得出结论，即复杂性是O(NlogN)，而忽略了重要的警告，即它存在“最坏情况” O(N^2)。另一个例子是随着问题规模变大，可观察到的性能特征发生变化。

简而言之，这种方法很容易给你不可靠的答案。

于 2013-06-03T09:52:37.987 回答
2

好吧，在对程序进行一些假设的实践中，您可能能够在大量测试用例上运行您的程序（并测量它所花费的时间）并使用插值来估计程序的增长率和复杂性，并使用统计假设检验以显示您正确的概率。

但是，这件事不能在所有情况下都完成。事实上，你甚至不能有一个算法来告诉每个程序它是否会停止（运行一个无限循环）。这被称为停机问题，被证明是无法解决的。

于 2013-06-03T09:33:52.433 回答
1

像这样的微型基准本身就存在缺陷，使用它们您永远不会获得非常准确的读数——尤其是在纳秒范围内。JIT 需要时间来“热身”您的代码，在此期间它将围绕正在调用的代码进行自我优化。

如果你必须走这条路，那么你需要一个大的算法测试集，它需要几秒钟而不是几纳秒的时间来运行，最好还有一个“热身”期——那么你可能会看到一些差异接近你期待什么。但是，您永远无法仅获取这些时间并直接从中计算时间复杂度-您需要运行许多不同大小的案例，然后绘制每个输入大小所用时间的图表。即使这种方法也不会为您提供非常准确的结果，但足以给出一个想法。

于 2013-06-03T09:34:07.443 回答
1

您的问题可能与程序可以计算算法的复杂性有关吗？和程序/算法来查找任何给定程序的时间复杂度，我认为你做了一个程序，你计算 while 或 for 循环，看看它是否嵌套，但我不知道如何计算一些递归函数的复杂度.

于 2013-06-03T09:35:58.647 回答
1

你写的微基准测试不正确。当您想要收集代码的一些时间指标以进行进一步优化时，JFF 等使用JMH。这会对你有很大帮助。

于 2013-06-03T09:38:52.747 回答
1

当我们说一个算法表现出O(nlogn)复杂性时，我们是说该算法的渐近上限是O(nlogn)。也就是说，对于足够大的 值n，算法的行为类似于函数n log n。我们并不是说对于n输入，肯定会有n log n处决。简单地说，这是您的算法所属的定义集。

通过在系统上设置时间间隔，您实际上是在将自己暴露在计算机系统中涉及的各种变量中。也就是说，您正在处理系统延迟、线路电阻、CPU 速度、RAM 使用率……等等。所有这些都会对您的结果产生可衡量的影响。这就是我们asymptotics用来计算算法时间复杂度的原因。

于 2013-06-03T09:45:36.117 回答
1

检查时间复杂度的一种方法是在不同的大小上运行这两种算法n并检查每次运行之间的比率。从这个比率你可以得到时间复杂度

例如，
如果时间复杂度是，O(n)那么比率将是线性的

如果时间复杂度是O(n^2)这个比率，(n1/n2)^2
那么如果时间复杂度是O(log(n))这个比率，那么这个比率 就是log(n1)/log(n2)

于 2013-06-03T10:38:42.370 回答