Diferencias

Muestra las diferencias entre dos versiones de la página.

--- code:best-practices [2010/07/16 18:52]
alfred
+++ — (actual)
@@ Línea 1: / Línea 1: @@
-====== Codificando ======
-Conceptos que hay que tener en cuenta a la hora de programar.
-===== Programación declarativa =====
-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:
-<code csharp>
-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);
-    }
-}
-</code>
-Su equivalente declarativo sería:
-<code csharp>
-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);
-    }
-}
-</code>
-O con un grado declarativo mayor:
-<code csharp>
-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;
-    }
-}
-</code>
-===== Big-O Notation =====
-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. \\ \\
-==== Uso ====
-=== Complejidad lineal ===
-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)''.
-=== Complejidad cuadrática ===
-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).
-=== Complejidad logarítmica ===
-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 [[otros:algoritmos#binary_search|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)''.
-=== Determinar casos ===
-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).
-=== Complejidad factorial ===
-Partiendo del problema del vendedor, en él tenemos N ciudades cada una de ellas conectadas con una o más ciudades por carretareras de distinta longitud y hay que encontrar la forma de visitarlas todas recorriendo el menor trazo posible. Por ejemplo teniendo las ciudades A, B y C las carreteras podrían ir:
-<code>
-A -> B -> C
-A -> C -> B
-B -> C -> A
-B -> A -> C
-C -> A -> B
-C -> B -> A
-</code>
-Realmente hay sólo 3 posibilidades (aunque el proceso debería diferenciarlas) ya que "A -> B -> C" y "C -> B -> A" son equivalentes (usan las mismas carreteras). Pero con 4 ciudades realmente hay 12 posibilidades, con 5 hay 60 y con 6 360. Esto es un factorial:
-<code>
-! = 5 * 4 * 3 * 2 * 1 = 120
-! = 6 * 5 * 4 * 3 * 2 * 1 = 720
-! = 7 * 6 * 5 * 4 * 3 * 2 * 1 = 5040
-...
-! = 25 * 24 * ... * 2 * 1 = 15,511,210,043,330,985,984,000,000
-...
-! = 50 * 49 * ... * 2 * 1 = 3.04140932... × 10^64
-</code>
-Por lo que en términos de Big-O el problema del vendedor se representa como ''O(n!)'' y se le llama de **complejidad factorial o combinacional**.
-===== Notas =====
-  * {{code:how_i_explained_ood.pdf|Artículo sobre el diseño orientado a objetos}}

Programming

Herramientas de usuario

Herramientas del sitio

Diferencias

Herramientas de la página