S.D*_*S.D 4 sorting algorithm big-o
据我所知,当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的功能!元素如何定位的组合？
Big O表示法用于描述输入增长时运行时间或空间如何增长.如果您排序的事物数量没有随着输入的增长而增长,那么您正在评估的算法的排序步骤是O(1).
示例:假设您的输入是一个长度数组n >= 10,并且您的输出是相同的数组,但前10个元素按排序顺序,其余元素保持不变.然后,因为排序时间不会随着输入的增长而增长(随着n变大),排序步骤为O(1).