确定一个值是否在有序数组中的 O 时间是多少?

发布于 2024-07-13 04:01:57 字数 242 浏览 9 评论 0原文

我有一个包含 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 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(9

贪了杯 2024-07-20 04:01:57

log(n) 在 c 上进行二分查找

log(n) for binary search on c

三生路 2024-07-20 04:01:57

我会说它是 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.)

心欲静而疯不止 2024-07-20 04:01:57

正如其他人提到的,二分搜索是 O(log2N),并且可以递归地编码:

   BinarySearch(A[0..N-1], value, low, high) {
       if (high < low)
           return -1 // not found
       mid = (low + high) / 2
       if (A[mid] > value)
           return BinarySearch(A, value, low, mid-1)
       else if (A[mid] < value)
           return BinarySearch(A, value, mid+1, high)
       else
           return mid // found
   }

或迭代地编码:

   BinarySearch(A[0..N-1], value) {
       low = 0
       high = N - 1
       while (low <= high) {
           mid = (low + high) / 2
           if (A[mid] > value)
               high = mid - 1
           else if (A[mid] < value)
               low = mid + 1
           else
               return mid // found
       }
       return -1 // not found
   }

但是,如果您正在寻找尽可能最快的方法,您可以根据 设置一个查找表>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 中的示例代码,一如既往地读起来像伪代码 :-)

import math

N = 5000
ar = [17, 26, 37, 50, 10001, 40001]

lookup_table = [0] * N

for val in ar:
    idx = int(math.sqrt(val - 1))
    lookup_table[idx] = 1

def val_exists(val):
    return lookup_table[int(math.sqrt(val - 1))] == 1

print val_exists(37)
print val_exists(65)
print val_exists(40001)
print val_exists(90001)

构建表最多需要 O(N),而查找则为 O(1)。

Binary search, as others have mentioned, is O(log2N), and can be coded either recursively:

   BinarySearch(A[0..N-1], value, low, high) {
       if (high < low)
           return -1 // not found
       mid = (low + high) / 2
       if (A[mid] > value)
           return BinarySearch(A, value, low, mid-1)
       else if (A[mid] < value)
           return BinarySearch(A, value, mid+1, high)
       else
           return mid // found
   }

or iteratively:

   BinarySearch(A[0..N-1], value) {
       low = 0
       high = N - 1
       while (low <= high) {
           mid = (low + high) / 2
           if (A[mid] > value)
               high = mid - 1
           else if (A[mid] < value)
               low = mid + 1
           else
               return mid // found
       }
       return -1 // not found
   }

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 :-)

import math

N = 5000
ar = [17, 26, 37, 50, 10001, 40001]

lookup_table = [0] * N

for val in ar:
    idx = int(math.sqrt(val - 1))
    lookup_table[idx] = 1

def val_exists(val):
    return lookup_table[int(math.sqrt(val - 1))] == 1

print val_exists(37)
print val_exists(65)
print val_exists(40001)
print val_exists(90001)

Building the table takes up O(N) at most, and lookups are O(1).

凉墨 2024-07-20 04:01:57

从技术上讲,在固定大小的数组中查找元素的复杂性是恒定的,因为 log2 5000 不会改变。

Technically, the complexity of finding an element in a fixed-size array is constant, since log2 5000 isn't going to change.

一页 2024-07-20 04:01:57

二分查找的时间复杂度为 O(log n)

WikiPedia

Binary Search is O(log n)

WikiPedia

花辞树 2024-07-20 04:01:57

如果数组有 n 个元素,则 O(log n)

O(log n) if the array has n elements

独行侠 2024-07-20 04:01:57

扩展一下:它是 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.

待天淡蓝洁白时 2024-07-20 04:01:57

使用二分搜索时,搜索时间为 Log(N)。

bool ContainsBinarySearch(int[] array, int value) {
  return Array.BinarySearch(arrray, value) >= 0;
}

Using a binary search, it's Log(N) search time.

bool ContainsBinarySearch(int[] array, int value) {
  return Array.BinarySearch(arrray, value) >= 0;
}
皓月长歌 2024-07-20 04:01:57

在 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";

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文