Complexidade de algoritmo

Disponível somente no TrabalhosFeitos
  • Páginas : 8 (1757 palavras )
  • Download(s) : 0
  • Publicado : 19 de junho de 2012
Ler documento completo
Amostra do texto
Historia da Complexidade

A palavra algoritmo tem origem no sobrenome, Al-Khwarizmi, do matemático persa do século IX Mohamed Ben Musa, cujas obras foram traduzidas no ocidente cristão no século XII, tendo uma delas recebido o nome Algorithmi de numero indorum, sobre os algoritmos usando o sistema de numeração decimal (indiano). Outros autores, entretanto, defendem a origem da palavra emAl-goreten (raiz - conceito que se pode aplicar aos cálculos). Um programa de computador basicamente é um algoritmo que diz ao computador os passos a passos e as ordens que os programas devem ser executados. como por exemplo, os passos para calcular as notas dos boletins de alunos em uma certa escola, outro exemplo é um programa de academia que calcula a mensalidade dos alunos, quando vence, quando foipago, logo, o algoritmo pode ser considerado uma sequência de operações que podem ser simuladas por uma máquina de Turing completa. Quando os procedimentos de um algoritmo envolvem o processamento de dados, a informação é lida de uma fonte de entrada, processada e retornada sob novo valor após processamento, o que geralmente é realizado com o auxílio de uma ou mais estrutura de dados. Paraqualquer processo computacional, o algoritmo precisa estar rigorosamente definido, especificando a maneira que ele se comportará em todas as circunstâncias. A corretividade do algoritmo pode ser provada matematicamente, bem como a quantidade assintótica de tempo e espaço (complexidade) necessários para a sua execução. Estes aspectos dos algoritmos são alvo da análise de algoritmos. A maneira mais simplesde se pensar um algoritmo é por uma lista de procedimentos bem definida, na qual as instruções são executadas passo a passo a partir do começo da lista, uma idéia que pode ser facilmente visualizada através de um fluxograma. Tal formalização adota as premissas da programação imperativa, que é uma forma mecânica para visualizar e desenvolver um algoritmo. Concepções alternativas para algoritmosvariam em programação funcional e programação lógica. Hoje tem alguns objetivos para estudar algoritmo, a preocupação com a complexidade de algoritmos é fundamental para projetar algoritmos eficientes, muitas vezes as pessoas quando começam a estudar algoritmos perguntam-se qual a necessidade de desenvolver novos algoritmos para problemas  que ja têm solução. O desempenho é extremamente importantena informática pelo que existe uma necessidade constante de melhorar os algoritmos. Apesar de parecer contraditório, com o aumento da velocidade dos computadores, torna-se cada vez mais importante desenvolver algoritmos mais eficientes, devido ao aumento constante do "tamanho" dos problemas a serem resolvidos. Devido a este fator surge a Complexidade Computacional, pois e através dela que se tornapossível determinar se a implementação de determinado algoritmo é viável. podemos desenvolver um algoritmo e depois analisar a sua complexidade para verificar a sua eficiência, mas o melhor ainda é ter a preocupação de projetar algoritmos eficientes desde a sua concepção. Muitas vezes quando começamos a estudar algoritmos existe um questionamento da necessidade de se desenvolver novos algoritmospara resolução de problemas que já existem solução. Uma das respostas para isso, é que o desempenho é essencial para a informática. Apesar de parecer contraditório, com o aumento da velocidade dos computadores, torna-se cada vez mais importante desenvolver algoritmos mais eficientes, devido ao aumento constante do "tamanho" dos problemas a serem resolvidos. A avaliação analítica de um algoritmopode ser feita com vistas a se obter uma estimativa do esforço de computação, não em termos de unidade de tempo propriamente, mais em termos de uma taxa de crescimento do tempo de execução em função do “tamanho do problema”, i.e., do tamanho da entrada. Um exemplo típico desse relacionamento entre tamanho da entrada e tempo de processamento é o caso dos algoritmos de ordenação: nestes, os dados são...
tracking img