Estruturas de dados - Noções básicas de algoritmos

Algoritmo é um procedimento passo a passo, que define um conjunto de instruções a serem executadas em uma determinada ordem para obter a saída desejada. Os algoritmos são geralmente criados independentemente das linguagens subjacentes, ou seja, um algoritmo pode ser implementado em mais de uma linguagem de programação.

Do ponto de vista da estrutura de dados, a seguir estão algumas categorias importantes de algoritmos -

  • Search - Algoritmo para pesquisar um item em uma estrutura de dados.

  • Sort - Algoritmo para classificar os itens em uma determinada ordem.

  • Insert - Algoritmo para inserir item em uma estrutura de dados.

  • Update - Algoritmo para atualizar um item existente em uma estrutura de dados.

  • Delete - Algoritmo para excluir um item existente de uma estrutura de dados.

Características de um Algoritmo

Nem todos os procedimentos podem ser chamados de algoritmo. Um algoritmo deve ter as seguintes características -

  • Unambiguous- O algoritmo deve ser claro e inequívoco. Cada uma de suas etapas (ou fases) e suas entradas / saídas devem ser claras e levar a apenas um significado.

  • Input - Um algoritmo deve ter 0 ou mais entradas bem definidas.

  • Output - Um algoritmo deve ter 1 ou mais saídas bem definidas e deve corresponder à saída desejada.

  • Finiteness - Os algoritmos devem terminar após um número finito de etapas.

  • Feasibility - Deve ser viável com os recursos disponíveis.

  • Independent - Um algoritmo deve ter instruções passo a passo, que devem ser independentes de qualquer código de programação.

Como escrever um algoritmo?

Não existem padrões bem definidos para escrever algoritmos. Em vez disso, é dependente de problemas e recursos. Algoritmos nunca são escritos para suportar um código de programação específico.

Como sabemos, todas as linguagens de programação compartilham construções de código básicas como loops (do, for, while), controle de fluxo (if-else), etc. Essas construções comuns podem ser usadas para escrever um algoritmo.

Escrevemos algoritmos passo a passo, mas nem sempre é o caso. A escrita do algoritmo é um processo e é executada depois que o domínio do problema está bem definido. Ou seja, devemos conhecer o domínio do problema, para o qual estamos projetando uma solução.

Exemplo

Vamos tentar aprender a escrever algoritmos usando um exemplo.

Problem - Projete um algoritmo para adicionar dois números e exibir o resultado.

Step 1 − START
Step 2 − declare three integers a, b & c
Step 3 − define values of a & b
Step 4 − add values of a & b
Step 5 − store output of step 4 to c
Step 6 − print c
Step 7 − STOP

Os algoritmos informam aos programadores como codificar o programa. Alternativamente, o algoritmo pode ser escrito como -

Step 1 − START ADD
Step 2 − get values of a & b
Step 3 − c ← a + b
Step 4 − display c
Step 5 − STOP

No projeto e análise de algoritmos, geralmente o segundo método é usado para descrever um algoritmo. Isso torna mais fácil para o analista analisar o algoritmo, ignorando todas as definições indesejadas. Ele pode observar quais operações estão sendo usadas e como o processo está fluindo.

Escrita step numbers, é opcional.

Projetamos um algoritmo para obter a solução de um determinado problema. Um problema pode ser resolvido de mais de uma maneira.

Portanto, muitos algoritmos de solução podem ser derivados para um determinado problema. O próximo passo é analisar esses algoritmos de solução propostos e implementar a solução mais adequada.

Análise de Algoritmo

A eficiência de um algoritmo pode ser analisada em dois estágios diferentes, antes e após a implementação. Eles são os seguintes -

  • A Priori Analysis- Esta é uma análise teórica de um algoritmo. A eficiência de um algoritmo é medida assumindo que todos os outros fatores, por exemplo, a velocidade do processador, são constantes e não têm efeito na implementação.

  • A Posterior Analysis- Esta é uma análise empírica de um algoritmo. O algoritmo selecionado é implementado em linguagem de programação. Isso é então executado na máquina do computador de destino. Nesta análise, estatísticas reais, como tempo de execução e espaço necessário, são coletadas.

Vamos aprender sobre a análise de algoritmo a priori . A análise de algoritmo lida com a execução ou tempo de execução de várias operações envolvidas. O tempo de execução de uma operação pode ser definido como o número de instruções de computador executadas por operação.

Complexidade do Algoritmo

Suponha X é um algoritmo e n é o tamanho dos dados de entrada, o tempo e o espaço usados ​​pelo algoritmo X são os dois fatores principais, que decidem a eficiência de X.

  • Time Factor - O tempo é medido contando o número de operações principais, como comparações no algoritmo de classificação.

  • Space Factor - O espaço é medido contando o espaço máximo de memória exigido pelo algoritmo.

A complexidade de um algoritmo f(n) dá o tempo de execução e / ou o espaço de armazenamento exigido pelo algoritmo em termos de n como o tamanho dos dados de entrada.

Complexidade do Espaço

A complexidade de espaço de um algoritmo representa a quantidade de espaço de memória exigida pelo algoritmo em seu ciclo de vida. O espaço exigido por um algoritmo é igual à soma dos dois componentes a seguir -

  • Uma parte fixa que é um espaço necessário para armazenar certos dados e variáveis, que são independentes do tamanho do problema. Por exemplo, variáveis ​​simples e constantes usadas, tamanho do programa, etc.

  • Uma parte variável é um espaço requerido por variáveis, cujo tamanho depende do tamanho do problema. Por exemplo, alocação de memória dinâmica, espaço de pilha de recursão, etc.

A complexidade espacial S (P) de qualquer algoritmo P é S (P) = C + SP (I), onde C é a parte fixa e S (I) é a parte variável do algoritmo, que depende da característica de instância I. Seguinte é um exemplo simples que tenta explicar o conceito -

Algorithm: SUM(A, B)
Step 1 -  START
Step 2 -  C ← A + B + 10
Step 3 -  Stop

Aqui temos três variáveis ​​A, B e C e uma constante. Portanto, S (P) = 1 + 3. Agora, o espaço depende dos tipos de dados de determinadas variáveis ​​e tipos de constantes e será multiplicado de acordo.

Complexidade de tempo

A complexidade de tempo de um algoritmo representa a quantidade de tempo necessária para que o algoritmo seja executado até a conclusão. Os requisitos de tempo podem ser definidos como uma função numérica T (n), onde T (n) pode ser medido como o número de etapas, desde que cada etapa consuma um tempo constante.

Por exemplo, a adição de dois inteiros de n bits leva npassos. Conseqüentemente, o tempo computacional total é T (n) = c ∗ n, onde c é o tempo gasto para a adição de dois bits. Aqui, observamos que T (n) cresce linearmente conforme o tamanho da entrada aumenta.