这些结果如何证明我的方法在 O(n lgn) 时间内是 运行?
How do these results prove my method is running in O(n lgn) time?
我有一个我写在下面的方法。
public static long nlgn(double[] nums) {
long start = System.nanoTime();
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++;
}
}
double max = nums[nums.length - 1];
double min = nums[0];
double[] farthestPair = {max, min};
long end = System.nanoTime();
return (end - start);
}
这基本上是一个合并排序操作,一旦排序,就会找到最小和最大的数字。我相信这种方法可以在 O(n lgn) 时间内运行。但是,当我 运行 函数的输入大小在每个 运行(1000、2000、4000 等)时加倍,当我以纳秒为单位计时时,我得到以下结果。
First pass: (0.12) seconds
Second pass: (0.98) seconds
Third pass: (0.91) seconds
Fourth pass: (0.90) seconds
Fifth pass: (1.33) seconds
我的问题是,鉴于这些结果,这些结果是否表明此方法在 O(n lgn) 时间内 运行 有效?
如果你有算法的源代码,你应该分析它而不是做运行时基准测试。
如果是递归函数,请查看 master theorem.
在你的函数中你做了 2 次大小为 n / 2
的递归调用,所以 a = 2, b = 2
和 f(n) = 2n
,因为在你的前两个 for 循环中你遍历了所有数组 (n)并使用最后三个 while 循环再次迭代所有数组大小 (n),因此 2n
.
如果你应用主定理,它会给出结果 Θ(n ln(n))
,所以 O(n ln(n))
也是正确的。
我有一个我写在下面的方法。
public static long nlgn(double[] nums) {
long start = System.nanoTime();
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++;
}
}
double max = nums[nums.length - 1];
double min = nums[0];
double[] farthestPair = {max, min};
long end = System.nanoTime();
return (end - start);
}
这基本上是一个合并排序操作,一旦排序,就会找到最小和最大的数字。我相信这种方法可以在 O(n lgn) 时间内运行。但是,当我 运行 函数的输入大小在每个 运行(1000、2000、4000 等)时加倍,当我以纳秒为单位计时时,我得到以下结果。
First pass: (0.12) seconds
Second pass: (0.98) seconds
Third pass: (0.91) seconds
Fourth pass: (0.90) seconds
Fifth pass: (1.33) seconds
我的问题是,鉴于这些结果,这些结果是否表明此方法在 O(n lgn) 时间内 运行 有效?
如果你有算法的源代码,你应该分析它而不是做运行时基准测试。
如果是递归函数,请查看 master theorem.
在你的函数中你做了 2 次大小为 n / 2
的递归调用,所以 a = 2, b = 2
和 f(n) = 2n
,因为在你的前两个 for 循环中你遍历了所有数组 (n)并使用最后三个 while 循环再次迭代所有数组大小 (n),因此 2n
.
如果你应用主定理,它会给出结果 Θ(n ln(n))
,所以 O(n ln(n))
也是正确的。