c - 快速计算数组中较小/相等/较大元素的方法

Question

我需要优化我的算法以计算数组(未排序)中比给定数字更大/更小/相等的数字。

我必须多次执行此操作，并且给定的数组也可以包含数千个元素。

数组不变，数字在变

例子:

数组:1,2,3,4,5

n = 3

• <数量:2
• 数量>:2
• 数量 ==:1

第一个想法:

遍历数组并检查元素是否大于 n 或 < 或 ==。 O(n*k)

可能的优化:

O((n+k) * logn)

首先对数组进行排序(我使用 c qsort)，然后使用二进制搜索找到相等的数字，然后以某种方式计算较小和较大的值。但是该怎么做呢？

如果元素存在(bsearch 返回指向该元素的指针)我还需要检查数组是否包含此元素的可能重复项(因此我需要检查此元素之前和之后是否等于找到的元素)，然后使用一些指针操作来计算更大和更小的值。 如何通过指向相等元素的指针获得更大/更小的值？ 但是，如果找不到值(bsearch 返回 null)怎么办？

Answer 1

如果数组是未排序的，并且其中的数字没有其他有用的属性，则没有办法击败 O(n) 遍历数组一次并计算三个桶中的项目的方法。

假设您使用时间线性的排序算法(例如基数排序)，对数组进行排序后进行二分查找不会比 O(n) 更好。对于基于比较的排序，例如快速排序，时间会增加到 O(n*log₂n)。

另一方面，如果您需要针对同一组数字运行多个查询，则排序会有所帮助。针对 n 个数字的 k 个查询的时间将从 O(n*k) 到 O(n+k*log₂n) 假设线性时间排序，或 O((n+k)*log₂n) 与基于比较的排序。如果 k 足够大，平均查询时间会下降。