确定一个值是否在有序数组中的 O 时间是多少?
我有一个包含 5000 个整数的排序数组。 我能多快判断一个随机整数是否是数组的成员? 一般来说,C 和 Ruby 会很好。
数组值的形式
c * c + 1
为 c
可以是 1 到 5000 之间的任何整数。
例如:
[2, 5, 10, 17, 26, 37, 50 ...]
I have a sorted array of 5000 integers. How fast can I tell if a random integer is a member of the array? An answer in general, C and Ruby would be nice.
The array values are of the form
c * c + 1
where c
can be any integer from 1 to 5000.
For example:
[2, 5, 10, 17, 26, 37, 50 ...]
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(9)
log(n) 在 c 上进行二分查找
log(n) for binary search on c
我会说它是 O(const)! :)
给定一个随机数 r,检查它是否是一个可以用 (n*n+1) 形式表示的数字很简单。 只需检查 sqrt(r-1) 是否为整数即可!
(嗯,它可能比这更复杂一点,因为您的编程语言可能会在处理整数与浮点数时引入一些复杂性,但仍然:您根本不需要搜索数组:只需检查该数字是否在这种特殊的形式。)
I would say it's O(const)! :)
Given a random number r, it's trivial to check whether it's a number that could be represented in the form (n*n+1). Just check whether the sqrt(r-1) is an integer or not!
(Well, it might be a little more complicated than that since your programming language can introduce some complexity into dealing with integers vs floating point numbers, but still: you do not need to search the array at all: just check whether the number is in this particular form.)
正如其他人提到的,二分搜索是 O(log2N),并且可以递归地编码:
或迭代地编码:
但是,如果您正在寻找尽可能最快的方法,您可以根据
设置一个查找表>sqrt(N-1)
您的数字。 只需 5,000 个字的内存,您就可以通过这种方式实现 O(1) 查找。解释:
由于所有数字的形式都是 N^2 + 1(对于从 1 到 N 的整数 N),因此您可以创建一个包含 N 个元素的表。 位置 i 处的元素将指定 i^2 + 1 是否在数组中。 该表可以用长度为 N 的简单数组来实现。构建需要 O(N) 和 N 个字的空间。 但是一旦有了表,所有查找都是 O(1) 的。
示例:
这是 Python 中的示例代码,一如既往地读起来像伪代码 :-)
构建表最多需要 O(N),而查找则为 O(1)。
Binary search, as others have mentioned, is O(log2N), and can be coded either recursively:
or iteratively:
However, if you're looking for the fastest possible way, you can set up a look up table based on the
sqrt(N-1)
of your numbers. With just 5,000 words of memory you can achieve O(1) lookups this way.Explanation:
Since all your numbers are of the form N^2 + 1 for an integer N from 1 to N, you can create a table of N elements. The element at position i will specify if i^2 + 1 is in your array or not. The table can be implemented with a simple array of length N. It will take O(N) to build, and N words of space. But once you have the table, all lookups are O(1).
Example:
Here's sample code in Python, which reads like pseudocode, as always :-)
Building the table takes up O(N) at most, and lookups are O(1).
从技术上讲,在固定大小的数组中查找元素的复杂性是恒定的,因为 log2 5000 不会改变。
Technically, the complexity of finding an element in a fixed-size array is constant, since log2 5000 isn't going to change.
二分查找的时间复杂度为 O(log n)
WikiPedia
Binary Search is O(log n)
WikiPedia
如果数组有 n 个元素,则 O(log n)
O(log n) if the array has n elements
扩展一下:它是 lg n 次测试,即 log2 n。 这使得它O(log n)。 为什么? 因为二分查找的每次尝试都会将数组分成两半; 因此需要 lg n 次试验。
Just to expand on that: it's lg n tests, that is log2 n. That makes it O(log n). Why? because each trial of a binary search divides the array in half; thus it takes lg n trials.
使用二分搜索时,搜索时间为 Log(N)。
Using a binary search, it's Log(N) search time.
在 Perl 中:
我会将这些值加载到静态哈希中,然后它的复杂度将是 O(1)。
构建查找哈希
lookup_hash{$_} = 1 foreach (@original_array);
查找语法
($lookup_hash{$lookup_value}) && print "在 O(1) 中找到它 - 这里没有循环\n";
In Perl:
I would load the values into a static hash and then it would be O(1).
Build the Lookup hash
lookup_hash{$_} = 1 foreach (@original_array);
Lookup syntax
($lookup_hash{$lookup_value}) && print "Found it in O(1) - no loop here\n";