1,068
个编辑
更改
跳到导航
跳到搜索
第8行：
第8行： − + 第19行：
第19行： − + 第94行：
第94行： − + − + 第105行：
第105行： − +
无编辑摘要
在'''计算机科学 computer science'''中，一个'''算法 algorithm'''的'''计算复杂度'''或简单的'''复杂度'''就是运行这个算法所需要的资源量，特别是'''时间'''（CPU占用时间）和'''空间'''（内存占用空间）需求。
在'''计算机科学 computer science'''中，一个'''算法 algorithm'''的'''[[计算复杂度]]'''或简单的'''复杂度'''就是运行这个算法所需要的资源量，特别是'''时间'''（CPU占用时间）和'''空间'''（内存占用空间）需求。
对一个有明确定义的算法的复杂度进行的研究叫做'''算法分析 analysis of algorithm'''，而对'''问题 problem'''的复杂度研究叫做'''计算复杂度理论 computation complexity theory'''分析。举个例子，怎样把一串数字从小到大进行排序，是一个问题（problem）；而针对这一问题，我们有多种明确定义的算法，如选择排序，归并排序等。假设我们有<math>n</math>个数字，那么排序问题的复杂度就是<math>nlogn</math>，而选择排序的复杂度是<math>n^2</math>，归并排序的复杂度是<math>6nlogn</math>。
对一个有明确定义的算法的复杂度进行的研究叫做'''[[算法分析]] analysis of algorithm'''，而对'''问题 problem'''的复杂度研究叫做'''[[计算复杂度理论]] computation complexity theory'''分析。举个例子，怎样把一串数字从小到大进行排序，是一个问题（problem）；而针对这一问题，我们有多种明确定义的算法，如选择排序，归并排序等。假设我们有<math>n</math>个数字，那么排序问题的复杂度就是<math>nlogn</math>，而选择排序的复杂度是<math>n^2</math>，归并排序的复杂度是<math>6nlogn</math>。
这两个领域是高度相关的，因为算法的复杂度一直是该算法所求解问题复杂度的'''上限 upper bound'''。
这两个领域是高度相关的，因为算法的复杂度一直是该算法所求解问题复杂度的'''上限 upper bound'''。
==计算模型==
==计算模型==
复杂度的评估依赖于'''计算模型 model of computation'''的选择，包括定义在一个时间单位内完成的基本操作。当没有明确指定时，默认使用的计算模型是'''多带图灵机 multitape Turing machine'''。
复杂度的评估依赖于'''[[计算模型]] model of computation'''的选择，包括定义在一个时间单位内完成的基本操作。当没有明确指定时，默认使用的计算模型是'''多带[[图灵机]] multitape Turing machine'''。
===确定性模型===
===确定性模型===
一个'''确定性模型 deterministic model '''的计算是一种机器的后续状态和要执行的操作完全由前面的状态决定的计算模型。历史上，最早的确定性模型是'''递归函数 recursive functions'''、 '''lambda 演算 lambda calculus'''和'''图灵机 Turing machines'''。'''随机存取机器 Random access machine '''(也称 RAM-machines)的模型也被广泛使用，更接近真实的'''计算机 computer'''。
一个'''确定性模型 deterministic model '''的计算是一种机器的后续状态和要执行的操作完全由前面的状态决定的计算模型。历史上，最早的确定性模型是'''[[递归]]函数 recursive functions'''、 '''lambda 演算 lambda calculus'''和'''[[图灵机]] Turing machines'''。'''随机存取机器 Random access machine '''(也称 RAM-machines)的模型也被广泛使用，更接近真实的'''计算机 computer'''。
当计算模型没有被指定时，通常假设它是一个'''多带图灵机 multitape Turing machine'''。对于大多数算法，在多带图灵机上的时间复杂度与在RAM-machines上的相同，尽管可能需要注意如何将数据存储在内存中，以确保这种等价性.
当计算模型没有被指定时，通常假设它是一个'''多带图灵机 multitape Turing machine'''。对于大多数算法，在多带图灵机上的时间复杂度与在RAM-machines上的相同，尽管可能需要注意如何将数据存储在内存中，以确保这种等价性.
===非确定性计算===
===非确定性计算===
在'''非确定性计算模型 non-deterministic model of computation'''中，例如'''不确定的图灵机 non-deterministic Turing machine'''，在计算的某些步骤中可能会进行一些选择。在复杂度理论中，非确定性时间复杂度即为，同时考虑所有可能的选择且做出最佳选择时所需的时间。换句话说，我们认为计算是多个（相同的）处理器上同时进行的，而不确定计算时间是第一个完成计算的处理器所花费的时间。这种并行性在一定程度上可以通过运行特定'''量子算法 quantum algorithm'''的叠加'''纠缠态 entangled state'''来实现'''量子计算 quantum computing'''。例如小整数上的'''肖尔因式分解 Shor's factorization'''。
在'''非确定性计算模型 non-deterministic model of computation'''中，例如'''不确定的图灵机 non-deterministic Turing machine'''，在计算的某些步骤中可能会进行一些选择。在复杂度理论中，非确定性时间复杂度即为，同时考虑所有可能的选择且做出最佳选择时所需的时间。换句话说，我们认为计算是多个（相同的）处理器上同时进行的，而不确定计算时间是第一个完成计算的处理器所花费的时间。这种并行性在一定程度上可以通过运行特定'''[[量子算法]] quantum algorithm'''的叠加'''纠缠态 entangled state'''来实现'''[[量子计算]] quantum computing'''。例如小整数上的'''肖尔因式分解 Shor's factorization'''。
Even when such a computation model is not realistic yet, it has theoretical importance, mostly related to the [[P = NP]] problem, which questions the identity of the complexity classes formed by taking "polynomial time" and "non-deterministic polynomial time" as least upper bounds. Simulating an NP-algorithm on a deterministic computer usually takes "exponential time". A problem is in the complexity class [[NP (complexity)|NP]], if it may be solved in [[polynomial time]] on a non-deterministic machine. A problem is [[NP-complete]] if, roughly speaking, it is in NP and is not easier than any other NP problem. Many [[combinatorics|combinatorial]] problems, such as the [[Knapsack problem]], the [[travelling salesman problem]], and the [[Boolean satisfiability problem]] are NP-complete. For all these problems, the best known algorithm has exponential complexity. If any one of these problems could be solved in polynomial time on a deterministic machine, then all NP problems could also be solved in polynomial time, and one would have P = NP. {{As of|2017}} it is generally conjectured that {{nowrap|P ≠ NP,}} with the practical implication that the worst cases of NP problems are intrinsically difficult to solve, i.e., take longer than any reasonable time span (decades!) for interesting lengths of input.
Even when such a computation model is not realistic yet, it has theoretical importance, mostly related to the [[P = NP]] problem, which questions the identity of the complexity classes formed by taking "polynomial time" and "non-deterministic polynomial time" as least upper bounds. Simulating an NP-algorithm on a deterministic computer usually takes "exponential time". A problem is in the complexity class [[NP (complexity)|NP]], if it may be solved in [[polynomial time]] on a non-deterministic machine. A problem is [[NP-complete]] if, roughly speaking, it is in NP and is not easier than any other NP problem. Many [[combinatorics|combinatorial]] problems, such as the [[Knapsack problem]], the [[travelling salesman problem]], and the [[Boolean satisfiability problem]] are NP-complete. For all these problems, the best known algorithm has exponential complexity. If any one of these problems could be solved in polynomial time on a deterministic machine, then all NP problems could also be solved in polynomial time, and one would have P = NP. {{As of|2017}} it is generally conjectured that {{nowrap|P ≠ NP,}} with the practical implication that the worst cases of NP problems are intrinsically difficult to solve, i.e., take longer than any reasonable time span (decades!) for interesting lengths of input.