GoCalf 博客 - 旧站

算法的复杂度与 Master 定理

平时设计或者阅读一个算法的时候，必然会提到算法的复杂度（包括时间复杂度和空间复杂度）。比如我们说一个二分查找算法的平均时间复杂度为 O(log n)，快速排序可能是 O(n log n)。那这里的 O 是什么意思？这样的表达是否准确呢？今天来复习一下与算法复杂度相关的知识：函数渐进阶；记号 O、Ω、θ和 o；Master 定理。

发表于 2011年11月16日 algorithm complexity master theorem 算法

twilight-princess

黎明公主攻略：第四章沙漠深处的审判

林克和米德娜来到精灵之泉，最后一位光之精灵拉内鲁被解放了，但是就在这时魔法师赞特出现，并嘲笑林克和米德娜所做的一切都是没有意义的。随后其将米德娜打伤并把一块水晶碎片插入林克头部，让林克无法变回人形。

发表于 2011年11月10日 twilight princess 游戏

twilight-princess

黎明公主攻略：第三章深海鱼族的传说

回到卡卡里科村，林克遇见塔洛，他看到了林克的英雄之弓，又闹着要林克表演箭术，并要林克射中西北山丘房子顶上的一根木棒，就算是救世主。

发表于 2011年11月5日 twilight princess 游戏

自动机编程游戏：Manufactoria（流水线编程）

前几天在 Matrix67 的博客里看到了这个益智小游戏：Manufactoria，抽空玩了玩，虽然关卡不算多，但非常有趣。这是个程序设计类的游戏，感觉就像是个状态机吧（有限自动机？），从纸带上读取数据，具有分支和写数据的功能，利用简单的几种原件组装成一台可以识别特定模式或者完成指定运算的机器。

发表于 2011年11月3日 puzzle 游戏

求内积最大的子数组

问题描述：有两个长度均为 n 的整数数组 A 和 B，现在要从这两个数组中各抽出 s 个数字，分别构成两个新的数组 C 和 D，要求数组 C 和 D 的内积最大。

发表于 2011年10月29日 interview question 算法

求二叉树中两结点的最小公共祖先

据说这是微软的一道面试题，谁知道呢。问题描述：找出二叉树上任意两个指定结点的最近共同父结点（LCA，Least Common Ancestor）。

发表于 2011年10月21日 interview question data structure binary tree 算法

任务调度问题：资源占用与释放

问题描述：有 n 个任务，第 i 个任务运行时需要使用 R[i] 的资源，运行完毕后需要占用 O[i] 的资源（O[i] <= R[i]），假设现在我们总共有 s 的资源，要求设计一个调度算法，能保证所有任务能顺利执行；如果无法执行完，需要说明理由。

发表于 2011年10月15日 interview question task schedule greedy algorithm 算法

检测单向链表是否存在环

问题描述：在单向链表中，每个结点都包含一个指向下一个结点的指针，最后一个结点的这个指针被设置为空。但如果把最后一个结点的指针指向链表中存在的某个结点，就会形成一个环，在顺序遍历链表的时候，程序就会陷入死循环。我们的问题就是，如何检测一个链表中是否有环，如果检测到环，如何确定环的入口点（即求出环长，环前面的链长）。

发表于 2011年10月14日 interview question data structure linked list 算法

twilight-princess

黎明公主攻略：第二章死亡山颠的咆哮

打倒达巴巴之后，林克得到一个完整的心之容器（加一格血）。米德娜出现并将林克传送回法隆之泉处，顺路来到柯洛处，可以补充一点灯油，之前关上的栅栏打开了，过去后就来到海拉尔平原（Hyrule Field）。

发表于 2011年10月12日 twilight princess 游戏

利用不均匀硬币产生等概率

问题描述：有一枚不均匀的硬币，已知抛出此硬币后，正面向上的概率为 p（0 < p < 1）。请利用这枚硬币产生出概率相等的两个事件。

发表于 2011年10月8日 interview question probability 算法