天真的是O(n).有一个是O(log n)还是O(1)？
排序数组怎么样？如何使用二叉搜索树？
我的数组有一个大小n = [2 ^(h + 1)] - 1？// h =完整二叉树的高度
无序
如果数组是没有排序,那么你可以做不超过O(n)的更好.证明:假设您没有查看数组中的每个元素,那么攻击者就可以使其中一个元素看起来不大于或小于给定数字,以使您的计数不正确.所以,优于O(n)是不可能的.
排序
如果对数组进行排序,则可以通过定位大于或等于给定数字的第一个元素,然后从数组大小中减去该索引来确定O(log n)时间内的结果.