更改

For a precise definition of what it means to solve a problem using a given amount of time and space, a computational model such as the deterministic Turing machine is used. The time required by a deterministic Turing machine M on input x is the total number of state transitions, or steps, the machine makes before it halts and outputs the answer ("yes" or "no"). A Turing machine M is said to operate within time f(n) if the time required by M on each input of length n is at most f(n). A decision problem A can be solved in time f(n) if there exists a Turing machine operating in time f(n) that solves the problem. Since complexity theory is interested in classifying problems based on their difficulty, one defines sets of problems based on some criteria. For instance, the set of problems solvable within time f(n) on a deterministic Turing machine is then denoted by DTIME(f(n)).

For a precise definition of what it means to solve a problem using a given amount of time and space, a computational model such as the deterministic Turing machine is used. The time required by a deterministic Turing machine M on input x is the total number of state transitions, or steps, the machine makes before it halts and outputs the answer ("yes" or "no"). A Turing machine M is said to operate within time f(n) if the time required by M on each input of length n is at most f(n). A decision problem A can be solved in time f(n) if there exists a Turing machine operating in time f(n) that solves the problem. Since complexity theory is interested in classifying problems based on their difficulty, one defines sets of problems based on some criteria. For instance, the set of problems solvable within time f(n) on a deterministic Turing machine is then denoted by DTIME(f(n)).

为了精确定义在给定的时间和空间内解决问题的意义，我们使用了确定性图灵机这样的计算模型。确定性图灵机 m 在输入 x 上所需的时间是该机在停止并输出答案(“是”或“否”)之前进行的状态转换或步骤的总数。如果 m 对每个长度 n 的输入所需的时间最多为 f (n) ，则称 m 在时间 f (n)内工作。如果存在一个在时间 f (n)内运行的图灵机，决策问题 a 可以在时间 f (n)内得到解决。由于复杂性理论对根据问题的难度对问题进行分类感兴趣，因此人们根据一些标准来定义问题集。例如，在确定性图灵机上，在时间 f (n)内可解决的问题的集合由 DTIME (f (n))表示。

为了精确定义在给定的时间和空间内解决问题的意义，我们使用了确定性图灵机这样的计算模型。确定性图灵机 m 在输入 x 上所需的时间是该机在停止并输出答案(“是”或“否”)之前进行的状态转换或步骤的总数。如果 m 对每个长度 n 的输入所需的时间最多为 f (n) ，则称 m 在时间 f (n)内工作。如果存在一个在时间 f (n)内运行的图灵机，决策问题 a 可以在时间 f (n)内得到解决。由于复杂性理论对根据问题的难度对问题进行分类感兴趣，因此人们根据一些标准来定义问题集。例如，在确定性图灵机上，在时间 f (n)内可解决的问题的集合由 '''<font color="#ff8000"> DTIME(f (n))</font>'''表示。

Analogous definitions can be made for space requirements. Although time and space are the most well-known complexity resources, any complexity measure can be viewed as a computational resource. Complexity measures are very generally defined by the Blum complexity axioms. Other complexity measures used in complexity theory include communication complexity, circuit complexity, and decision tree complexity.

Analogous definitions can be made for space requirements. Although time and space are the most well-known complexity resources, any complexity measure can be viewed as a computational resource. Complexity measures are very generally defined by the Blum complexity axioms. Other complexity measures used in complexity theory include communication complexity, circuit complexity, and decision tree complexity.

可以对空间要求作类似的定义。虽然时间和空间是最著名的复杂性资源，但任何复杂性度量都可以被视为计算资源。复杂性度量通常是由 Blum 复杂性公理定义的。复杂性理论中使用的其他复杂性度量包括通信复杂性、电路复杂性和决策树复杂性。

可以对空间要求作类似的定义。虽然时间和空间是最著名的复杂性资源，但任何'''<font color="#ff8000"> 复杂性度量Complexity measure</font>'''都可以被视为计算资源。复杂性度量通常是由 Blum 复杂性公理定义的。复杂性理论中使用的其他复杂性度量包括'''<font color="#ff8000">通信复杂性、电路复杂性和决策树复杂性</font>'''。

算法的复杂性通常用大 O 符号来表示。

算法的复杂性通常用大 O 符号来表示。

===Best, worst and average case complexity最佳、最差和平均情况下的复杂度===

===Best, worst and average case complexity最佳、最差和平均情况下的复杂度===