更改

The best, worst and average case complexity refer to three different ways of measuring the time complexity (or any other complexity measure) of different inputs of the same size. Since some inputs of size n may be faster to solve than others, we define the following complexities:

The best, worst and average case complexity refer to three different ways of measuring the time complexity (or any other complexity measure) of different inputs of the same size. Since some inputs of size n may be faster to solve than others, we define the following complexities:

最佳、最差和平均情况复杂度是指三种不同的方法来度量相同大小的不同输入的时间复杂度(或任何其他复杂度度量)。由于一些 n 大小的输入可能比其他的更快解决，我们定义了以下复杂性:

'''<font color="#ff8000"> 最佳、最差和平均情况复杂度</font>'''是指三种不同的方法来度量相同大小的不同输入的时间复杂度(或任何其他复杂度度量)。由于一些 n 大小的输入可能比其他的更快解决，我们定义了以下复杂性:

#Best-case complexity: This is the complexity of solving the problem for the best input of size ''n''.

#Best-case complexity: This is the complexity of solving the problem for the best input of size ''n''.

Best-case complexity: This is the complexity of solving the problem for the best input of size n.

Best-case complexity: This is the complexity of solving the problem for the best input of size n.

最佳情况复杂性: 这是解决问题的复杂性，最佳输入的大小 n。

'''<font color="#ff8000"> 最佳情况复杂性Best-case complexity</font>''': 这就是解决n大小的最佳输入问题的复杂性。

#Average-case complexity: This is the complexity of solving the problem on an average. This complexity is only defined with respect to a [[probability distribution]] over the inputs. For instance, if all inputs of the same size are assumed to be equally likely to appear, the average case complexity can be defined with respect to the uniform distribution over all inputs of size ''n''.

#Average-case complexity: This is the complexity of solving the problem on an average. This complexity is only defined with respect to a [[probability distribution]] over the inputs. For instance, if all inputs of the same size are assumed to be equally likely to appear, the average case complexity can be defined with respect to the uniform distribution over all inputs of size ''n''.

Average-case complexity: This is the complexity of solving the problem on an average. This complexity is only defined with respect to a probability distribution over the inputs. For instance, if all inputs of the same size are assumed to be equally likely to appear, the average case complexity can be defined with respect to the uniform distribution over all inputs of size n.

Average-case complexity: This is the complexity of solving the problem on an average. This complexity is only defined with respect to a probability distribution over the inputs. For instance, if all inputs of the same size are assumed to be equally likely to appear, the average case complexity can be defined with respect to the uniform distribution over all inputs of size n.

平均案例复杂度: 这是解决问题的平均复杂度。这种复杂性仅仅定义在输入的概率分布上。例如，如果假定所有相同大小的输入出现的可能性相等，则可以根据大小 n 的所有输入的均匀分布来定义平均案例复杂度。

'''<font color="#ff8000"> 平均案例复杂度Average-case complexity</font>''': 这是解决问题的平均复杂度。这种复杂性仅仅定义在输入的概率分布上。例如，如果假定所有相同大小的输入出现的可能性相等，则可以根据大小 n 的所有输入的均匀分布来定义平均案例复杂度。

#[[Amortized analysis]]: Amortized analysis considers both the costly and less costly operations together over the whole series of operations of the algorithm.

#[[Amortized analysis]]: Amortized analysis considers both the costly and less costly operations together over the whole series of operations of the algorithm.

Amortized analysis: Amortized analysis considers both the costly and less costly operations together over the whole series of operations of the algorithm.

Amortized analysis: Amortized analysis considers both the costly and less costly operations together over the whole series of operations of the algorithm.

平摊分析算法: 在算法的整个系列操作中，平摊分析算法同时考虑了成本较高和成本较低的操作。

'''<font color="#ff8000"> 平摊分析Amortized analysis</font>''': 在算法的整个系列操作中，平摊分析同时考虑了成本较高和成本较低的操作。

#Worst-case complexity: This is the complexity of solving the problem for the worst input of size ''n''.

#Worst-case complexity: This is the complexity of solving the problem for the worst input of size ''n''.

Worst-case complexity: This is the complexity of solving the problem for the worst input of size n.

Worst-case complexity: This is the complexity of solving the problem for the worst input of size n.

最坏情况复杂度: 这是解决大小 n 的最坏输入问题的复杂度。

'''<font color="#ff8000"> 最坏情况复杂度Worst-case complexity</font>''': 这是解决大小 n 的最坏输入问题的复杂度。

The order from cheap to costly is: Best, average (of [[discrete uniform distribution]]), amortized, worst.

The order from cheap to costly is: Best, average (of [[discrete uniform distribution]]), amortized, worst.

The order from cheap to costly is: Best, average (of discrete uniform distribution), amortized, worst.

The order from cheap to costly is: Best, average (of discrete uniform distribution), amortized, worst.

 

For example, consider the deterministic sorting algorithm quicksort. This solves the problem of sorting a list of integers that is given as the input. The worst-case is when the pivot is always the largest or smallest value in the list (so the list is never divided). In this case the algorithm takes time O(n²). If we assume that all possible permutations of the input list are equally likely, the average time taken for sorting is O(n log n). The best case occurs when each pivoting divides the list in half, also needing O(n log n) time.

For example, consider the deterministic sorting algorithm quicksort. This solves the problem of sorting a list of integers that is given as the input. The worst-case is when the pivot is always the largest or smallest value in the list (so the list is never divided). In this case the algorithm takes time O(n²). If we assume that all possible permutations of the input list are equally likely, the average time taken for sorting is O(n log n). The best case occurs when each pivoting divides the list in half, also needing O(n log n) time.

例如，考虑确定性排序算法快速排序。这解决了对作为输入的整数列表进行排序的问题。最坏的情况是，pivot 总是列表中最大或最小的值(因此列表从不被除)。在这种情况下，算法需要时间 o (n < sup > 2 </sup >)。如果我们假设输入列表的所有可能排列都是相等的，那么排序所需的平均时间是 o (n log n)。最好的情况发生在每个旋转将列表分为两部分时，也需要 o (n log n)时间。

例如，考虑确定性排序算法'''<font color="#ff8000"> 快速排序Quicksort</font>'''。这解决了对作为输入的整数列表进行排序的问题。最坏的情况是轴总是列表中的最大值或最小值（因此列表永远不会被拆分）。在这种情况下，算法需要时间O(n²)。如果我们假设输入列表的所有可能的排列都是相同的，那么排序所花费的平均时间是O(n log n)。最好的情况发生在每次旋转将列表分成两半时，也需要O(n log n)时间。

 

 

===Upper and lower bounds on the complexity of problems问题复杂性的上下界===

===Upper and lower bounds on the complexity of problems问题复杂性的上下界===