我需要优化我的算法来计算数组（未排序）中的大/小/相等数字，而不是给定数字 .
我必须做很多次，并且给定数组也可以有数千个元素 .
数组不会改变，数字也在变化
例：
数组：1,2,3,4,5
n = 3
-
<：2的数量
-
的数量：2
-
= =的数量：1
First thought:
遍历数组并检查元素是否>或<或==而不是n . O(n*k)
可能的优化：
O((n+k) * logn)
首先对数组进行排序（即使用c qsort），然后使用二进制搜索找到相等的数字，然后以某种方式计算越来越小的值 . 但是怎么做呢？
如果元素存在（bsearch返回指向元素的指针），我还需要检查数组是否包含这些元素的可能重复（所以我需要在这些元素之前和之后检查它们等于找到的元素），然后使用一些指针操作计算越来越大的值 . 如何使用指向相同元素的指针获得更大/更小的值的数量？但是，如果我找不到值（bsearch返回null）该怎么办？
2 回答
如果数组未排序，并且其中的数字没有其他有用的属性，则无法击败一次行走数组的O（n）方法，并计算三个存储桶中的项目 .
假设您使用的是时间上线性的排序算法（例如基数排序），对数组进行排序后接二进制搜索并不比O（n）好 . 对于基于比较的排序，例如快速排序，时间将增加到O（n
*log2n） .另一方面，如果您需要针对同一组数字运行多个查询，则排序将有所帮助 . 针对n个数的k个查询的定时将从O（n
*k）进行k个线性搜索，假设为线性时间排序，或O（（n k）*log2n），具有基于比较的排序 . 给定足够大的k，平均查询时间将减少 .a . ）实现自己的bsearch版本（无论如何都会减少代码）
你可以使用索引与指针进行内联
您不需要指向专用函数的函数指针
b . ）因为你说你想要计算匹配数，你暗示数组可以包含多个具有相同值的条目（否则你将使用布尔值has_n） .
这意味着你需要对"n"数组的开头和结尾进行线性搜索 .
您可以从中计算小于n且大于n的数字 .
看来你有一些不成文的算法来选择这些（对于n = 3，你要找的值大于2且等于1的数量，所以没有办法给出具体的代码）
c . ）为了进一步优化（以内存为代价），您可以将数据排序到结构的二叉搜索树中，该结构不仅包含值，还包含每个值之前和之后的计数和值的数量 . 如果你有很多重复值，它可能根本不会使用更多的内存，但没有数据集就很难分辨 .