Qual é o tempo O para determinar se um valor está em um array ordenado?

Question

Eu tenho uma matriz ordenada de 5000 inteiros. O quão rápido eu posso dizer se um número inteiro aleatório é um membro da matriz? Uma resposta em geral, C e Ruby seria bom.

Os valores da matriz são da forma

c * c + 1

onde c pode ser qualquer número inteiro de 1-5000.

Por exemplo:

[2, 5, 10, 17, 26, 37, 50 ...]

Answer 1

Pesquisa binária, como outros já referiram, é O (log2N), e pode ser codificado quer de forma recursiva:

   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
   }

ou iterativa:

   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
   }

No entanto, se você está procurando a maneira mais rápida possível, você pode configurar um olhar de tabela com base no sqrt(N-1) dos seus números. Com apenas 5.000 palavras de memória que você pode conseguir O (1) pesquisas desta forma.

Explicação:

Uma vez que todos os seus números são da forma N ^ 2 + 1 para um inteiro N de 1 a N, você pode criar uma tabela de N elementos. O elemento na posição i irá especificar se i ^ 2 + 1 está em sua matriz ou não. A mesa pode ser implementado com uma simples disposição de comprimento N. Ele irá tomar O (N) para a construção, e N palavras de espaço. Mas uma vez que você tem a mesa, todas as pesquisas são O (1).

Exemplo:

Aqui está o código de exemplo em Python, que se lê como pseudocódigo, como sempre: -)

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)

A construção da tabela ocupa S (N), no máximo, e as pesquisas são O (1).

Answer 2

log (n) para busca binária em c

Answer 3

Eu diria que é O (const)! :)

Dado um número aleatório R, é trivial para verificar se se trata de um número que pode ser representado na forma (n * n + 1). Basta verificar se o sqrt (r-1) é um número inteiro ou não!

(Bem, pode ser um pouco mais complicado do que isso desde a sua linguagem de programação pode apresentar alguma complexidade em lidar com números inteiros vs números de ponto flutuante, mas ainda: você não precisa procurar a matriz em tudo: basta verificar se o número é nesta forma particular.)

Answer 4

Tecnicamente, a complexidade de encontrar um elemento em uma matriz de tamanho fixo é constante, já log ₂ 5000 não vai mudar.

Answer 5

Binary Search é O (log n)

WikiPedia

Answer 6

O (N log N), se a matriz n tem elementos

Answer 7

Apenas para expandir em que: É lg n testes, isto é log ₂ n. Isso torna O ( log n) . Por quê? porque cada julgamento de uma pesquisa binária divide a matriz ao meio; assim, é preciso lg n tentativas.

Answer 8

Usando uma busca binária, é Log (N) tempo de busca.

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

Answer 9

Em Perl:

eu carregar os valores em um hash estático e, em seguida, seria ó (1).

construir o hash Lookup

lookup_hash {$ _} = 1 foreach (@original_array);

Lookup sintaxe

($ lookup_hash {$ valor_procurado}) && print "Encontrei-o em O (1) - nenhum loop aqui \ n";