我有一个下面编写的函数。此功能本质上是合并排序。
public static long nlgn(double[] nums) {
if(nums.length > 1) {
int elementsInA1 = nums.length/2;
int elementsInA2 = nums.length - elementsInA1;
double[] arr1 = new double[elementsInA1];
double[] arr2 = new double[elementsInA2];
for(int i = 0; i < elementsInA1; i++)
arr1[i] = nums[i];
for(int i = elementsInA1; i < elementsInA1 + elementsInA2; i++)
arr2[i - elementsInA1] = nums[i];
nlgn(arr1);
nlgn(arr2);
int i = 0, j = 0, k = 0;
while(arr1.length != j && arr2.length != k) {
if(arr1[j] <= arr2[k]) {
nums[i] = arr1[j];
i++;
j++;
} else {
nums[i] = arr2[k];
i++;
k++;
}
}
while(arr1.length != j) {
nums[i] = arr1[j];
i++;
j++;
}
while(arr2.length != k) {
nums[i] = arr2[k];
i++;
k++;
}
}
return nuts;
}
由于这是一种合并排序，因此从我的研究中我知道该算法的big-O复杂度为O(n lgn)。但是，当我运行计时测试时，得到的结果并不表明它正在O(n lgn)时间内运行。看起来好像是O(n lgn)时间，因为直到我们在开始时到达两个for循环的结尾为止。它运行时间为O(n)。一旦超过该时间，它就应该在O(lgn)时间内运行，因为它会对每个元素进行排序。
我的问题是，有人可以确认这段代码在O(n lgn)时间内运行吗？如果没有，我想知道我的理解哪里出了问题。
最佳答案
由于这是一种合并排序，因此从我的研究中我知道该算法的big-O复杂度是O(n lgn)。 [...]我的问题是，有人可以确认这段代码是否在O(n lgn)时间内运行？
无需显示它，因为已经证明合并排序可以在O(n lg(n))时间内运行。但是，如果您想观察它，则需要对输入值进行越来越大的试验。您可能需要使用输入值和计时结果更新帖子。
但是，当我运行计时测试时，得到的结果并不表明这是在O(n lgn)时间内运行的。 [...]如果不是，我想知道我的理解哪里出了问题。
我认为您可能会误解Big-Oh符号实际上试图告诉您的内容。当输入变得足够大时，Big-O为您提供算法的渐近上限的近似值。 (“大”如何“足够大”将因算法而异，需要通过实验找到。关键是该值确实存在，并且我们可以更抽象地表示它。)
换句话说，Big-O会告诉您，随着N变得非常大，该算法的最坏情况可能是什么。由于这是最坏的情况，因此这也意味着它在某些情况下可能会表现更好，但我们通常并不关心这些情况。 (如果您感兴趣，请查看Big-Omega和Big-Theta。)例如，如果您有一个“足够小”的列表，则merge-sort的运行速度比quick-sort快，并且通常被用作优化。
这也是一个近似值，因为常量和其他多项式项未作为符号的一部分显示。例如，一些具有500x^2 + 15x + 9000时间复杂度的假设算法将被编写为O(n^2)。
放弃较低条款的一些原因包括:
n趋于正无穷大时，较大的n^2术语占主导；与最大/主要期限相比，较低的期限对总体成本的贡献越来越小-例如向湖中添加几滴或一桶水； O(n^2)比冗长而复杂的多项式更容易，而且没有真正的好处