哪些排序算法的时间复杂度为Θ(N)？Θ复杂度符号相关疑问

1. 时间复杂度为Θ(N)的排序算法 #

所有线性时间复杂度的排序算法均为非比较排序，比较类排序的时间复杂度下界为Ω(N log N)，不可能达到Θ(N)。常见的线性时间排序包括：

• 计数排序：仅适用于元素取值范围有限的场景，当取值范围大小K和N同阶或为常数时，整体复杂度为Θ(N+K) ≈ Θ(N)
• 基数排序：基于逐位稳定排序实现，当排序轮次d为常数时，复杂度为Θ(d*N) ≈ Θ(N)
• 桶排序：仅适用于输入数据均匀分布的场景，每个桶内元素数量为常数级时，平均时间复杂度为Θ(N)

2. 复杂度符号Θ的含义 #

Θ不专门表示最坏时间复杂度，它是渐近紧确界符号：
如果一个算法的复杂度标记为Θ(f(N))，代表当数据规模N足够大时，该算法的实际运行时间同时以c1f(N)为上界、c2f(N)为下界（c1、c2为正的常数）。
Θ可以用来描述任意场景下的复杂度紧确界：包括最好时间复杂度、平均时间复杂度、最坏时间复杂度。我们常说的最坏时间复杂度通常用O（渐近上界）来表示，仅当最坏场景下上下界同阶时，才会用Θ来描述最坏复杂度。

3. 线性搜索的分类说明 #

你的判断是正确的：线性搜索属于查找类算法，核心能力是在序列中定位目标元素，不属于用来将无序序列调整为有序状态的排序算法范畴，因此不计入线性时间排序的统计中。

内容的提问来源于stack exchange，提问作者sober