我已经运行了这个算法,我知道它可以工作,但我不太确定它的最坏情况下的时间复杂度。 我认为这个合并排序算法的最坏情况时间复杂度是 O(n log n)。如果有人能提供第二意见,我将不胜感激。
//The main function
public Node mergeSort(Node a){
Node oldHead = a;
int mid = length(a)/2;
if(a == null || a.next == null)
return a;
while(mid-1 > 0){
oldHead = oldHead.next;
mid--;
}
Node newHead = oldHead.next;
oldHead.next = null;
oldHead = a;
Node t1 = mergeSort(oldHead);
Node t2 = mergeSort(newHead);
return merge(t1,t2);
}
public Node merge(Node a, Node b){
Node result = head;
if(a == null)
return b;
if(b == null)
return a;
if(b.name.compareTo(a.name) <= 0){
result = b;
result.next = merge(a,b.next);
}
else{
result = a;
result.next = merge(a.next,b);
}
return result;
}
public int length(Node a){
int count = 0;
Node c = a;
while( c != null){
count++;
c = c.next;
}
return count;
}
最佳答案
是的,这仍然是 O(n log(n))。与传统的合并排序算法相比,这里没有任何改变来改变它的时间复杂度。与链表的唯一真正区别是将列表一分为二。这具有 O(n) 的复杂性,但它与同样具有复杂性 O(n) 的合并操作处于同一级别。所以它对复杂性没有整体影响。
编辑。长度操作是 O(n),但它与拆分操作和合并操作处于同一级别,它们也是 O(n),因此它也不会影响时间复杂度。
关于java - 这种链表合并排序算法的时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43703367/