为什么对图的边进行排序需要 O(E log E) 时间？
Why sorting Edges of a graph takes O(E log E) time?
我正在尝试计算最小生成树算法的运行时间。
算法如下：
我理解从 1 到 3 的步骤的时间。但是我真的不明白为什么按非降序对边进行排序需要 O(E logE) 时间。
谢谢。
步骤 4 对图中的所有 |E| 条边进行排序。
假设我们使用快速排序或等效算法，因此该步骤将使用 O(n log n) 时间来执行该步骤。在这种情况下，n = |E|，因此排序步骤需要 O(|E| log |E|).
在平均或最坏情况下，所有通用比较排序的性能都不能优于 O(n log n)。所以作者选择了任意排序算法的平均场景，大家可以自行选择。
因为最强大的算法（合并排序、堆排序、快速排序）保证在 n log n 最坏情况下对 n 项的集合进行排序。参见证明 here。在您的情况下，E 似乎是边数。所以 E log E 对它们进行排序。
所有基于比较的排序算法至少需要 $\Omega(n \log n)$ 时间来排序 $n$ 个数字，堆排序和归并排序是渐进最优的，因为它们需要 $O(n \log n )$ 时间。
我正在尝试计算最小生成树算法的运行时间。
算法如下：
我理解从 1 到 3 的步骤的时间。但是我真的不明白为什么按非降序对边进行排序需要 O(E logE) 时间。
谢谢。
步骤 4 对图中的所有 |E| 条边进行排序。
假设我们使用快速排序或等效算法，因此该步骤将使用 O(n log n) 时间来执行该步骤。在这种情况下，n = |E|，因此排序步骤需要 O(|E| log |E|).
在平均或最坏情况下，所有通用比较排序的性能都不能优于 O(n log n)。所以作者选择了任意排序算法的平均场景，大家可以自行选择。
因为最强大的算法（合并排序、堆排序、快速排序）保证在 n log n 最坏情况下对 n 项的集合进行排序。参见证明 here。在您的情况下，E 似乎是边数。所以 E log E 对它们进行排序。
所有基于比较的排序算法至少需要 $\Omega(n \log n)$ 时间来排序 $n$ 个数字，堆排序和归并排序是渐进最优的，因为它们需要 $O(n \log n )$ 时间。