如何从合并排序中得到 O(n log(n))?
How to get O(n log(n)) from merge sort?
如何知道我是否在链表上的合并排序实现中使用了 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;
}
您可以做的是向您的排序方法添加一个计数器参数(引用),并在每次进入循环时递增它。然后将此计数器与您尝试排序的元素数量的复杂性进行比较(我们称该数量为 N)。然后你会看到你是在 O(NlogN) 中更多还是在 O(N²) 中更多。
例如,如果您尝试对 N =10 个元素进行排序时计数器为 30,如
10*log(10) = 23,02... 和 10² = 100 你会发现 O(NlogN) 比 O(N²) 更多。
请注意,已知此算法执行 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);
但请注意,此算法也已知具有显着的隐藏成本(找到中间,即使使用 slow/fast 指针技术)。
如何知道我是否在链表上的合并排序实现中使用了 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;
}
您可以做的是向您的排序方法添加一个计数器参数(引用),并在每次进入循环时递增它。然后将此计数器与您尝试排序的元素数量的复杂性进行比较(我们称该数量为 N)。然后你会看到你是在 O(NlogN) 中更多还是在 O(N²) 中更多。
例如,如果您尝试对 N =10 个元素进行排序时计数器为 30,如 10*log(10) = 23,02... 和 10² = 100 你会发现 O(NlogN) 比 O(N²) 更多。
请注意,已知此算法执行 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);
但请注意,此算法也已知具有显着的隐藏成本(找到中间,即使使用 slow/fast 指针技术)。