对于某类特定问题最优时间复杂度解的存在性的疑问
  • 板块灌水区
  • 楼主xigou_zmx
  • 当前回复49
  • 已保存回复49
  • 发布时间2023/8/21 18:51
  • 上次更新2023/11/3 02:10:39
查看原帖
对于某类特定问题最优时间复杂度解的存在性的疑问
1030676
xigou_zmx楼主2023/8/21 18:51

以单源最短路径举例。大部分人平常使用的都是普通 dijkstra 或者 堆优化的 dijkstra 或者 spfa。相信不少人都知道可以使用斐波那契堆将 dijkstra 优化成 O(nlog⁡n+m)O(n \log n+m)。然后今年(也有可能是去年),有国外学者宣布研究出了大常数的单源最短路径算法,复杂度为 O(nlog⁡log⁡n+m)O(n \log \log n + m) 的算法。而单源最短路径算法的理论最优解下限明显是 O(n+m)O(n+m),那请问,在我们找到(也有可能找不到) O(n+m)O(n+m) 的算法之前,我们能否证明或者证伪存在 O(n+m)O(n+m) 的算法.

2023/8/21 18:51
加载中...