如何知道我在链表上的合并排序实现中是否使用 O(nlog(n)) 。我应该向 O(nlog(n)) 输入什么才能知道我实现合并排序的时间。
public static LinkedListNode<T> MergeSortLL<T>(LinkedListNode<T> Head) where T : IComparable<T>
{
if (Head?.Next == null)
{
return Head;
}
var middle = GetMiddle(Head);
var half = middle.Next;
middle.Next = null;
Head = Merge(MergeSortLL(Head), MergeSortLL(half));
return Head;
}
public static LinkedListNode<T> Merge<T>(LinkedListNode<T> Left, LinkedListNode<T> Right) where T : IComparable<T>
{
var mHead = new LinkedListNode<T>(default(T));
LinkedListNode<T> curr = mHead;
while (Left != null && Right != null)
{
if (Left.Value.CompareTo(Right.Value) <= 0)
{
curr.Next = Left;
Left = Left.Next;
}
else
{
curr.Next = Right;
Right = Right.Next;
}
curr = curr.Next;
}
curr.Next = (Left == null) ? Right : Left;
return mHead.Next;
}
public static LinkedListNode<T> GetMiddle<T>(LinkedListNode<T> Head) where T : IComparable<T>
{
if (Head == null)
{
return Head;
}
LinkedListNode<T> slow, fast;
slow = fast = Head;
while (fast.Next?.Next != null)
{
slow = slow.Next;
fast = fast.Next.Next;
}
return slow;
}
最佳答案
请注意,已知该算法执行 O(N*log(N)) 比较。如果您想确认这一点(因为它已被证明),您可以放置一个计数器并在每次比较时递增它。
例如
public static int Comparisons;
public static LinkedListNode<T> Merge<T>(LinkedListNode<T> Left, LinkedListNode<T> Right) where T : IComparable<T>
{
// ...
Comparisons++;
if (Left.Value.CompareTo(Right.Value) <= 0)
// ...
}
并检查
LinkedListNode<int> head = ...;
Comparisons = 0;
head = MergeSortLL(head);
Debug.Print(Comparisons);
但请注意,该算法也具有显着的隐藏成本(即使使用慢/快指针技术,也要找到中间值)。
关于c# - 如何从合并排序中获得O(n log(n))?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35406612/