标签: 算法复杂度

  1. 上篇文章 扫雷是 NP 完全问题 之后, You Xu 提到"不光扫雷是 NP 完全问题, 空当接龙 问题也极有可能是一个 NP 完全问题。目前最好的通用 planner 只能解半副牌"。他说对了,不光扫雷, Windows 自带的游戏都是 NP 完全的。Windows 自带的游戏除了扫雷,还有空当接龙和蜘蛛纸牌。
  2. 本科时有同学扫雷最快可以在 60 多秒完成高级难度,让我这种最快 130 秒的人非常惭愧,当时就想着编一个全自动的扫雷程序,不过一直也没写。今天才知道,原来扫雷问题是 NP 完全的 ...
  3. Xie Xie 给我看了一个链接 性能调优 -- 永远超乎想象 ,里面提到了素数筛法的复杂度,作者用实验发现此筛法是线形的。
  4. 更新:证明的关键一步发现错误,作者更新了论文,结论甚至论文标题都改了(废话),新版本 On the graph isomorphism problem
  5. Game Theory 即博弈论,目前在经济学中运用得最多 ( 纳什更因为他在这上面的工作拿到了诺贝尔经济学奖 )。但在最近几年,理论计算机界对它的研究也很热。
  6. 很多人一看到 NP-hard ,就从字面上理解成为比 NP 还难的问题。但如果这里的「更难」指得是解决问题所花费时间更长的话,这个论断是不正确的。从算法角度来看, NP-hard 问题的确比 NP 难,但比 NP 还难(指花费时间更多)的问题却不见得是 NP-hard 的。