标签： 算法复杂度

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