Category: Programming

势能法 Potential Method

均摊分析 Amortized Analysis

假设我们把每个操作的最大耗时记为f(n)，n个操作以后则得到时间上界f(n)⋅n，然而这个界限是不 tight 的，因为一些操作会比其他操作耗时更多。

均摊分析关注于每个操作消耗的平均时间。

Continue reading “算法导论笔记0x15 —— 均摊分析 & 斐波那契堆”

KMP

m is the length of text
n is the length of pattern

• [Prefix Array Logic]
• 初始j指向0索引，i指向1索引
• 数组0索引初始化为0
• 检查匹配
  • 不匹配时，跳到j索引的前一个数组值所对应的索引位置继续检查匹配
    • 不匹配时，j=Array[j-1]
    • 若j是0，数组值为0，Array[i]=0
  • 匹配时，数组中的值为j的值加1，i和j同时加1继续检查匹配
    • Array[i]=j+1, i++, j++

Continue reading “算法导论笔记0x16 —— 子串搜索”

Must sacrifice one of three desired features.

• Solve problem to optimality.
• Solve problem in polynomial time.
• Solve arbitrary instances of the problem.

Continue reading “算法设计与分析笔记0x10 —— Extending the Limits of Tractability”

P Decision problems solvable in polynomial time.
PSPACE Decision problems solvable in polynomial space.

• P ⊆ PSPACE
• 3-SAT is in PSPACE
• NP ⊆ PSPACE

Continue reading “算法设计与分析笔记0x0F —— PSPACE”

Partitioning Problems

3-Dimensional Matching

3D-MATCHING. Given n instructors, n courses, and n times, and a list of the possible courses and times each instructor is willing to teach, is it possible to make an assignment so that all courses are taught at different times?
3D-MATCHING. Given disjoint sets X, Y, and Z, each of size n and a set T ⊆ X × Y × Z of triples, does there exist a set of n triples in T such that each element of X ∪ Y ∪ Z is in exactly one of these triples?

Continue reading “算法设计与分析笔记0x0E —— Part 3 NP完全”

Algorithm design patterns.

• Greedy.
• Divide-and-conquer.
• Dynamic programming.
• Max-flow min-cut.
• Reductions.

Algorithm design anti-patterns.

• NP-completeness.
• PSPACE-completeness.
• Undecidability.

Continue reading “算法设计与分析笔记0x0C —— Part 1 NP完全”