como calcular a complexidade da pesquisa binária

Ouvi alguém dizer que, uma vez que a pesquisa binária reduz pela metade a entrada necessária para pesquisar, é um algoritmo de log (n). Como não sou de matemática, não sou capaz de me relacionar com isso. Alguém pode explicar isso com mais detalhes? isso tem a ver com a série logarítmica?

Aqui está uma maneira mais matemática de vê-lo, embora não seja realmente complicado. OMI muito mais claras que as informais:

A questão é: quantas vezes você pode dividir N por 2 até ter 1? Isto é essencialmente dizer, faça uma pesquisa binária (metade dos elementos) até encontrá-la. Em uma fórmula, seria este:

1 = N / 2 ^x

multiplique por 2 ^x :

2 ^x = N

agora faça o log ₂ :

log ₂ (2 ^x ) = log ₂ N
x * log ₂ (2) = log ₂ N
x * 1 = log ₂ N

isso significa que você pode dividir o registro N vezes até ter tudo dividido. O que significa que você precisa dividir o log N ("execute a etapa de pesquisa binária") até encontrar seu elemento.

Para Pesquisa Binária, T (N) = T (N / 2) + O (1) // a relação de recorrência

Aplique o Teorema Mestrado para calcular a complexidade do tempo de execução das relações de recorrência: T (N) = aT (N / b) + f (N)

Aqui, a = 1, b = 2 => log (a base b) = 1

Além disso, aqui f (N) = n ^ c log ^ k (n) // k = 0 & c = log (a base b)

Então, T (N) = O (N ^ c log ^ (k + 1) N) = O (log (N))

Fonte: http://en.wikipedia.org/wiki/Master_theorem

T (n) = T (n / 2) +1

T (n / 2) = T (n / 4) + 1 + 1

Coloque o valor de (n / 2) acima para que T (n) = T (n / 4) + 1 + 1. . . . T (n / 2 ^ k) + 1 + 1 + 1 ..... + 1

= T (2 ^ k / 2 ^ k) + 1 + 1 .... + 1 até k

= T (1) + k

Como tomamos 2 ^ k = n

K = log n

Portanto, a complexidade do tempo é O (log n)

Não metade do tempo de pesquisa, isso não tornaria o registro (n). Isso diminui logarítmica. Pense nisso por um momento. Se você tivesse 128 entradas em uma tabela e tivesse que pesquisar linearmente seu valor, provavelmente levaria cerca de 64 entradas, em média, para encontrar seu valor. Isso é n / 2 ou tempo linear. Com uma pesquisa binária, você elimina 1/2 das entradas possíveis a cada iteração, de modo que, no máximo, levaria apenas 7 comparações para encontrar seu valor (a base de log 2 de 128 é 7 ou 2 e a potência 7 é 128.) o poder da pesquisa binária.

A complexidade de tempo do algoritmo de pesquisa binária pertence à classe O (log n). Isso é chamado de notação O grande . A maneira como você deve interpretar isso é que o crescimento assintótico do tempo que a função leva para executar, dado um conjunto de tamanho de entrada n não excederá log n.

Este é apenas o jargão matemático formal para poder provar afirmações, etc. Tem uma explicação muito direta. Quando n cresce muito, a função log n aumenta em muito o tempo necessário para executar a função. O tamanho do "conjunto de entrada", n, é apenas o comprimento da lista.

Simplificando, a razão pela qual a pesquisa binária está em O (log n) é que ela reduz pela metade a entrada definida em cada iteração. É mais fácil pensar sobre isso na situação inversa. Nas x iterações, quanto tempo lista o algoritmo de pesquisa binária no max examinar? A resposta é 2 ^ x. A partir disso, podemos ver que o inverso é que, em média, o algoritmo de busca binária precisa de iterações log2 n para uma lista de comprimento n.

Se por que é O (log n) e não O (log2 n), é porque basta colocar novamente - Usar as grandes constantes da notação O não conta.

Aqui está a wikipedia entrada da

Se você observar a abordagem iterativa simples. Você está apenas eliminando metade dos elementos a serem pesquisados ​​até encontrar o elemento necessário.

Aqui está a explicação de como criamos a fórmula.

Diga inicialmente que você tem N número de elementos e, em seguida, o que você faz é ⌊N / 2⌋ como primeira tentativa. Onde N é a soma do limite inferior e do limite superior. O primeiro valor de tempo de N seria igual a (L + H), onde L é o primeiro índice (0) e H é o último índice da lista que você está procurando. Se você tiver sorte, o elemento que você tentar encontrar estará no meio [por exemplo. Você está procurando 18 na lista {16, 17, 18, 19, 20} e calcula ⌊ (0 + 4) / 2⌋ = 2 onde 0 é o limite inferior (L - índice do primeiro elemento da matriz) e 4 é o limite superior (índice H do último elemento da matriz). No caso acima, L = 0 e H = 4. Agora 2 é o índice do elemento 18 que você está procurando. Bingo! Você achou.

Se o caso fosse uma matriz diferente {15,16,17,18,19}, mas você ainda estivesse procurando por 18, não teria sorte e faria o primeiro N / 2 (que é ⌊ (0 + 4) / 2⌋ = 2 e, em seguida, perceba que o elemento 17 no índice 2. não é o número que você está procurando. Agora você sabe que não precisa procurar pelo menos metade da matriz na sua próxima tentativa de pesquisar de maneira iterativa. Então, basicamente, você não pesquisa metade da lista de elementos pesquisados ​​anteriormente, toda vez que tenta encontrar o elemento que não conseguiu encontrar na tentativa anterior.

Então, o pior caso seria

[N] / 2 + [(N / 2)] / 2 + [((N / 2) / 2)] / 2 .....
ou seja:
N / 2 ¹ + N / 2 ² + N / 2 ³ + ..... + N / 2 ^x … ..

até ... você terminar de pesquisar, onde o elemento que você está tentando encontrar está no final da lista.

Isso mostra que o pior caso é quando você atinge N / 2 ^x onde x é tal que 2 ^x = N

Noutros casos, N / 2 ^x onde x é tal que 2 ^x <N O valor mínimo de x pode ser 1, que é o melhor caso.

Agora, já que o pior caso é matematicamente quando o valor de
2 ^x = N
=> log ₂ (2 ^x ) = log ₂ (N)
=> x * log ₂ (2) = log ₂ (N)
=> x * 1 = log ₂ (N)
=> Mais formalmente ⌊log ₂ (N) + 1⌋

Log2 (n) é o número máximo de pesquisas necessárias para encontrar algo em uma pesquisa binária. O caso médio envolve pesquisas log2 (n) -1. Aqui estão mais informações:

http://en.wikipedia.org/wiki/Binary_search#Performance

Digamos que a iteração na Pesquisa Binária termine após k iterações. A cada iteração, a matriz é dividida pela metade. Então, digamos que o comprimento da matriz em qualquer iteração seja n Na Iteração 1,

Length of array = n

Na iteração 2,

Length of array = n⁄2

Na iteração 3,

Length of array = (n⁄2)⁄2 = n⁄22

Portanto, após a Iteração k,

Length of array = n⁄2k

Além disso, sabemos que após Depois divisões k, o comprimento da matriz torna-se uma Portanto

Length of array = n⁄2k = 1
=> n = 2k

Aplicando a função de log nos dois lados:

=> log2 (n) = log2 (2k)
=> log2 (n) = k log2 (2)
As (loga (a) = 1)

Portanto,

As (loga (a) = 1)
k = log2 (n)

Portanto, a complexidade de tempo da Pesquisa Binária é

log2 (n)

Uma pesquisa binária funciona dividindo o problema ao meio repetidamente, algo como isto (detalhes omitidos):

Exemplo procurando 3 em [4,1,3,8,5]

1. Encomende a sua lista de itens [1,3,4,5,8]
2. Veja o item do meio (4),
   • Se é o que você está procurando, pare
   • Se for maior, olhe para a primeira metade
   • Se for menor, veja a segunda metade
3. Repita o passo 2 com a nova lista [1, 3], encontre 3 e pare

É um bi pesquisa -nary quando você dividir o problema em 2.

A pesquisa requer apenas as etapas log2 (n) para encontrar o valor correto.

Eu recomendaria Introdução aos algoritmos se você quiser aprender sobre a complexidade algorítmica.

Como cortamos uma lista pela metade todas as vezes, precisamos saber em quantas etapas obtemos 1 enquanto dividimos uma lista por duas. No cálculo abaixo, x indica o número de vezes que dividimos uma lista até obtermos um elemento (no pior dos casos).

1 = N / 2x

2x = N

Tomando log2

log2 (2x) = log2 (N)

x * log2 (2) = log2 (N)

x = log2 (N)

T (N) = T (N / 2) + 1

T (N) = T (N / 2) + 1 = (T (N / 4) + 1) + 1

...

T (N) = T (N / N) + (1 + 1 + 1 + ... + 1) = 1 + logN (log de base 2) = 1 + logN

Portanto, a complexidade temporal da pesquisa binária é O (logN)

ok see this
for(i=0;i<n;n=n/2)
{
i++;
}
1. Suppose at i=k the loop terminate. i.e. the loop execute k times.

2. at each iteration n is divided by half.

2.a n=n/2                   .... AT I=1
2.b n=(n/2)/2=n/(2^2)
2.c n=((n/2)/2)/2=n/(2^3)....... aT I=3
2.d n=(((n/2)/2)/2)/2=n/(2^4)

So at i=k , n=1 which is obtain by dividing n  2^k times
n=2^k
1=n/2^k 
k=log(N)  //base 2

Deixe-me facilitar para todos vocês com um exemplo.

Por uma questão de simplicidade, vamos assumir que existem 32 elementos em uma matriz na ordem classificada, dos quais estamos procurando um elemento usando a pesquisa binária.

1 2 3 4 5 6 ... 32

Suponha que estamos procurando 32. após a primeira iteração, ficaremos com

17 18 19 20 .... 32

após a segunda iteração, ficaremos com

25 26 27 28 .... 32

após a terceira iteração, ficaremos com

29 30 31 32

após a quarta iteração, ficaremos com

31 32

Na quinta iteração, encontraremos o valor 32.

Então, se convertermos isso em uma equação matemática, obteremos

(32 X (1/2 ⁵ )) = 1

=> n X (2 ^-k ) = 1

=> (2 ^k ) = n

=> k log ₂ 2 = log ₂ n

=> k = log ₂ n

Daí a prova.

Aqui está a solução usando o teorema mestre, com LaTeX legível.

Para cada recorrência na relação de recorrência para pesquisa binária, convertemos o problema em um subproblema, com o tempo de execução T (N / 2). Portanto:

Substituindo o teorema mestre, obtemos:

Agora, como é 0 ef (n) é 1, podemos usar o segundo caso do teorema mestre, porque:

Isso significa que: