Originaly posted on myblog.

Hello, today we are going to talk about Algoritmics!

"Algoritmics? Is it eatable?"

Hell no, or only by your brain. Before speaking about algoritmics, let's talk about algorithm. According toWikipedia:

Inmathematics andcomputer science, analgorithm (ⁱ/ˈælÉ¡É™rɪðəm/AL-gÉ™-ri-dhÉ™m) is a self-contained sequence of actions to be performed. Algorithms can performcalculation,data processing andautomated reasoning tasks.An algorithm is aneffective method that can be expressed within a finite amount of space and time^[1] and in a well-defined formal language^[2] for calculating afunction.^[3] Starting from an initial state and initial input (perhapsempty),^[4] the instructions describe acomputation that, whenexecuted, proceeds through a finite^[5] number of well-defined successive states, eventually producing "output"^[6] and terminating at a final ending state. The transition from one state to the next is not necessarilydeterministic; some algorithms, known asrandomized algorithms, incorporate random input.^[7]

This is quite difficult to eat. To put it simply, an algorithm is a sequence of operations which produce a result. For example, when you are baking bread, you follow an algorithm: you're putting the flour, then the yeast, etc... And it produces bread.

And again according toWikipedia:

Algorithmics is the science ofalgorithms. It includesalgorithm design, the art of building a procedure which can solve efficiently a specific problem or a class of problem,algorithmic complexity theory, the study of estimating the hardness of problems by studying the properties of algorithm that solves them, oralgorithm analysis, the science of studying the properties of a problem, such as quantifying resources in time and memory space needed by this algorithm to solve this problem.

We could say that algorithmics is studying and making algorithm. This include calculate the complexity or the cost of them.

"Cost? I got to pay?"

Yes and no. An algorithm got a cost of resources. When you bake your bread, you use ingredients (those are the inputs) and for each action, you use resources (like your hand, a wooden spoon, etc...) and those represent the cost.

What we want is to evaluate this cost, also called complexity.

Again withWikipedia (yes, again):

Incomputer science, theanalysis of algorithms is the determination of the amount of time, storage and/or other resources necessary toexecute them. Mostalgorithms are designed to work with inputs of arbitrary length. Usually, the efficiency or running time of an algorithm is stated as a function relating the input length to the number of steps (time complexity) or storage locations (space complexity).

"So, how do we measure that?"

First, it exists a specific notation: O(f(n)) ("Big O of f(n)") where f is a mathematical function of n.

Look at the following algorithm:

Entries: array a of size nFor i from 1 to n do  print a[i] // one action hereEnd for

We got an input array with n elements. For each of the, we are going to print it, so one action. At the end, the algorithm should have print n time. So n actions. So the complexity is O(n).

It does not matter if you make one are two actions, the constant factor is always relative to n.

But in the following algorithm:

Entries: array a of size nFor i from 1 to n do  For j from 1 to n do    print a[i] // one action  End forEnd for

We do a second loop inside the first one. So we are printing n messages n times. So the complexity is O(n²).

"Ok, and the Rust"

It is juste the language I have chose to make the future algorithms.

As this article starts to getting big, I shall end it here, see you next for the studying of bubble sort.

-- Mathieu