排序算法分析

Analysis of Time Complexity of Comparison-Based Sorting Algorithms

基于比较的排序算法的时间复杂度分析

英文版

Introduction

Comparison-based sorting algorithms are fundamental in computer science. These algorithms determine the order of elements by comparing them, which has implications on the time complexity of these algorithms. This cheat sheet provides a detailed derivation of the time complexity for comparison-based sorting algorithms.

Definitions

• Comparison-Based Sorting: Sorting algorithms that determine the order of elements solely by comparing pairs of elements.
• Time Complexity: The computational complexity that describes the amount of time it takes to run an algorithm as a function of the length of the input.

Key Points

1. Decision Tree Model: A useful model for understanding the time complexity of comparison-based sorting algorithms is the decision tree model. Each internal node represents a comparison, and each leaf represents a possible permutation of the input.

2. Height of the Decision Tree: The height of the decision tree gives the number of comparisons in the worst case. For $n$ elements, there are $n!$ permutations, so the decision tree must have at least $n!$ leaves.

Derivation

1. Number of Comparisons:

   • The number of leaves in the decision tree for sorting $n$ elements is $n!$.
   • The height $h$ of a binary tree with $L$ leaves is at least ${\log }_{2}L$. Hence, $h\ge {\log }_2(n!)$.

2. Stirling’s Approximation:

   • Using Stirling’s approximation, $n!\approx \sqrt{2\pi n}{\left(\frac{n}{e}\right)}^n$.
   • Taking the logarithm: ${\log }_2(n!)\approx {\log }_2(\sqrt{2\pi n})+n{\log }_2\left(\frac{n}{e}\right)$.
   • Simplifying, ${\log }_2(n!)\approx \frac{1}{2}{\log }_2(2\pi n)+n{\log }_{2}n-n{\log }_{2}e$.

3. Simplified Complexity:

   • The dominant term is $n{\log }_{2}n$.
   • Therefore, ${\log }_2(n!)=\Theta (n{\log }_{2}n)$.

Conclusion

The height of the decision tree, and hence the worst-case time complexity for any comparison-based sorting algorithm, is $\mathbf{O}(n{\log }_{2}n)$. This establishes the lower bound for comparison-based sorting algorithms.

中文版

介绍

基于比较的排序算法是计算机科学中的基础算法。这些算法通过比较元素来确定它们的顺序，这对算法的时间复杂度有重要影响。本备忘单详细推导了基于比较的排序算法的时间复杂度。

定义

• 基于比较的排序: 仅通过比较元素对来确定元素顺序的排序算法。
• 时间复杂度: 描述算法运行时间随输入长度变化的计算复杂度。

关键点

1. 决策树模型: 理解基于比较的排序算法时间复杂度的有用模型是决策树模型。每个内部节点代表一次比较，每个叶子节点代表输入的一种可能排列。

2. 决策树的高度: 决策树的高度给出了最坏情况下的比较次数。对于 $n$ 个元素，有 $n!$ 种排列，因此决策树至少有 $n!$ 个叶子。

推导

1. 比较次数:

   • 对于排序 $n$ 个元素的决策树，其叶子数为 $n!$。
   • 二叉树中有 $L$ 个叶子的高度 $h$ 至少为 ${\log }_{2}L$。因此，$h\ge {\log }_2(n!)$。

2. 斯特林近似:

   • 使用斯特林近似，$n!\approx \sqrt{2\pi n}{\left(\frac{n}{e}\right)}^n$。
   • 取对数：${\log }_2(n!)\approx {\log }_2(\sqrt{2\pi n})+n{\log }_2\left(\frac{n}{e}\right)$。
   • 简化，${\log }_2(n!)\approx \frac{1}{2}{\log }_2(2\pi n)+n{\log }_{2}n-n{\log }_{2}e$。

3. 简化复杂度:

   • 主导项是 $n{\log }_{2}n$。
   • 因此，${\log }_2(n!)=\Theta (n{\log }_{2}n)$。

结论

决策树的高度，因此任何基于比较的排序算法的最坏情况下的时间复杂度是 $\mathbf{O}(n{\log }_{2}n)$。这确立了基于比较的排序算法的下界。