Time Complexity
度量复杂性
Measuring complexity
为了简单起见，使用关于输入字符串的长度的函数来计算算法的运行时间
- 平均情况分析 (average-case analysis)：某特定长度的所有输入上的运行时间的平均值
- 最坏情况分析 (worst-case analysis)： 某特定长度的所有输入上的最长运行时间
大O和小O记法
- 使一个函数渐近地 (asymptotic) 不大于另一个函数的记法称为大O记法 (big-O notation)
- 例如 （渐进上界）
- 使一个函数渐近地小于另一个函数的记法称为大O记法 (small-o notation)
- 与大O的区别类似于 与 之间的区别
- 例如
分析算法
- 时间复杂性类 (time complexity class)
：由 时间的图灵机判定的所有语言的集合
语言对应的图灵机：
= ”对输入串 :
- 扫描带子， 如果在1的右边发现0，就拒绝。
- 如果带子上既有0也有1，就重复下一步。
- 扫描带子，删除一个0和一个1 。
- 如果删除所有1后还有0, 或者所有0都被删除以后还有1，就拒绝。 否则，如果在带子上既没有剩下0也没有剩下1，就接受。”
步骤1中，机器扫描带子以验证输入的形式是 0*1*，执行这次扫描需要步，将读写头重新放置在带子的左端另外需要 步，所以这一步骤总共需要 步。使用大O记法，称这一阶段需要 步。
- 在机器描述中没有提及重新放置读写头的操作
- 渐近记法允许忽略那些对运行时间的影响不超过常数倍的操作细节在
步骤2和3中，机器反复扫描带子，在每一次扫描中删除一个0和一个1。每一次扫描需要 步。每一次扫描删除两个符号，所以最多扫描次。所以这一阶段需要的全部时间是
- 即
模型间的复杂性关系
定理（设 是一个函数，）
- 每一个 时间的多带图灵机都和某一个 时间的单带图灵机等价。
- 每一个 时间的非确定型单带图灵机都与某一个 时间的确定型单带图灵机等价。
考察不同计算模型的选择怎样影响语言的时间复杂度 - 运行时间在确定型和非确定型图灵机上最多是
指数的差异 - 典型的指数时间算法来源于搜索解的所有空间，即蛮力搜索 (brute force search)。
- 运行时间在确定型单带和多带图灵机上最多是
多项式的差异 - 指数差异则被认为是大的，而多项式差异可以认为是较小的。
- 忽略多项式差异让我们可以不依赖于选择具体计算模型来研究理论。我们的目标是给出计算的基本性质，而不是图灵机或其他特殊模型的性质。
- 合理的确定型计算模型都是多项式等价的 (polynomially equivalent)，也就是说它们中任何一个模型都可以模拟另一个，而运行时间只增长多项式倍。
可满足性
一个布尔公式若是由 连接的若干子句组成， 则为合取范式 (conjunctive normal form) 的，称它为 cnf 公式。
若所有子句 (clause) 都有三个变量 (literal)， 则称为 3cnf 公式。
例：
如果对变量赋值后能使得公式的值等于 1，则该公式是可满足 (satisfiable) 的。
库克－列文定理：以下问题是 NP 完全的。
- SAT = { ⟨Φ⟩ | Φ is a satisfiable cnf boolean formula }
- 3SAT = { ⟨Φ⟩ | Φ is a satisfiable 3cnf boolean formula }
那么给定一个 3SAT 表达式，实施以下操作：
- 将每一个簇中的三个变量相互连接
- 将不同簇中不一致的相同变量相连 ( 比如 )
这样就可以把一个 3-SAT 布尔表达式转换成无向图
- 例：
P 类
Polynominal
P is the class of languages that are decidable in polynomial time on a deterministic single-tape Turing machine.
- 一个问题在 中，就有办法在时间 内求解
- 一个语言在 中，当且仅当它能被某个确定性单带图灵机，在多项式时间内判定
路径问题
证明：
= “对输入〈G,s,t〉，G是包含结点 s 和 t 的有向图：
- 在结点 s 上做标记。
- 复重下面步骤3，直到不再有结点被标记。
- 扫描 G 的所有边。如果找到一条边 (a,b)，a 被标记而 b 没被标记， 则标记 b。
- 若 t 被标记， 则接受；否则，拒绝。”
步骤1和4很容易用合理的确定型模型在多项式时间内实现。步骤3需要扫描输入，检查某些结点是否被标记，这也容易在多项式时间内实现。
互素问题
CS370 Lecture Two numbers are relatively prime if 1 is the largest integer that evenly divides them both.
证明：
欧几里得算法 如下：
= “对输入〈x,y〉，x和y是二进制表示的自然数：
- 重复下面的操作， 直到 y= 0。
- 赋值 。
- 交换 x 和 y 的值。
- 输出x。”
算法 以 为子程序求解 RELPRIME
= “对输入 〈x, y〉，x 和 y是二进制表示的自然数：
- 在〈x, y〉上运行 。
- 若结果为1，就接受；否则，就拒绝。”
的每一步仅消耗多项式时间，所以整个运行时间是多项式的。
NP 类
Nondeterministic polynominal
NP is the class of languages that have polynomial time verifiers.
非确定性：指问题只能通过验证猜测来解，而不能直接求解。
- 一个语言在 中，当且仅当它能被某个非确定型多项式时间图灵机判定
- 是否所有的NP问题都是 P 类问题（即 ）是理论计算机科学和当代数学中最大的悬而未决的问题之一。
哈密顿路径
A Hamiltonian path in a directed graph G is a directed path that goes through each node exactly once.
证明
= “对输入〈G,s,t〉，G是包含结点 s 和 t 的有向图：
- 写 m 个数 ，m是G的结点数，每一个数是从1到 m 中非确定挑选。
- 在列中检查重复性，若发现有重复，则拒绝。
- 检查 和 是否都成立。若有一个不成立，则拒绝。
- 对于 1 到 m-1 的每一个， 检查 是否为 G 的一条边。若有一 个不是，则拒绝。否则，所有检查都通过了，接受。”
在步骤 1 中，非确定的选择显然在多项式时间内运行。在步骤 2 和 3 中，每一步进行一次检查，所以合起来它们仍在多项式时间内运行。步骤4显然也在多项式时间内运行。 所以该算法在非确定型多项式时间内运行。
团问题
Given a specified size k, determine whether a graph contains k-clique. A clique in a subset graph that every two distinct vertices are adjacent, i.e., there is an edge connecting every pair of vertices in the clique. (每两个结点都有边相连)
（法一）构建验证机
= “ 对输入〈〈G,k〉, c〉
- 检查 c 是否是 G 中 k 个结点的子图。
- 检查 G 是否包含连接 c 中结点的所有边。
- 若两项检查都通过，则接受；否则，拒绝。”
（🏆 法二）构建非确定性图灵机
= “对输入〈G, k〉，G是一个图：
- 非确定地选择 G 中 k 个结点的子集 c。
- 检查 G 是否包含连接 c 中结点的所有边。
- 若是，则接受；否则拒绝。”
3SAT is polynomial time reducible to CLIQUE.
Given 3SAT
- Select one node corresponding to a truc literal in the satisfying assignment in each triple. (If more than one literal is true in a particular clause, choose one arbitrarily.)
- The number of nodes selected is k. Each pair of nodes can be joined by an edge because no pair fits one of the exceptions.
- Duplication Exception: They could not be from the same triple because we selected only one node pertriple.
- Conflic Exception: They could not have contradictory labels because the associated literals were both true in the satisfying assignment.
- Thus, G contains a k-clique
NP 完全
- 如果语言 B 满足下面两个条件， 就称为 NP 完全的 (NP-complete)：
- B 属于 NP
- NP 中的每个A都多项式时间可归约到 B
- 若语言 B 是 NP 完全的，且 ，则 。
- 若语言 B 是 NP 完全的，且 ，C 属于NP，则 C 是 NP 完全的。
顶点覆盖问题
Given an undirected graph G, a vertex cover of G is a subset of the nodes where every edge of G touches one of those nodes → VERTEX-COVER = | 是由一个顶点覆盖尺寸为 （即包含的顶点数）的无向图 .
3SAT is polynomial time mapping reducible to VERTEX-COVER.
Given 3SAT has variables and clauses
- First put the nodes of the variable that correspond to the true literals in the assignment into the vertex cover (i.e., nodes)
- Then, select one true literal in every clause and put the remaining two nodes from every clause into the vertex (i.e., nodes)
- Thus, G contains a k vetex-cover,