Algoritmo é um passo-a-passo do procedimento, o que define um conjunto de instruções a serem executadas em uma determinada ordem para obter o resultado pretendido. Algoritmos são geralmente criados independentes de 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, seguem – se algumas categorias importantes de algoritmos −
-
Search − Algorithm para procurar um item numa estrutura de dados.
-
Sort − Algorithm to sort items in a certain order.
-
inserir um algoritmo para inserir um item numa estrutura de dados.
-
Update − Algorithm to update an existing item in a data structure.
-
Delete − Algorithm to delete an existing item from a data structure.
características de um algoritmo
nem todos os procedimentos podem ser chamados de algoritmo., Um algoritmo deve ter as seguintes características −
-
algoritmo inequívoco deve ser claro e inequívoco. Cada uma das suas etapas (ou fases), e as suas entradas/saídas devem ser claras e conduzir a um único significado.
-
Input-um algoritmo deve ter 0 ou mais entradas bem definidas.
-
Saída − um algoritmo deve ter 1 ou mais saídas bem definidas, e deve corresponder à saída desejada.
-
Finiteness − Algorithms must terminate after a finite number of steps.,viabilidade-deve ser viável com os recursos disponíveis.
-
independente-um algoritmo deve ter direções passo a passo, que deve ser independente de qualquer código de programação.
Como escrever um algoritmo?
não existem padrões bem definidos para a escrita de algoritmos. Pelo contrário, depende do problema e dos recursos. Algoritmos nunca são escritos para suportar um código de programação particular.
Como sabemos que todas as linguagens de programação compartilham construções básicas de código como loops (fazer, por, enquanto), Controle de fluxo (if-else), etc., Estas construções comuns podem ser usadas para escrever um algoritmo.
escrevemos algoritmos passo a passo, mas nem sempre é o caso. A escrita de algoritmos é um processo e é executado depois que o domínio problema é bem definido. Ou seja, devemos conhecer o domínio do problema, para o qual estamos a conceber uma solução.
Example
Let ” s try to learn algorithm-writing by using an example.
problema-desenhe um algoritmo para adicionar dois números e exibir o resultado.
Step 1 − STARTStep 2 − declare three integers a, b & cStep 3 − define values of a & bStep 4 − add values of a & bStep 5 − store output of step 4 to cStep 6 − print cStep 7 − STOP
algoritmos dizem aos programadores como codificar o programa., Alternatively, the algorithm can be written as −
Step 1 − START ADDStep 2 − get values of a & bStep 3 − c ← a + bStep 4 − display cStep 5 − STOP
In design and analysis of algorithms, usually the second method is used to describe an algorithm. Torna fácil para o analista analisar o algoritmo ignorando todas as definições indesejadas. Ele pode observar que operações estão sendo usadas e como o processo está fluindo.
escrever números de passos, é opcional.
Nós projetamos um algoritmo para obter uma solução de um dado problema. Um problema pode ser resolvido de várias maneiras.,
portanto, muitos algoritmos de solução podem ser derivados para um dado problema. O próximo passo é analisar esses algoritmos de solução propostos e implementar a melhor solução adequada.
Análise de algoritmo
eficiência de um algoritmo pode ser analisada em duas fases diferentes, antes da implementação e após a implementação. Eles são os seguintes –
-
a Priori Análise – 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.
-
Uma análise Posterior − esta é uma análise empírica de um algoritmo. O algoritmo selecionado é implementado usando a linguagem de programação. Isto é então executado em máquina de computador alvo. Nesta análise, as estatísticas reais, como o tempo de execução e espaço necessário, são coletadas.
vamos aprender sobre uma análise de algoritmo a priori., 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 do computador executadas por operação.
Algoritmo de Complexidade
Suponha que X é um algoritmo e n é o tamanho dos dados de entrada, o tempo e o espaço utilizado pelo algoritmo de X são os dois principais fatores que decidem a eficiência de X.
-
Fator Tempo − o Tempo é medido pela contagem do número de operações de chave, tais como comparações no algoritmo de classificação.,
-
espaço Factor − espaço é medido pela contagem do espaço de memória máximo 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 de espaço
complexidade de espaço de um algoritmo representa a quantidade de espaço de memória necessária pelo algoritmo em seu ciclo de vida., O espaço necessário por um algoritmo é igual à soma dos dois componentes −
-
Uma parte fixa, que é um espaço necessário para armazenar alguns dados e variáveis, que são independentes do tamanho do problema. Por exemplo, variáveis e constantes simples usados, 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 dinâmica de memória, espaço de pilha recursiva, etc.,
Espaço complexidade S(P) de qualquer algoritmo de P é S(P) = C + SP(I), onde C é a parte fixa e S(I) é a parte variável do algoritmo, o que depende de instância característica I. a Seguir é um exemplo simples que tenta explicar o conceito −
Algorithm: SUM(A, B)Step 1 - STARTStep 2 - C ← A + B + 10Step 3 - Stop
Aqui temos três variáveis A, B e C e uma constante. Hence S (P) = 1 + 3. Agora, o espaço depende de tipos de dados de variáveis dadas e tipos constantes e será multiplicado em conformidade.,
complexidade de tempo
complexidade de tempo de um algoritmo representa a quantidade de tempo necessária pelo algoritmo para executar até a conclusão. Os requisitos de tempo podem ser definidos como uma função numérica T(n), em que T(n) pode ser medido como o número de passos, desde que cada passo consuma tempo constante.
Por exemplo, a adição de dois inteiros de n-bit toma n passos. Consequentemente, o tempo computacional total é T(n) = c ∗ n, onde c é o tempo necessário para a adição de dois bits. Aqui, observamos que T (n) cresce linearmente à medida que o tamanho da entrada aumenta.,