1,068
个编辑
更改
无编辑摘要
在'''计算机科学 computer science'''中，一个'''算法 algorithm'''的'''计算复杂度'''或简单的'''复杂度'''就是运行这个算法所需要的资源量，特别是'''时间'''（CPU占用时间）和'''空间'''（内存占用空间）需求。
在'''计算机科学 computer science'''中，一个'''算法 algorithm'''的'''计算复杂度'''或简单的'''复杂度'''就是运行这个算法所需要的资源量，特别是'''时间'''（CPU占用时间）和'''空间'''（内存占用空间）需求。
由于运行一个算法所需的资源量通常随输入规模的大小而变化，因此复杂度通常用函数{{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'''分析。举个例子，怎样把一串数字从小到大进行排序，是一个问题；而针对这一问题，我们有多种明确定义的算法，如选择排序，归并排序等。假设我们有<math>n</math>个数字，那么排序问题的复杂度就是<math>nlogn</math>，而选择排序的复杂度是<math>n^2</math>，归并排序的复杂度是<math>6nlogn</math>。
这两个领域是高度相关的，因为算法的复杂度一直是该算法所求解问题复杂度的'''上限 upper bound'''。
这两个领域是高度相关的，因为算法的复杂度一直是该算法所求解问题复杂度的'''上限 upper bound'''。
For many algorithms the size of the integers that are used during a computation is not bounded, and it is not realistic to consider that arithmetic operations take a constant time. Therefore, the time complexity, generally called bit complexity in this context, may be much larger than the arithmetic complexity. For example, the arithmetic complexity of the computation of the determinant of a integer matrix is <math>O(n^3)</math> for the usual algorithms (Gaussian elimination). The bit complexity of the same algorithms is exponential in , because the size of the coefficients may grow exponentially during the computation. On the other hand, if these algorithms are coupled with multi-modular arithmetic, the bit complexity may be reduced to soft O notation|.
For many algorithms the size of the integers that are used during a computation is not bounded, and it is not realistic to consider that arithmetic operations take a constant time. Therefore, the time complexity, generally called bit complexity in this context, may be much larger than the arithmetic complexity. For example, the arithmetic complexity of the computation of the determinant of a integer matrix is <math>O(n^3)</math> for the usual algorithms (Gaussian elimination). The bit complexity of the same algorithms is exponential in , because the size of the coefficients may grow exponentially during the computation. On the other hand, if these algorithms are coupled with multi-modular arithmetic, the bit complexity may be reduced to soft O notation|.
对于许多算法，在计算过程中使用的整数大小是没有界限的，并且考虑算术运算占用一个常量时间是不现实的。因此，时间复杂度，在此上下文中通常称为 '''位复杂度 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>)}}。