1,068
个编辑
更改
跳到导航
跳到搜索
第18行：
第18行： − − − The study of the complexity of explicitly given algorithms is called [[analysis of algorithms]], while the study of the complexity of [[computational problem|problems]] is called [[computational complexity theory]]. Both areas are highly related, as the complexity of an algorithm is always an [[upper bound]] on the complexity of the problem solved by this algorithm. − − The study of the complexity of explicitly given algorithms is called analysis of algorithms, while the study of the complexity of problems is called computational complexity theory. Both areas are highly related, as the complexity of an algorithm is always an upper bound on the complexity of the problem solved by this algorithm. 第33行：
第28行： − The resource that is most commonly considered is time. When "complexity" is used without qualification, this generally means time complexity. − − The resource that is most commonly considered is time. When "complexity" is used without qualification, this generally means time complexity. − The usual units of time (seconds, minutes etc.) are not used in [[computational complexity theory|complexity theory]] because they are too dependent on the choice of a specific computer and on the evolution of technology. For instance, a computer today can execute an algorithm significantly faster than a computer from the 1960s; however, this is not an intrinsic feature of the algorithm but rather a consequence of technological advances in [[computer hardware]]. Complexity theory seeks to quantify the intrinsic time requirements of algorithms, that is, the basic time constraints an algorithm would place on ''any'' computer. This is achieved by counting the number of ''elementary operations'' that are executed during the computation. These operations are assumed to take constant time (that is, not affected by the size of the input) on a given machine, and are often called ''steps''. − − The usual units of time (seconds, minutes etc.) are not used in complexity theory because they are too dependent on the choice of a specific computer and on the evolution of technology. For instance, a computer today can execute an algorithm significantly faster than a computer from the 1960s; however, this is not an intrinsic feature of the algorithm but rather a consequence of technological advances in computer hardware. Complexity theory seeks to quantify the intrinsic time requirements of algorithms, that is, the basic time constraints an algorithm would place on any computer. This is achieved by counting the number of elementary operations that are executed during the computation. These operations are assumed to take constant time (that is, not affected by the size of the input) on a given machine, and are often called steps. 第47行：
第36行： − − Another important resource is the size of [[computer memory]] that is needed for running algorithms. − − Another important resource is the size of computer memory that is needed for running algorithms. − − The number of [[arithmetic operations]] is another resource that is commonly used. In this case, one talks of '''arithmetic complexity'''. If one knows an [[upper bound]] on the size of the [[binary representation]] of the numbers that occur during a computation, the time complexity is generally the product of the arithmetic complexity by a constant factor. − − The number of arithmetic operations is another resource that is commonly used. In this case, one talks of arithmetic complexity. If one knows an upper bound on the size of the binary representation of the numbers that occur during a computation, the time complexity is generally the product of the arithmetic complexity by a constant factor. 第70行：
第51行： − − − In [[sorting]] and [[search algorithm|searching]], the resource that is generally considered is the number of entries comparisons. This is generally a good measure of the time complexity if data are suitably organized. − − In sorting and searching, the resource that is generally considered is the number of entries comparisons. This is generally a good measure of the time complexity if data are suitably organized. 第81行：
第57行： − + − − For clarity, only time complexity is considered in this section, but everything applies (with slight modifications) to the complexity with respect to other resources. − − 第121行：
第93行： − The evaluation of the complexity relies on the choice of a [[model of computation]], which consists in defining the basic operations that are done in a unit of time. When the model of computation is not explicitly specified, this is generally meant as being [[multitape Turing machine]]. − The evaluation of the complexity relies on the choice of a model of computation, which consists in defining the basic operations that are done in a unit of time. When the model of computation is not explicitly specified, this is generally meant as being multitape Turing machine.+ − 复杂度的评估依赖于'''计算模型 model of computation'''的选择，包括定义在一个时间单位内完成的基本操作。当没有明确指定时，默认使用的计算模型是'''多带图灵机 multitape Turing machine'''。 − A [[deterministic model]] of computation is a model of computation such that the successive states of the machine and the operations to be performed are completely determined by the preceding state. Historically, the first deterministic models were [[μ-recursive function|recursive function]]s, [[lambda calculus]], and [[Turing machine]]s. The model of [[Random access machine]]s (also called RAM-machines) is also widely used, as a closer counterpart to real [[computer]]s. − − A deterministic model of computation is a model of computation such that the successive states of the machine and the operations to be performed are completely determined by the preceding state. Historically, the first deterministic models were recursive functions, lambda calculus, and Turing machines. The model of Random access machines (also called RAM-machines) is also widely used, as a closer counterpart to real computers. − − When the model of computation is not specified, it is generally assumed to be a [[multitape Turing machine]]. For most algorithms, the time complexity is the same on multitape Turing machines as on RAM-machines, although some care may be needed in how data is stored in memory to get this equivalence. − − When the model of computation is not specified, it is generally assumed to be a multitape Turing machine. For most algorithms, the time complexity is the same on multitape Turing machines as on RAM-machines, although some care may be needed in how data is stored in memory to get this equivalence. − In a [[non-deterministic algorithm|non-deterministic model of computation]], such as [[non-deterministic Turing machine]]s, some choices may be done at some steps of the computation. In complexity theory, one considers all possible choices simultaneously, and the non-deterministic time complexity is the time needed, when the best choices are always done. In other words, one considers that the computation is done simultaneously on as many (identical) processors as needed, and the non-deterministic computation time is the time spent by the first processor that finishes the computation. This parallelism is partly amenable to [[quantum computing]] via superposed [[entangled state]]s in running specific [[quantum algorithms]], like e.g. [[Shor's algorithm|Shor's factorization]] of yet only small integers ({{as of|2018|03|lc=yes}}: 21 = 3 × 7). − − In a non-deterministic model of computation, such as non-deterministic Turing machines, some choices may be done at some steps of the computation. In complexity theory, one considers all possible choices simultaneously, and the non-deterministic time complexity is the time needed, when the best choices are always done. In other words, one considers that the computation is done simultaneously on as many (identical) processors as needed, and the non-deterministic computation time is the time spent by the first processor that finishes the computation. This parallelism is partly amenable to quantum computing via superposed entangled states in running specific quantum algorithms, like e.g. Shor's factorization of yet only small integers (: 21 = 3 × 7). 第156行：
第116行： − Parallel and distributed computing consist of splitting computation on several processors, which work simultaneously. The difference between the different model lies mainly in the way of transmitting information between processors. Typically, in parallel computing the data transmission between processors is very fast, while, in distributed computing, the data transmission is done through a [[computer network|network]] and is therefore much slower. − − Parallel and distributed computing consist of splitting computation on several processors, which work simultaneously. The difference between the different model lies mainly in the way of transmitting information between processors. Typically, in parallel computing the data transmission between processors is very fast, while, in distributed computing, the data transmission is done through a network and is therefore much slower. 第167行：
第124行： − − − The main complexity problem is thus to design algorithms such that the product of the computation time by the number of processors is as close as possible to the time needed for the same computation on a single processor. − − The main complexity problem is thus to design algorithms such that the product of the computation time by the number of processors is as close as possible to the time needed for the same computation on a single processor. − A [[quantum computer]] is a computer whose model of computation is based on [[quantum mechanics]]. The [[Church–Turing thesis (complexity theory)|Church–Turing thesis]] applies to quantum computers; that is, every problem that can be solved by a quantum computer can also be solved by a Turing machine. However, some problems may theoretically be solved with a much lower [[time complexity]] using a quantum computer rather than a classical computer. This is, for the moment, purely theoretical, as no one knows how to build an efficient quantum computer. − − A quantum computer is a computer whose model of computation is based on quantum mechanics. The Church–Turing thesis applies to quantum computers; that is, every problem that can be solved by a quantum computer can also be solved by a Turing machine. However, some problems may theoretically be solved with a much lower time complexity using a quantum computer rather than a classical computer. This is, for the moment, purely theoretical, as no one knows how to build an efficient quantum computer. − − [[Quantum complexity theory]] has been developed to study the [[complexity class]]es of problems solved using quantum computers. It is used in [[post-quantum cryptography]], which consists of designing [[cryptographic protocol]]s that are resistant to attacks by quantum computers. − − Quantum complexity theory has been developed to study the complexity classes of problems solved using quantum computers. It is used in post-quantum cryptography, which consists of designing cryptographic protocols that are resistant to attacks by quantum computers. − − − The complexity of a problem is the [[infimum]] of the complexities of the algorithms that may solve the problem, including unknown algorithms. Thus the complexity of a problem is not greater than the complexity of any algorithm that solves the problems. − − The complexity of a problem is the infimum of the complexities of the algorithms that may solve the problem, including unknown algorithms. Thus the complexity of a problem is not greater than the complexity of any algorithm that solves the problems. − − It follows that every complexity that is expressed with [[big O notation]] is a complexity of the algorithm as well as of the corresponding problem. − − It follows that every complexity that is expressed with big O notation is a complexity of the algorithm as well as of the corresponding problem. − On the other hand, it is generally hard to obtain nontrivial lower bounds for problem complexity, and there are few methods for obtaining such lower bounds. − − On the other hand, it is generally hard to obtain nontrivial lower bounds for problem complexity, and there are few methods for obtaining such lower bounds. 第214行：
第147行： − 第232行：
第164行： − − Evaluating the complexity of an algorithm is an important part of [[algorithm design]], as this gives useful information on the performance that may be expected. − − Evaluating the complexity of an algorithm is an important part of algorithm design, as this gives useful information on the performance that may be expected. 第244行：
第172行： − − Thus the evaluation of the complexity may allow eliminating many inefficient algorithms before any implementation. This may also be used for tuning complex algorithms without testing all variants. By determining the most costly steps of a complex algorithm, the study of complexity allows also focusing on these steps the effort for improving the efficiency of an implementation. − − Thus the evaluation of the complexity may allow eliminating many inefficient algorithms before any implementation. This may also be used for tuning complex algorithms without testing all variants. By determining the most costly steps of a complex algorithm, the study of complexity allows also focusing on these steps the effort for improving the efficiency of an implementation.
无编辑摘要
由于运行一个算法所需的资源量通常随输入规模的大小而变化，因此复杂度通常用函数{{math| ''f''(''n'')}}表示，其中{{math|''n''}}是输入量的大小，{{math|''f''(''n'')}}是'''最坏情况复杂度 worst-case complexity'''(输入大小为 {{math|''n''}}时所需的资源量的最大值) ，或是'''平均情况复杂度 average-case complexity'''(资源总量相对于{{math|''n''}}的所有占用的平均值)。'''时间复杂度 Time complexity'''通常表示为对一个输入值长度所需基本操作（通常是加法操作或者乘法操作）的数量。我们假设基本操作在一台计算机上只占用一个不变的时间量（比如1纳秒），而在另一台计算机上运行时，只根据一个常量因子进行改变（比如k*1纳秒）。'''空间复杂度 space complexity'''通常表示为算法对一个输入值长度所需的内存量。
由于运行一个算法所需的资源量通常随输入规模的大小而变化，因此复杂度通常用函数{{math| ''f''(''n'')}}表示，其中{{math|''n''}}是输入量的大小，{{math|''f''(''n'')}}是'''最坏情况复杂度 worst-case complexity'''(输入大小为 {{math|''n''}}时所需的资源量的最大值) ，或是'''平均情况复杂度 average-case complexity'''(资源总量相对于{{math|''n''}}的所有占用的平均值)。'''时间复杂度 Time complexity'''通常表示为对一个输入值长度所需基本操作（通常是加法操作或者乘法操作）的数量。我们假设基本操作在一台计算机上只占用一个不变的时间量（比如1纳秒），而在另一台计算机上运行时，只根据一个常量因子进行改变（比如k*1纳秒）。'''空间复杂度 space complexity'''通常表示为算法对一个输入值长度所需的内存量。
对一个有明确定义的算法的复杂度进行的研究叫做'''算法分析 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>。
===时间===
===时间===
最常被考虑的资源是时间。当没有明确说明时，“复杂度”通常意味着时间复杂度而非空间复杂度。
最常被考虑的资源是时间。当没有明确说明时，“复杂度”通常意味着时间复杂度而非空间复杂度。
在'''复杂度理论 complexity theory'''中不使用通常的时间单位(秒、分等)，因为它们过于依赖于特定计算机的选择和技术的演变。例如，今天的计算机执行算法的速度明显快于20世纪60年代的计算机; 然而，这不是算法的固有特征，而是计算机硬件技术进步的结果。复杂度理论旨在量化算法的内在时间需求，也就是算法对任何计算机的基本时间约束。这是通过统计在计算过程中执行的基本操作数量来实现的。这些基本操作假定在给定的机器上占用常量时间(即不受输入大小的影响) ，通常被称为步骤。
在'''复杂度理论 complexity theory'''中不使用通常的时间单位(秒、分等)，因为它们过于依赖于特定计算机的选择和技术的演变。例如，今天的计算机执行算法的速度明显快于20世纪60年代的计算机; 然而，这不是算法的固有特征，而是计算机硬件技术进步的结果。复杂度理论旨在量化算法的内在时间需求，也就是算法对任何计算机的基本时间约束。这是通过统计在计算过程中执行的基本操作数量来实现的。这些基本操作假定在给定的机器上占用常量时间(即不受输入大小的影响) ，通常被称为步骤。
===空间===
===空间===
另一个重要的资源是运行算法所需的'''计算机内存 computer memory'''大小。
另一个重要的资源是运行算法所需的'''计算机内存 computer memory'''大小。
===其他===
===其他===
'''算术运算 arithmetic operations'''的数量是另一种常用的资源。在这种情况下，人们会谈到'''算术复杂度'''。如果已知一个计算过程中出现的数的'''二进制表示 binary representation'''长度的'''上限 upper bound'''，时间复杂度通常是该算术复杂度乘以一个常数因子。
'''算术运算 arithmetic operations'''的数量是另一种常用的资源。在这种情况下，人们会谈到'''算术复杂度'''。如果已知一个计算过程中出现的数的'''二进制表示 binary representation'''长度的'''上限 upper bound'''，时间复杂度通常是该算术复杂度乘以一个常数因子。
对于许多算法，在计算过程中使用的整数大小是没有界限的，并且考虑算术运算占用一个常量时间是不现实的。因此，时间复杂度，在此上下文中通常称为 '''位复杂度 bit complexity'''，可能远远大于算术复杂度。例如，根据通常的算法 '''高斯消去法 Gaussian elimination''' 计算一个{{math|''n''×''n''}} 整数矩阵行列式 的算术复杂度是<math>O(n^3)</math>。因为系数的大小可能在计算过程中呈指数增长，相同算法的位复杂度是指数级的。另一方面，如果这些算法与多模运算相结合，位复杂度可以降低到[[soft O notation|{{math|''O''<sup>~</sup>(''n''<sup>4</sup>)}}]]。
对于许多算法，在计算过程中使用的整数大小是没有界限的，并且考虑算术运算占用一个常量时间是不现实的。因此，时间复杂度，在此上下文中通常称为 '''位复杂度 bit complexity'''，可能远远大于算术复杂度。例如，根据通常的算法 '''高斯消去法 Gaussian elimination''' 计算一个{{math|''n''×''n''}} 整数矩阵行列式 的算术复杂度是<math>O(n^3)</math>。因为系数的大小可能在计算过程中呈指数增长，相同算法的位复杂度是指数级的。另一方面，如果这些算法与多模运算相结合，位复杂度可以降低到[[soft O notation|{{math|''O''<sup>~</sup>(''n''<sup>4</sup>)}}]]。
在'''排序 sorting'''和'''搜索 searching'''中，通常考虑的资源是需要做几次''比较大小''。如果数据组织得当，这通常是一个很好的时间复杂度测量方法。
在'''排序 sorting'''和'''搜索 searching'''中，通常考虑的资源是需要做几次''比较大小''。如果数据组织得当，这通常是一个很好的时间复杂度测量方法。
复杂度作为关于输入长度的函数
复杂度作为关于输入长度的函数
:''For clarity, only time complexity is considered in this section, but everything applies (with slight modifications) to the complexity with respect to other resources.''
:''为了清晰起见，本节只考虑时间复杂度，不过所有内容(稍加修改)也都适用于其他资源的复杂度。''
为了清晰起见，本节只考虑时间复杂度，不过所有内容(稍加修改)也都适用于其他资源的复杂度。
It is impossible to count the number of steps of an algorithm on all possible inputs. As the complexity generally increases with the size of the input, the complexity is typically expressed as a function of the size {{math|''n''}} (in [[bit]]s) of the input, and therefore, the complexity is a function of {{math|''n''}}. However, the complexity of an algorithm may vary dramatically for different inputs of the same size. Therefore, several complexity functions are commonly used.
It is impossible to count the number of steps of an algorithm on all possible inputs. As the complexity generally increases with the size of the input, the complexity is typically expressed as a function of the size {{math|''n''}} (in [[bit]]s) of the input, and therefore, the complexity is a function of {{math|''n''}}. However, the complexity of an algorithm may vary dramatically for different inputs of the same size. Therefore, several complexity functions are commonly used.
==计算模型==
==计算模型==
复杂度的评估依赖于'''计算模型 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'''。
===并行和分布式计算===
===并行和分布式计算===
并行处理器和分布式计算处理器由同时工作的多个处理器组成。不同模型之间的差异主要体现在处理器之间的信息传输方式上。通常情况下，在并行计算中处理器之间的数据传输非常快，而在分布式计算中，数据传输通过'''网络'''完成，因此速度要慢得多。
并行处理器和分布式计算处理器由同时工作的多个处理器组成。不同模型之间的差异主要体现在处理器之间的信息传输方式上。通常情况下，在并行计算中处理器之间的数据传输非常快，而在分布式计算中，数据传输通过'''网络'''完成，因此速度要慢得多。
在{{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'''表示的每一个复杂度都是算法的复杂度，也是相应问题的复杂度。
另一方面，问题复杂度的非平凡（nontrivial）下界一般难以获得，并且获得这种下界的方法很少。
另一方面，问题复杂度的非平凡（nontrivial）下界一般难以获得，并且获得这种下界的方法很少。
为了解决大多数问题，往往需要与数据大小成比例的时间来读取所有输入数据。因此，这些问题的复杂度至少是'''线性的 linear'''，使用'''大欧米茄符号 big omega notation'''，记为复杂度<math>\Omega(n).</math>
为了解决大多数问题，往往需要与数据大小成比例的时间来读取所有输入数据。因此，这些问题的复杂度至少是'''线性的 linear'''，使用'''大欧米茄符号 big omega notation'''，记为复杂度<math>\Omega(n).</math>
==在算法设计中的应用==
==在算法设计中的应用==
评估算法的复杂度是'''算法设计 algorithm design'''的一个重要组成部分，因为这给出了一个算法关于预期性能的有用信息。
评估算法的复杂度是'''算法设计 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秒钟。
因此，对复杂度的评估允许在编程实现之前就消除许多低效率的算法。这也可用于在不用测试所有变量的情况下调优复杂的算法。通过确定复杂算法中最复杂的步骤，对复杂度的研究还可以将重点放在这些步骤上，从而提高实现的效率。
因此，对复杂度的评估允许在编程实现之前就消除许多低效率的算法。这也可用于在不用测试所有变量的情况下调优复杂的算法。通过确定复杂算法中最复杂的步骤，对复杂度的研究还可以将重点放在这些步骤上，从而提高实现的效率。