我正在尝试计算最小生成树算法的运行时间。
这是算法:
我理解从 1 到 3 的步骤的时间。但我真的不明白为什么按非降序对边进行排序需要 O(E logE) 时间。
谢谢。
最佳答案
因为最强大的算法(合并排序、堆排序、快速排序)保证在 n log n 最坏情况下对 n 项的集合进行排序。见证明here .在您的情况下，E 似乎是边数。所以 E log E 对它们进行排序。
关于algorithm - 为什么对图的边进行排序需要 O(E log E) 时间？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/43693713/