java - 实际计算算法的时间复杂度

Question

我只在理论上读过时间复杂度。有什么方法可以在程序中计算它们吗？不是通过“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() 不够精确还是我应该使用较慢的系统？或者还有其他办法吗？

Answer 1

Is there any way to calculate them in a program? Not by assumptions like 'n' or anything but by actual values.

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

---

将这个问题放在一边，理论上可以自动对复杂性进行严格的分析。然而，这是一个难题:自动定理证明是困难的......特别是如果循环中没有人来“指导”这个过程。停机定理暗示不存在可以证明任意程序复杂性的自动定理证明器。 (当然，不可能有一个复杂性证明器适用于所有可能会或可能不会终止的程序......)

---

但是有一种方法可以计算具有给定输入集的程序的性能指标。你只要运行它!实际上，您进行了一系列运行，根据一些问题大小度量(即 N)绘制性能图......并对与性能和 N 相关的公式进行有根据的猜测 测量。或者您可以尝试将测量结果与公式相匹配。

然而……

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

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

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