algorithm - 为什么对固定长度的数组(例如只有五个元素的数组)进行排序的成本为 O(1)？

Question

据我了解，当n固定时，对n个元素进行排序的成本是O(1)。

例如，在线性时间中值查找算法的解释中，它说:

# Next, we sort each chunk. Each group is a fixed length, so each sort
# takes constant time. Since we have n/5 chunks, this operation
# is also O(n)

https://rcoh.me/posts/linear-time-median-finding/

我不明白为什么。我是否应该想象有一个函数涵盖所有可能的 5!元素如何定位的组合？

Answer 1

大 O 符号用于描述运行时间或空间如何随着输入的增长而增长。如果您要排序的事物的数量没有随着输入的增长而增长，那么您正在评估的算法的排序步骤就是 O(1)。

示例:假设您的输入是一个长度为 n >= 10 的数组，而您的输出是同一个数组，但前 10 个元素按排序顺序排列，其余元素不变。然后，由于您花在排序上的时间不会随着输入的增长(随着 n 变大)而增长，因此排序步骤为 O(1)。