1,068
个编辑
更改
跳到导航
跳到搜索
第3行：
第3行： − 第15行：
第14行： + − − 第28行：
第26行： + + − 另一个重要的资源是运行算法所需的'''计算机内存 computer memory'''大小。 第43行：
第42行： + + 第54行：
第55行： + + + − 例如，通常整数'''乘法 multiplication'''的复杂度是<math>O(n^2),</math>，这意味着存在一个常数<math>c_u</math>，使得两个最多{{mvar|n}}位的整数乘法可以在小于<math>c_un^2</math>的时间内完成。这个界限是尖锐的，因为最坏情况复杂度和平均情况复杂度是<math>\Omega(n^2),</math>，意味着存在一个常数<math>c_l</math>，使得这些复杂度比<math>c_ln^2</math>大。 第73行：
第76行： + + + + + + + + + + + 第115行：
第129行： + + − 评估算法的复杂度是'''算法设计 algorithm design'''的一个重要组成部分，因为这给出了一个算法关于预期性能的有用信息。 + + 第179行：
第196行： − − [[Category:Analysis of algorithms]] − [[Category:Computational complexity theory]] − [[Category:Computational resources]] − − − − [[Category:Analysis of algorithms]] − − Category:Analysis of algorithms − − 类别: 算法分析 − − [[Category:Computational complexity theory]] − − Category:Computational complexity theory
无编辑摘要
|description=文本情感分析是指用自然语言处理、文本挖掘以及计算机语言学等方法来识别、提取、量化和研究原素材中的情感状态和主观信息。情感分析被广泛应用于来源于用户的素材，如评论和调查回复，在线和社交媒体；也被应用于来源于卫生保健的素材，其应用范围涵盖了从市场营销到客户服务到临床医学的各个方面。
|description=文本情感分析是指用自然语言处理、文本挖掘以及计算机语言学等方法来识别、提取、量化和研究原素材中的情感状态和主观信息。情感分析被广泛应用于来源于用户的素材，如评论和调查回复，在线和社交媒体；也被应用于来源于卫生保健的素材，其应用范围涵盖了从市场营销到客户服务到临床医学的各个方面。
}}
}}
{{Short description|amount of resources (usually time and/or memory) to perform an algorithm}}
{{Short description|amount of resources (usually time and/or memory) to perform an algorithm}}
对一个有明确定义的算法的复杂度进行的研究叫做'''[[算法分析]] analysis of algorithm'''，而对'''问题 problem'''的复杂度研究叫做'''计算复杂度理论 computation complexity theory'''分析。举个例子，怎样把一串数字从小到大进行排序，是一个问题；而针对这一问题，我们有多种明确定义的算法，如选择排序，归并排序等。假设我们有<math>n</math>个数字，那么排序问题的复杂度就是<math>nlogn</math>，而选择排序的复杂度是<math>n^2</math>，归并排序的复杂度是<math>6nlogn</math>。
对一个有明确定义的算法的复杂度进行的研究叫做'''[[算法分析]] analysis of algorithm'''，而对'''问题 problem'''的复杂度研究叫做'''计算复杂度理论 computation complexity theory'''分析。举个例子，怎样把一串数字从小到大进行排序，是一个问题；而针对这一问题，我们有多种明确定义的算法，如选择排序，归并排序等。假设我们有<math>n</math>个数字，那么排序问题的复杂度就是<math>nlogn</math>，而选择排序的复杂度是<math>n^2</math>，归并排序的复杂度是<math>6nlogn</math>。
这两个领域是高度相关的，因为算法的复杂度一直是该算法所求解问题复杂度的'''上限 upper bound'''。
这两个领域是高度相关的，因为算法的复杂度一直是该算法所求解问题复杂度的'''上限 upper bound'''。
==资源==
==资源==
===时间===
===时间===
在'''复杂度理论 complexity theory'''中不使用通常的时间单位(秒、分等)，因为它们过于依赖于特定计算机的选择和技术的演变。例如，今天的计算机执行算法的速度明显快于20世纪60年代的计算机; 然而，这不是算法的固有特征，而是计算机硬件技术进步的结果。复杂度理论旨在量化算法的内在时间需求，也就是算法对任何计算机的基本时间约束。这是通过统计在计算过程中执行的基本操作数量来实现的。这些基本操作假定在给定的机器上占用常量时间(即不受输入大小的影响) ，通常被称为步骤。
在'''复杂度理论 complexity theory'''中不使用通常的时间单位(秒、分等)，因为它们过于依赖于特定计算机的选择和技术的演变。例如，今天的计算机执行算法的速度明显快于20世纪60年代的计算机; 然而，这不是算法的固有特征，而是计算机硬件技术进步的结果。复杂度理论旨在量化算法的内在时间需求，也就是算法对任何计算机的基本时间约束。这是通过统计在计算过程中执行的基本操作数量来实现的。这些基本操作假定在给定的机器上占用常量时间(即不受输入大小的影响) ，通常被称为步骤。
===空间===
===空间===
另一个重要的资源是运行算法所需的'''计算机内存 computer memory'''大小。
===其他===
===其他===
在'''排序 sorting'''和'''搜索 searching'''中，通常考虑的资源是需要做几次''比较大小''。如果数据组织得当，这通常是一个很好的时间复杂度测量方法。
在'''排序 sorting'''和'''搜索 searching'''中，通常考虑的资源是需要做几次''比较大小''。如果数据组织得当，这通常是一个很好的时间复杂度测量方法。
==复杂度：输入规模的函数==
==复杂度：输入规模的函数==
复杂度作为关于输入长度的函数
复杂度作为关于输入长度的函数
'''最坏情况复杂度 worst-case complexity'''是对所有输入{{mvar|n}}长度中的最大复杂度，'''平均情况复杂度 average-case complexity'''是对所有输入{{mvar|n}}长度中的平均复杂度。一般来说，如果使用“复杂度”一词且不进行进一步说明 ，即考虑最坏情况时间复杂度。
'''最坏情况复杂度 worst-case complexity'''是对所有输入{{mvar|n}}长度中的最大复杂度，'''平均情况复杂度 average-case complexity'''是对所有输入{{mvar|n}}长度中的平均复杂度。一般来说，如果使用“复杂度”一词且不进行进一步说明 ，即考虑最坏情况时间复杂度。
==渐近复杂度==
==渐近复杂度==
通常很难精确计算最坏情况和平均情况复杂度。此外，由于计算机或计算模型的任何变化都会改变复杂度，精确的复杂度值没多少实际意义。更多地，对于较小的{{mvar|n}}值，资源的使用并不是关键。因此对于小 {{mvar|n}}，人们通常更在乎一个算法的简单性和易实现性，而非复杂度。
通常很难精确计算最坏情况和平均情况复杂度。此外，由于计算机或计算模型的任何变化都会改变复杂度，精确的复杂度值没多少实际意义。更多地，对于较小的{{mvar|n}}值，资源的使用并不是关键。因此对于小 {{mvar|n}}，人们通常更在乎一个算法的简单性和易实现性，而非复杂度。
由于这些原因，人们通常把注意力集中在大{{mvar|n}}的复杂度上，即输入规模趋于无穷大的'''渐近行为 asymptotic behavior'''上。因此，复杂度通常用'''大O符号 big O notation'''来表示。
由于这些原因，人们通常把注意力集中在大{{mvar|n}}的复杂度上，即输入规模趋于无穷大的'''渐近行为 asymptotic behavior'''上。因此，复杂度通常用'''大O符号 big O notation'''来表示。
例如，通常整数'''乘法 multiplication'''的复杂度是<math>O(n^2),</math>，这意味着存在一个常数<math>c_u</math>，使得两个最多{{mvar|n}}位的整数乘法可以在小于<math>c_un^2</math>的时间内完成。这个界限是尖锐的，因为最坏情况复杂度和平均情况复杂度是<math>\Omega(n^2),</math>，意味着存在一个常数<math>c_l</math>，使得这些复杂度比<math>c_ln^2</math>大。
==计算模型==
==计算模型==
一个'''确定性模型 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'''。
即使这样的计算模型还不现实，它仍然具有重要的理论意义，主要涉及'''P = NP?''' 问题。如果一个问题可以在确定性图灵机上以'''多项式时间 polynomial time'''求解，则该问题属于 '''P 类问题'''。如果一个问题可以在非确定性机器上以'''多项式时间 polynomial time'''求解，则该问题属于 '''NP 类问题'''。我们知道所有P类问题都属于NP类问题，但是否所有NP类问题也属于P类问题？亦即，是否P类问题和NP类问题是等价的？这就是所谓的 P=NP? 问题
即使这样的计算模型还不现实，它仍然具有重要的理论意义，主要涉及'''P = NP?''' 问题。如果一个问题可以在确定性图灵机上以'''多项式时间 polynomial time'''求解，则该问题属于 '''P 类问题'''。如果一个问题可以在非确定性机器上以'''多项式时间 polynomial time'''求解，则该问题属于 '''NP 类问题'''。我们知道所有P类问题都属于NP类问题，但是否所有NP类问题也属于P类问题？亦即，是否P类问题和NP类问题是等价的？这就是所谓的 P=NP? 问题
如果一个问题属于 NP 问题，且不比其他任何 NP 问题简单，则称该问题为''' NP完全问题 NP-complete'''。许多'''组合 combinatorial'''问题，例如'''背包问题 Knapsack problem'''、'''旅行推销员问题 travelling salesman problem'''和'''布尔可满足性问题 Boolean satisfiability problem'''都是NP完全问题。对于所有这些问题，最著名的算法具有指数复杂度。如果这些问题中的任何一个都可以在确定性机器上在多项式时间内求解，那就意味着所有 NP 问题都可以在多项式时间内求解，我们立即可以得出结论：P = NP。一般认为P类问题和NP类问题是等价的，即所有NP类问题都有在确定性图灵机上以多项式时间解决的方法。现在我们主要的猜想是，NP 问题的最坏情况本质上是难以解决的，即 <math>P \neq NP</math>。
如果一个问题属于 NP 问题，且不比其他任何 NP 问题简单，则称该问题为''' NP完全问题 NP-complete'''。许多'''组合 combinatorial'''问题，例如'''背包问题 Knapsack problem'''、'''旅行推销员问题 travelling salesman problem'''和'''布尔可满足性问题 Boolean satisfiability problem'''都是NP完全问题。对于所有这些问题，最著名的算法具有指数复杂度。如果这些问题中的任何一个都可以在确定性机器上在多项式时间内求解，那就意味着所有 NP 问题都可以在多项式时间内求解，我们立即可以得出结论：P = NP。一般认为P类问题和NP类问题是等价的，即所有NP类问题都有在确定性图灵机上以多项式时间解决的方法。现在我们主要的猜想是，NP 问题的最坏情况本质上是难以解决的，即 <math>P \neq NP</math>。
===并行和分布式计算===
===并行和分布式计算===
并行处理器和分布式计算处理器由同时工作的多个处理器组成。不同模型之间的差异主要体现在处理器之间的信息传输方式上。通常情况下，在并行计算中处理器之间的数据传输非常快，而在分布式计算中，数据传输通过'''网络'''完成，因此速度要慢得多。
并行处理器和分布式计算处理器由同时工作的多个处理器组成。不同模型之间的差异主要体现在处理器之间的信息传输方式上。通常情况下，在并行计算中处理器之间的数据传输非常快，而在分布式计算中，数据传输通过'''网络'''完成，因此速度要慢得多。
在{{mvar|N}}个处理器上进行计算所需的时间至少是单个处理器所需时间的{{mvar|N}}的商。但实际上，这个理论上的最优界限永远不可能达到，由于有些子任务不能并行化，部分处理器不得不先等待另一个处理器的结果。
在{{mvar|N}}个处理器上进行计算所需的时间至少是单个处理器所需时间的{{mvar|N}}的商。但实际上，这个理论上的最优界限永远不可能达到，由于有些子任务不能并行化，部分处理器不得不先等待另一个处理器的结果。
因此，主要的复杂度问题是如何设计算法，使得计算时间与处理器数量的乘积尽可能接近在单个处理器上进行同一计算所需的时间。
因此，主要的复杂度问题是如何设计算法，使得计算时间与处理器数量的乘积尽可能接近在单个处理器上进行同一计算所需的时间。
===量子计算===
===量子计算===
'''量子计算机 quantum computer'''是一种基于'''量子力学 quantum mechanics'''的计算机。'''丘奇-图灵理论 Church–Turing thesis'''适用于量子计算机，也就是说，任何可以由量子计算机解决的问题也可以由图灵机解决。然而，有些问题理论上可以用量子计算机以极低的'''时间复杂度 time complexity解决，而用传统图灵机则无法解决'''。由于没有人知道如何建造一台高效的量子计算机，目前这纯粹只是理论上可行的。
'''量子计算机 quantum computer'''是一种基于'''量子力学 quantum mechanics'''的计算机。'''丘奇-图灵理论 Church–Turing thesis'''适用于量子计算机，也就是说，任何可以由量子计算机解决的问题也可以由图灵机解决。然而，有些问题理论上可以用量子计算机以极低的'''时间复杂度 time complexity解决，而用传统图灵机则无法解决'''。由于没有人知道如何建造一台高效的量子计算机，目前这纯粹只是理论上可行的。
'''量子复杂度理论 Quantum complexity theory'''研究用量子计算机解决的问题的'''复杂度类'''。它主要用于'''后量子密码学 post-quantum cryptography'''，包括设计能抵御量子计算机攻击的'''安全协议 cryptographic protocol'''。
'''量子复杂度理论 Quantum complexity theory'''研究用量子计算机解决的问题的'''复杂度类'''。它主要用于'''后量子密码学 post-quantum cryptography'''，包括设计能抵御量子计算机攻击的'''安全协议 cryptographic protocol'''。
==问题复杂度(下限)==
==问题复杂度(下限)==
问题的复杂度是解决问题算法(包括未知算法)复杂度的'''下确界 infimum，'''即解决这个问题所需的最少时间。因此，问题的复杂度比任何解决该问题的算法的复杂度都要小。
问题的复杂度是解决问题算法(包括未知算法)复杂度的'''下确界 infimum，'''即解决这个问题所需的最少时间。因此，问题的复杂度比任何解决该问题的算法的复杂度都要小。
用'''大O符号 big O notation'''表示的每一个复杂度都是算法的复杂度，也是相应问题的复杂度。
用'''大O符号 big O notation'''表示的每一个复杂度都是算法的复杂度，也是相应问题的复杂度。
获得复杂度下限的标准方法包括将一个问题转化为另一个问题。更准确地说，假设一个大小为{{mvar|n}}的问题{{mvar|A}}可以编码成大小为{{math|''f''(''n'')}}的问题{{mvar|B}}，则问题{{mvar|A}}的复杂度为<math>\Omega(g(n))</math>。不失一般性地，我们可以假设函数{{mvar|f}}随着{{mvar|n}}的增加而增加，并且有一个'''反函数 inverse function'''，那么问题{{mvar|B}}的复杂度就是<math>\Omega(g(h(n)))</math>。这个方法可以用来证明，若'''P ≠ NP'''(一个未解决的猜想) ，对于每个正整数{{mvar|k}}，每个'''NP完全问题 NP-complete problem'''的复杂度都是 <math>\Omega(n^k)</math>。
获得复杂度下限的标准方法包括将一个问题转化为另一个问题。更准确地说，假设一个大小为{{mvar|n}}的问题{{mvar|A}}可以编码成大小为{{math|''f''(''n'')}}的问题{{mvar|B}}，则问题{{mvar|A}}的复杂度为<math>\Omega(g(n))</math>。不失一般性地，我们可以假设函数{{mvar|f}}随着{{mvar|n}}的增加而增加，并且有一个'''反函数 inverse function'''，那么问题{{mvar|B}}的复杂度就是<math>\Omega(g(h(n)))</math>。这个方法可以用来证明，若'''P ≠ NP'''(一个未解决的猜想) ，对于每个正整数{{mvar|k}}，每个'''NP完全问题 NP-complete problem'''的复杂度都是 <math>\Omega(n^k)</math>。
==在算法设计中的应用==
==在算法设计中的应用==
评估算法的复杂度是'''算法设计 algorithm design'''的一个重要组成部分，因为这给出了一个算法关于预期性能的有用信息。
有一个常见的误解，由于'''摩尔定律 Moore's law'''假定了现代计算机功率的'''指数增长 exponential growth'''，对算法复杂度的评估将变得不那么重要。这是错误的，因为这种功率增加同样也会容使得处理较大的输入数据('''大数据 big data''')成为可能。例如，当一个人想要按字母顺序对数百个条目的列表进行排序时，比如一本书的'''参考书目 bibliography'''，任何算法都应该在不到一秒的时间内就能正常工作。另一方面，对于一个包含100万个条目的列表(例如一个大城镇的电话号码) ，需要<math>O(n^2)</math>次比较的基本算法，须进行1万亿次比较运算，即以每秒1000万次的速度进行比较需要大约3个小时。另一方面，'''快速排序 quicksort'''和'''合并排序 merge sort'''只需要<math>n\log_2 n</math>次比较(前者为平均情况复杂度，后者为最坏情况复杂度)。这大约是3000万次比较，以每秒1000万次比较计算，只需要3秒钟。
有一个常见的误解，由于'''摩尔定律 Moore's law'''假定了现代计算机功率的'''指数增长 exponential growth'''，对算法复杂度的评估将变得不那么重要。这是错误的，因为这种功率增加同样也会容使得处理较大的输入数据('''大数据 big data''')成为可能。例如，当一个人想要按字母顺序对数百个条目的列表进行排序时，比如一本书的'''参考书目 bibliography'''，任何算法都应该在不到一秒的时间内就能正常工作。另一方面，对于一个包含100万个条目的列表(例如一个大城镇的电话号码) ，需要<math>O(n^2)</math>次比较的基本算法，须进行1万亿次比较运算，即以每秒1000万次的速度进行比较需要大约3个小时。另一方面，'''快速排序 quicksort'''和'''合并排序 merge sort'''只需要<math>n\log_2 n</math>次比较(前者为平均情况复杂度，后者为最坏情况复杂度)。这大约是3000万次比较，以每秒1000万次比较计算，只需要3秒钟。
因此，对复杂度的评估允许在编程实现之前就消除许多低效率的算法。这也可用于在不用测试所有变量的情况下调优复杂的算法。通过确定复杂算法中最复杂的步骤，对复杂度的研究还可以将重点放在这些步骤上，从而提高实现的效率。
因此，对复杂度的评估允许在编程实现之前就消除许多低效率的算法。这也可用于在不用测试所有变量的情况下调优复杂的算法。通过确定复杂算法中最复杂的步骤，对复杂度的研究还可以将重点放在这些步骤上，从而提高实现的效率。
==更多资料==
==更多资料==
|location=USA
|location=USA
}}
}}