Conceptos que hay que tener en cuenta a la hora de programar.

El código imperativo describe cómo se hace algo, mientras el declarativo describe qué se está haciendo.
La programación declarativa expresa la lógica sin describir un flujo (if, bucles…).

El código siguiente es imperativo:

using System;
class Example
{
    static void Main()
    {
        Int32 sum = 0;
        for (Int32 i = 0; i < 100; i++)
        {
            if (i % 2 == 0)
            {
                sum += i;
            }
        }
        Console.WriteLine(sum);
    }
}

Su equivalente declarativo sería:

using System;
using System.Linq;
 
class Example
{
    static void Main()
    {
        Int32 sum = Enumerable.Range(0, 99)
                      .Where(i => i % 2 == 0)
                      .Sum();
        Console.WriteLine(sum);
    }
}

O con un grado declarativo mayor:

using System;
using System.Linq;
 
class Example
{
    static void Main()
    {
        Int32 sum = Enumerable.Range(0, 99)
                      .Where(isEven)
                      .Sum();
        Console.WriteLine(sum);
    }
    static Boolean isEven(Int32 number)
    {
        return number % 2 == 0;
    }
}

Esta notación es una forma de representar la complejidad de una algoritmo. Esto significa que es una forma de calculo de tiempo (o proceso) en la que teniendo una cantidad de datos cuánto tiempo\proceso costaría si esta cantidad cambia.
Hay que entender que que los algoritmos se han de comparar con los del mismo tipo, es decir, un algoritmo que realice operaciones aritméticas no debería ser comparado con uno que ordene números, en cambio sí que podrán ser comparados dos que realicen operaciones aritméticas (por ejemplo uno sumas y otro multiplicaciones).
Big-O reduce la comparación a una simple variable escogida a partir de observaciones o casos asumidos.
Básicamente viene a decirte cuanto tardaría el algoritmo en ordenar un millón de elementos si tarda un segundo en ordenar 10000.

Imaginemos algoritmos aritméticos (suma, resta, multiplicación y división). Por ejemplo la suma, esta consiste básicamente en alinear a la derecha los dos números a sumar e ir recorriendolos de derecha a izquierda e ir sumandolos (teniendo en cuenta las unidades que sobrepasen dos dígitos), si sumamos dos cifras de 6 dígitos cada una tendremos que hacer seis sumas, si sumamos dos cifras de 100 dígitos haremos 100 sumas. La complejidad de la operación es directamente proporcional al número de dígitos, llamamos a esta complejidad lineal y representada como O(n).

La multiplicación en cambio es diferente, se van colocando línea a línea los dígitos del primer número multiplicados por los dígitos del segundo (para después hacer una suma). Es decir si multiplicamos dos cifras de 6 dígitos haremos 36 multiplicaciones y sobre 10 sumas. Si multiplicamos números de 100 dígitos tendremos que hacer 10000 multiplicaciones y 200 sumas. Esta complejidad es la llamada complejidad cuadrática y representada como O(n²).

Es importante entender que sólo nos preocuparemos de la porción más significante de la notación. Es decir, en este caso de la multiplicación podríamos representarlo como O(n² + 2n) pero si nos fijamos nos daremos cuenta que el segundo término (2n) es insignificante (el 0,00002% de las operaciones realizadas).

Pongamos una búsqueda de elementos ordenados como ejemplo. Imaginemos una lista telefónica ordenada por los nombres, si buscasemos uno, por ejemplo “John Smith”, lo que haríamos sería un Binary Search (o búsqueda por bisección), dividir la lista entre dos y ver en cual de las porciones resultantes está tal nombre, volverla a dividir y así hasta encontrarlo. De esta forma se podría encontrar un nombre en una lista de millones con sólo realizar esta acción 21 veces…
Para una lista de 3 nombres nos tomaría 2 comparaciones (como mucho).
Para una de 7 como máximo 3.
Para 15, 4.
Para 1.000.000 nos tomaría 21.
En Big-O esta sería la complejidad logarítmica, O(log n).

Gracias a la notación Big-O podemos deteminar los siguientes casos, con este ejemplo:

• El mejor caso, encontrarlo con una única comparación. Esto sería la complejidad constante, representada por O(1).
• El caso esperado, O(log n).
• El peor caso, también O(log n).

Aunque generalmente será el peor caso en el que estemos interesados.

Si en cambio buscamos un nombre a partir de un número de teléfono lo que haremos ir de número en número comprobando hasta encontrar el idéntico. Por lo que determinaríamos:

• El mejor caso: O(1).
• El esperado: O(n) (unas 500.000 comparaciones).
• El peor: O(n) (1.000.00' comparaciones).

The Travelling Salesman

This is quite a famous problem in computer science and deserves a mention. In this problem you have N towns. Each of those towns is linked to 1 or more other towns by a road of a certain distance. The Travelling Salesman problem is to find the shortest tour that visits every town.

Sounds simple? Think again.

If you have 3 towns A, B and C with roads between all pairs then you could go:

A → B → C A → C → B B → C → A B → A → C c → A → B C → B → A

Well actually there's less than that because some of these are equivalent (A → B → C and C → B → A are equivalent, for example, because they use the same roads, just in reverse).

In actuality there are 3 possibilities.

Take this to 4 towns and you have (iirc) 12 possibilities. With 5 it's 60. 6 becomes 360.

This is a function of a mathematical operation called a factorial. Basically:

5! = 5 * 4 * 3 * 2 * 1 - 120 6! = 6 * 5 * 4 * 3 * 2 * 1 = 720 7! = 7 * 6 * 5 * 4 * 3 * 2 * 1 = 5040 … 25! = 25 * 24 * … * 2 * 1 = 15,511,210,043,330,985,984,000,000 … 50! = 50 * 49 * … * 2 * 1 = 3.04140932… × 10^64

So the Big-O of the Travelling Salesman problem is O(n!) or factorial or combinatorial complexity.

By the time you get to 200 towns there isn't enough time left in the universe to solve the problem with traditional computers.

Something to think about.

Polynomial Time

Another point I wanted to make quick mention of is that any algorithm that has a complexity of O(na) is said to have polynomial complexity or is solvable in polynomial time.

Traditional computers can solve problems in polynomial time. Certain things are used in the world because of this. Public Key Cryptography is a prime example. It is computationally hard to find two prime factors of a very large number. If it wasn't, we couldn't use the public key systems we use.

Anyway, that's it for my (hopefully plain English) explanation of Big O (revised).

• Artículo sobre el diseño orientado a objetos