违反Big中给定的平均时间复杂度
我试图实现一个解决方案，在给定的整数列表中找到第k个最大元素，其中O(N*log(N))平均时间复杂度为Big-O表示法，其中N是列表中元素的数量。
根据我的理解，合并排序的平均时间复杂度为O(N*log(N))但是在我的下面的代码中，我实际上使用了一个额外的for循环以及mergesort算法来删除重复，这肯定违反了我的find O(N*log(N))的第k个最大元素。 我如何通过在Big-O符号中实现我的任务O(N*log(N))平均时间复杂度来解决这个问题？
public class FindLargest {
public static void nthLargeNumber(int[] arr, String nthElement) {
mergeSort_srt(arr, 0, arr.length - 1);
// remove duplicate elements logic
int b = 0;
for (int i = 1; i < arr.length; i++) {
if (arr[b] != arr[i]) {
b++;
arr[b] = arr[i];
}
}
int bbb = Integer.parseInt(nthElement) - 1;
// printing second highest number among given list
System.out.println("Second highest number is::" + arr[b - bbb]);
}
public static void mergeSort_srt(int array[], int lo, int n) {
int low = lo;
int high = n;
if (low >= high) {
return;
}
int middle = (low + high) / 2;
mergeSort_srt(array, low, middle);
mergeSort_srt(array, middle + 1, high);
int end_low = middle;
int start_high = middle + 1;
while ((lo <= end_low) && (start_high <= high)) {
if (array[low] < array[start_high]) {
low++;
} else {
int Temp = array[start_high];
for (int k = start_high - 1; k >= low; k--) {
array[k + 1] = array[k];
}
array[low] = Temp;
low++;
end_low++;
start_high++;
}
}
}
public static void main(String... str) {
String nthElement = "2";
int[] intArray = { 1, 9, 5, 7, 2, 5 };
FindLargest.nthLargeNumber(intArray, nthElement);
}
}
这里唯一的问题是你不懂如何进行时间分析。 如果您有一个需要O（n）的例程和一个采用O（n * log（n））的例程，则两者都运行总共需要O（n * log（n））。 因此，您的代码像O（n * log（n））那样运行。
为了正式做事，我们会注意到O（）的定义如下：f（x）∈O（g（x））当且仅当存在值c> 0和y使得f（x）< cg（x）每当x> y时。
你的合并排序在O（n * log（n））中，告诉我们当某个c1，y1的n> y1时，它的运行时间是以c1 * n * log（n）为界。 您的重复消除在O（n）中，告诉我们，当某个c2和y2的n> y2时，其运行时间受c2 * n约束。 使用这个，我们可以知道，当n> max（y1，y2）时，两者的总运行时间受c1 * n * log（n）+ c2 * n限制。 因为log（n）> 1，我们知道c1 * n * log（n）+ c2 * n <c1 * n * log（n）+ c2 * n * log（n），这当然简化为（c1 + C2）* N *的log（n）。 因此，当n> max（y1，y2）时，我们可以知道两者的运行时间在（c1 + c2）* n * log（n）之上，因此使用c1 + c2作为c和max （y1，y2）作为我们的y，我们知道两者的运行时间在O（n * log（n））中。
非正式地，你可以知道更快的增长函数总是占主导地位，所以如果一段代码是O（n），第二个代码是O（n ^ 2），那么组合是O（n ^ 2）。 如果一个是O（log（n）），第二个是O（n），则组合是O（n）。 如果一个是O（n ^ 20），第二个是O（n ^ 19.99），则组合是O（n ^ 20）。 如果一个是O（n ^ 2000），第二个是O（2 ^ n），那么组合是O（2 ^ n）。
这里的问题是你的合并例程，你已经使用了另一个循环，我不明白为什么，因此我会说你的合并O（n ^ 2）算法，它将合并排序时间更改为O（n ^ 2）。
这是典型的O（N）合并例程的伪代码： -
void merge(int low,int high,int arr[]) {
int buff[high-low+1];
int i = low;
int mid = (low+high)/2;
int j = mid +1;
int k = 0;
while(i<=mid && j<=high) {
if(arr[i]<arr[j]) {
buff[k++] = arr[i];
i++;
}
else {
buff[k++] = arr[j];
j++;
}
}
while(i<=mid) {
buff[k++] = arr[i];
i++;
}
while(j<=high) {
buff[k++] = arr[j];
j++;
}
for(int x=0;x<k;x++) {
arr[low+x] = buff[x];
}
}