Complexidade linear de tempo de pesquisa

A pesquisa linear é pesquisa seqüencial. Este método de pesquisa verifica os elementos da lista um por um, começando do primeiro elemento. Quando vê a primeira ocorrência do elemento que está procurando, as paradas de busca. O elemento que está procurando é chamado de alvo. Se o elemento não for encontrado, todos os elementos da lista serão verificados. A pesquisa linear é um algoritmo de pesquisa muito simples que todo programador deve aprender, oficial ou intuitivamente.

Considere a seguinte lista:

Eu j a c b g d h e f

Para procurar A, o programa deve iterar a lista 3 vezes. Para procurar G, o programa deve iterar a lista 6 vezes. Para procurar F, o programa deve iterar a lista 10 vezes. Para procurar K ou qualquer carta que não esteja na lista, o programa deve iterar a lista 10 vezes e não encontrará uma correspondência.

O objetivo deste artigo é produzir a complexidade do tempo para pesquisa linear. A programação é feita na discussão seguinte C.

Algoritmo de pesquisa linear

O algoritmo para pesquisa linear é direto. Suponha que a lista seja uma matriz baseada por zero indexado. Deixe a variável que representa cada índice ser eu. Deixe a matriz ter o nome A. As etapas são as seguintes:

• • Deixe eu ser 0.
  • Se um [i] é o alvo, o valor para eu é devolvido e a pesquisa termina com sucesso.
  • Se um [i] não for o alvo, aumente i por 1 e repita a etapa anterior.
  • Embora eu seja menor que n, onde n é a duração da matriz, continue repetindo as duas etapas anteriores em ordem.
  • Continue assim até que o alvo seja encontrado ou não encontrado.

A pesquisa termina com sucesso quando o alvo é encontrado. A pesquisa termina sem sucesso quando o alvo não é encontrado. Para um final malsucedido, todos os n elementos são verificados.

Complexidade do tempo

A complexidade do tempo é o número de operações principais para algum código para concluir sua tarefa. Verificar se o alvo corresponde a um elemento é uma operação. Existe a pior complexidade do tempo, a complexidade do tempo médio e a melhor complexidade do tempo.

Pior complexidade do tempo

O número máximo de operações ocorre quando o alvo está no final da lista ou não está na lista. Este é o pior caso. A pior complexidade do tempo é dada como:

Sobre)

Isso usa a notação Big-O. A notação Big-O começa com a mancha O, seguida de parênteses. Dentro dos parênteses está a expressão para o número de operações para resolver a tarefa.

Melhor complexidade do tempo

Se o primeiro elemento da lista for o alvo, apenas uma operação de verificação será necessária para a pesquisa. Isto é, apenas uma operação é necessária para a pesquisa. Esta é a melhor complexidade do tempo. Está escrito como:

O (1)

Onde 1 nos parênteses significa uma operação.

Complexidade do tempo médio

A complexidade do tempo médio depende da distribuição de probabilidade. Se cada elemento puder estar em qualquer posição, cada elemento é igualmente provável que seja pesquisado. Nesta situação, a complexidade do tempo médio é dada como:

O (n/2)

Programação em c

A pesquisa linear é provavelmente a pesquisa mais fácil de escrever um programa para. Basta seguir o algoritmo, que é repetido aqui, para facilitar a referência:

• • Deixe eu ser 0.
  • Se um [i] é o alvo, o valor para eu é devolvido e a pesquisa termina com sucesso.
  • Se um [i] não for o alvo, aumente i por 1 e repita a etapa anterior.
  • Embora eu seja menor que n, onde n é a duração da matriz, continue repetindo as duas etapas anteriores em ordem.
  • Continue assim até que o alvo seja encontrado ou não encontrado.

Essencialmente, o programa é o seguinte:

#incluir
int linearSearch (char a [], int n, char t)
para (int i = 0; iif (t == a [i])
retornar i;

Começa incluindo o stdio.biblioteca H responsável pela entrada e saída. Depois disso, existe a definição de função linearSearch (). O código principal na definição da função é o loop for. O loop for escaneado a matriz do início ao fim, procurando uma partida do alvo. Se um alvo for encontrado, o índice para o elemento correspondente na matriz será retornado. Para obter o número ordinal do índice do elemento correspondente, adicione 1 ao índice baseado em zero.

Uma função principal C adequada para o programa acima é a seguinte:

int main (int argc, char ** argv)

int n = 10;
char a [] = 'i', 'j', 'a', 'c', 'b', 'g', 'd', 'h', 'e', ​​'f';
int ret = linearsearch (a, n, 'g');
printf ("%i \ n", ret);
retornar 0;

A primeira declaração da função principal C declara o número de elementos na matriz especificada. Depois disso, há a matriz com o nome A. Existem dez caracteres na matriz. A declaração da matriz começa com "char" e não "int". A partir daí, a função linearsearch () definida é chamada. O primeiro argumento para a chamada de função é a matriz. O segundo argumento é o número de elementos na matriz. O terceiro argumento é o alvo que é a letra cuja presença na matriz é verificada. Se estiver presente, o índice baseado em zero será retornado. Se não estiver presente, nada será devolvido.

A próxima declaração imprime qualquer índice retornado. Para esta função principal C, 5 é impresso. Se 1 for adicionado a 5, seria 6, que é o índice ordinal.

Conclusão

A pior complexidade do tempo é dada como:

Sobre)

Isso usa a notação Big-O. A notação Big-O começa com a mancha O, seguida de parênteses. Dentro dos parênteses está a expressão para o número de operações para resolver a tarefa.

Se o primeiro elemento da lista for o alvo, apenas uma operação de verificação será necessária para a pesquisa. Isto é, apenas uma operação é necessária para a pesquisa. Esta é a melhor complexidade do tempo. Está escrito como:

O (1)

Onde 1 nos parênteses significa uma operação.

A complexidade do tempo médio de depende da distribuição de probabilidade. Se cada elemento puder estar em qualquer posição, cada elemento é igualmente provável que seja pesquisado por este algoritmo. Nesta situação, a complexidade do tempo médio é:

O (n/2)