Algorithm Analysis

Gabriel Dantas — Tue, 17 Sep 2024 22:29:40 +0000

Algorithm analysis is a way to measure the impact of an algorithm's performance in solving a problem, whether it is in terms of time or space. To start, we can talk about what algorithms solve: problems.

All computational problems have a set of arguments called instances. An instance can also be "a case" of a problem. One instance is specified when we know the value of the parameters. In general, not every problem has a great solution described by a known algorithm, and these problems are called "non-deterministic polynomial complete problems" or NP-complete problems. Of course, they can be solved but not in polynomial time by a knew algorithm. However, in some cases, we can solve any instance of a problem using a matching algorithm, so we will focus on these cases.

For these cases, when there is a known algorithm that solves them, we can calculate the time spent by the algorithm, or at least the equation that describes this amount of time. There are some mathematical definitions to classify an algorithm, like the Big O notation.

Big O notation is a way to describe the asymptotic efficiency of an algorithm. In other words, it is a simplified way to measure the time consumption of an algorithm, a way to express how they grow when we ignore very small n sizes, or in other words, focusing on large instances, where n is the size of the instance. When we evaluate the time spent by an algorithm, we can simplify this portion of time by calling it "t". So if a computer spends t to solve a problem using algorithm "a", we can say that the exact same algorithm solving the exact same problem on a computer that is twice as slow will spend 2t, and a computer that is twice as fast will spend t/2.

Big O notation also provides a definition for the upper limit and lower limit of an algorithm. These limits are represented by the Greek letters O and Ω respectively. So when we say that an algorithm has a time complexity of O(n²), we are saying: "the time spent by this algorithm is at most n2n2," i.e., in the worst case, our algorithm will spend n2n2 units of time, never worse than that.

On the other hand, when we say: "the time spent by this algorithm is Ω(n²)," that is the lower limit, and our algorithm will spend n2n2 in the best case, but it can be worse than that.

You might be thinking right now, "Ok, but what about the case where the algorithm grows exactly proportional to the instance size?" In this case, we have the Greek letter Θ to denote the time spent by the algorithm. Thus, the time spent can be described by Θ(). For example, if an algorithm spends Θ(n²), I know the time spent by the algorithm is proportional to n2n2, because n is the instance size.

This article is a kind of test to summarize what I've learned in the last few days/weeks. I will keep writing about my studies, I don't know how often, but like this one they will be short texts about specific topics in computer science. I also simplify some concepts in this text, for education and time propose, but feel free to explain in comments. And please, if I wrote something wrong about ANY concept, let me know. Thank you all, see you!

A Arquitetura que Revolucionou o Mundo: Uma breve introdução ao trabalho de John Von Neumann

Gabriel Dantas — Wed, 06 Mar 2024 23:34:24 +0000

Os computadores atuais seguem a arquitetura concebida em 1946 por John von Neumann. Computadores são máquinas digitais ou analógicas capazes de processar dados. No entanto, os computadores modernos são definidos por sua capacidade de armazenar programas no mesmo local onde armazenam os dados, o que lhes permite manipular esses dados.

Os primeiros computadores, como o ENIAC, serviam ao propósito de realizar cálculos e permitiam a possibilidade de reconfiguração através de válvulas que comutavam sinais, alternando bits entre 0 e 1. Isso permitia realizar operações matemáticas e utilizava tambores magnéticos e fitas perfuradas como memória principal.

Apesar de estarem muito à frente das calculadoras comuns, os primeiros computadores sofriam de diversos problemas, como falta de memória, alto custo de energia e humano. No entanto, o que nos trouxe até a arquitetura atual foi a forma como eles funcionavam. Os "programas" utilizados não eram armazenados em memória, o que comprometia a capacidade de guardar estados e realizar operações mais complexas. Apesar disso, os primeiros computadores apresentavam a capacidade de executar contextos mais complexos como condicionais e loops.

A arquitetura de Von Neumann estabelece cinco unidades principais para um computador:

Unidade de memória
Unidade de controle
Unidade lógica e aritmética
Unidade de entrada
Unidade de saída

Atualmente, conhecemos essas unidades respectivamente como:

Discos de memória não volátil como SSDs
ULA (Unidade Lógica e Aritmética) concebida pelo próprio John von Neumann e atualmente incorporada pelos processadores
CPU (Unidade Central de Processamento), que também integrada aos processadores realiza os cálculos aritméticos
Mouses e teclados
Dispositivos de saída como monitores

O alinhamento dessas unidades permite a um computador manipular os programas gravados em sua memória, o que os torna máquinas programáveis. Isso permite realizar qualquer problema computacional (todas as funções computáveis, com resultado determinístico) e até mesmo simular outros computadores. Essas capacidades combinadas tornam um computador Turing complete, o que significa que ele é capaz de realizar qualquer tarefa que possa ser descrita por um algoritmo. A definição literal de Turing complete é "projetado segundo as limitações de hardware atual", já que na concepção teórica de Turing a máquina possuía memória infinita em formato de fita de bits.

Claro que os computadores modernos incorporam muitos outros conceitos posteriores, que complementam essa arquitetura, como o uso de registradores, barramentos e múltiplos núcleos. Mas a ideia central da arquitetura continua a mesma, o que permite hoje as linguagens de programação de alto nível que são utilizadas pelos programadores. Isso permite que os computadores não só realizem operações matemáticas, mas também alterem o estado de seus próprios programas armazenados em memória em tempo de execução. Isso os torna muito mais "programáveis" que os primeiros computadores e abre um grande leque de possibilidades para a computação moderna.

Esse foi meu primeiro texto baseado na série de estudos que estou desenvolvendo atualmente, pretendo manter tudo em learning in public pra me motivar a continuar, criticas construtivas e correções são muito bem vindas, assim como seu like e compartilhamento, muito obrigado!

DEV Community: Gabriel Dantas

Algorithm Analysis

A Arquitetura que Revolucionou o Mundo: Uma breve introdução ao trabalho de John Von Neumann