什么是O时间以确定是否值是一个排序的数组？

StackOverflow https://stackoverflow.com/questions/470605

题

我具有5000个整数的排序后的数组。我如何快速判断一个随机整数数组中的一员？在一般情况下，C和红宝石的回答将是很好。

在数组的值是以下形式的

c * c + 1

其中c可以是从1至5000的任意整数。

例如：

[2, 5, 10, 17, 26, 37, 50 ...]
有帮助吗？

解决方案

二进制搜索，如其他人提及的，是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)查找表。与只是5000的存储器字就可以实现O（1）查找这种方式。

说明：

由于所有的数字是从1-3的整数N到N的形式N ^ 2 + 1的，可以创建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）。

其他提示

的log（n）为第C二进制搜索

我会说这是O（常量）！ ：）

给定一个随机数r，是微不足道的检查它是否是可能的形式来表示的数（N * N + 1）。只是检查的sqrt（R-1）是否为整数或不！

（当然，这可能是比这更复杂一点，因为你的编程语言，可以引入一些复杂性与整数处理VS浮点数，但还是：你不需要到阵列的所有搜索：只需检查是否数是在该特定的形式。）

从技术上讲，在一个固定大小的数组找到一个元件的复杂性是恒定的，因为log <子> 2 5000是不会改变。

二进制搜索是O（log n）的

维基百科

O（log n）的，如果数组有n个元素

只是为了扩大是：它的 LG 名词的测试，即登录 2 ñ。这使得它的 O（的登录 n）的。为什么？因为二进制搜索的每个试验中分割一半的阵列;因此它需要的 LG n次试验。

使用二进制搜索，它的日志（N）的搜索时间。 

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

在Perl：

我将在值加载到一个静态散列，然后这将是O（1）。

构建查找散

lookup_hash {$ _} = 1的foreach（@original_array）;

查找语法

（$ lookup_hash {$ Lookup_Array中}）&&打印 “在O（1）找到它 - 无环这里\ n” 个;

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top