Vectores: Suma y Producto

Vectores

• Los vectores son herramientas fundamentales en física.

Suma de vectores

Método gráfico

• Los vectores se colocan consecutivamente, manteniendo su magnitud, dirección y sentido.
• El vector resultante une el origen del primer vector con el extremo del último.

Método analítico

Componentes rectangulares

• Cada vector se descompone en componentes horizontal ($V_x$) y vertical ($V_y$).
• $V_x = V \cos \theta$
• $V_y = V \sin \theta$
• El vector resultante se encuentra sumando las componentes horizontal y vertical de los vectores individuales.
• $R_x = \Sigma V_x$
• $R_y = \Sigma V_y$
• La magnitud del vector resultante se calcula con el teorema de Pitágoras: $R = \sqrt{R_x^2 + R_y^2}$
• El ángulo del vector resultante se calcula: $\theta = \tan^{-1} (\frac{R_y}{R_x})$

Producto de vectores

Producto escalar (punto)

• El producto escalar de dos vectores es un escalar.
• Se calcula como: $\overrightarrow{A} \cdot \overrightarrow{B} = AB \cos \theta$, donde A y B son las magnitudes y $\theta$ es el ángulo entre ellos.
• Puede calcularse como: $\overrightarrow{A} \cdot \overrightarrow{B} = A_x B_x + A_y B_y + A_z B_z$

Producto vectorial (cruz)

• El producto vectorial de dos vectores resulta en un vector perpendicular al plano que contiene a los dos vectores originales.
• Se calcula como:$\overrightarrow{A} \times \overrightarrow{B} = AB \sin \theta \hat{n}$, donde A y B son las magnitudes, $\theta$ es el ángulo entre ellos y $\hat{n}$ es un vector unitario perpendicular al plano.
• También se puede calcular como: $\qquad \overrightarrow{A} \times \overrightarrow{B} = \begin{vmatrix} \hat{i} & \hat{j} & \hat{k} \ A_x & A_y & A_z \ B_x & B_y & B_z \end{vmatrix} = (A_y B_z - A_z B_y)\hat{i} - (A_x B_z - A_z B_x)\hat{j} + (A_x B_y - A_y B_x)\hat{k}$
• La magnitud del producto vectorial es el área del paralelogramo formado por los dos vectores.

Algoritmos de ordenamiento

• Hay muchos algoritmos para ordenar colecciones de objetos.
• Elegir el más apropiado depende del tamaño de la colección, tipo de datos, restricciones de tiempo y espacio.

Complejidad de los algoritmos de ordenamiento

Complejidad temporal

• La complejidad temporal mide el tiempo necesario para ejecutar un algoritmo en función del tamaño de la entrada.
• Se expresa generalmente en notación "gran O".
• O(n log n): Complejidad óptima para algoritmos de ordenamiento generalistas (ej: ordenamiento por fusión, ordenamiento rápido).
• O(n2): Complejidad cuadrática, típica de algoritmos simples (ej: ordenamiento de burbuja, ordenamiento por inserción).
• O(n): Complejidad lineal, ideal pero rara para el ordenamiento (ej: ordenamiento por conteo, si los datos tienen una distribución favorable).

Complejidad espacial

• La complejidad espacial mide el espacio de memoria adicional necesario para ejecutar un algoritmo.
• O(1): Complejidad espacial constante, el algoritmo usa un espacio de memoria fijo, independiente del tamaño de la entrada (ej: ordenamiento de burbuja, ordenamiento por inserción).
• O(n): Complejidad espacial lineal, el algoritmo usa un espacio de memoria proporcional al tamaño de la entrada (ej: ordenamiento por fusión).

Algoritmos de ordenamiento clásicos

Ordenamiento de burbuja (Bubble Sort)

• Compara e intercambia elementos adyacentes mal ubicados hasta que la colección esté ordenada.
• Complejidad temporal: O(n2)
• Complejidad espacial: O(1)
• Ventajas: Simple de implementar.
• Desventajas: Muy lento para colecciones grandes.

Ordenamiento por inserción (Insertion Sort)

• Inserta cada elemento en su lugar en la porción ya ordenada de la colección.
• Complejidad temporal: O(n2)
• Complejidad espacial: O(1)
• Ventajas: Eficaz para colecciones pequeñas o parcialmente ordenadas.
• Desventajas: Lento para colecciones grandes no ordenadas.

Ordenamiento por selección (Selection Sort)

• Encuentra el elemento mínimo e intercámbialo con el primer elemento no ordenado, repite para el resto de la colección.
• Complejidad temporal: O(n2)
• Complejidad espacial: O(1)
• Ventajas: Simple de implementar.
• Desventajas: Lento para colecciones grandes.

Ordenamiento por fusión (Merge Sort)

• Divide la colección en sub-colecciones, ordena recursivamente las sub-colecciones, luego fusiona las sub-colecciones ordenadas.
• Complejidad temporal: O(n log n)
• Complejidad espacial: O(n)
• Ventajas: Eficaz para colecciones grandes, estable (preserva el orden relativo de los elementos iguales).
• Desventajas: Utiliza un espacio de memoria adicional.

Ordenamiento rápido (Quicksort)

• Elige un elemento pivote, particiona la colección en dos sub-colecciones (elementos inferiores al pivote y elementos superiores al pivote), ordena recursivamente las sub-colecciones.
• Complejidad temporal: O(n log n) en promedio, O(n2) en el peor caso.
• Complejidad espacial: O(log n) en promedio (recursivo).
• Ventajas: Muy eficaz en la práctica (a menudo el más rápido).
• Desventajas: Rendimiento sensible a la elección del pivote, inestable.

Ordenamiento por conteo (Counting Sort)

• Cuenta el número de ocurrencias de cada elemento, luego reconstruye la colección ordenada.
• Complejidad temporal: O(n + k) donde k es el rango de valores de los elementos.
• Complejidad espacial: O(k)
• Ventajas: Muy rápido para colecciones con un rango de valores pequeño.
• Desventajas: Solo funciona para enteros, necesita conocer el rango de valores.

Comparación de algoritmos de ordenamiento

• La elección del algoritmo de ordenamiento más adecuado depende de las características de los datos a ordenar y de las restricciones del problema.
• Para colecciones grandes, el ordenamiento por fusión y el ordenamiento rápido son generalmente los más eficientes.
• Para colecciones pequeñas o colecciones casi ordenadas, el ordenamiento por inserción puede ser una buena opción.
• El ordenamiento por conteo es muy eficaz para colecciones de enteros con un rango de valores pequeño.
• Conocer las ventajas y desventajas de cada algoritmo es importante para tomar la mejor decisión.

Complejidad Algorítmica

Operaciones elementales

• Adición: $O(1)$
• Sustracción: $O(1)$
• Multiplicación: $O(1)$
• División: $O(1)$
• Asignación: $O(1)$
• Comparación ($, ==$): $O(1)$
• Operación Booleana: $O(1)$
• Acceso a Array: $O(1)$

Instrucciones

Secuencia

• La complejidad de una secuencia de instrucciones corresponde a la complejidad máxima de estas instrucciones.

Bucle

• La complejidad de un bucle corresponde al número de iteraciones multiplicado por la complejidad de las instrucciones dentro del bucle.

Ejemplo

for (int i = 0; i < n; i++){ // bucle de n iteraciones

    cout  0){       // O(1)

    cout  O(n^2)

Complejidades comunes

Complejidades notables

Investigación

Array no ordenado

• $O(n)$: Se deben navegar todos los elementos para asegurarse de no perder el buscado.

Array ordenado

• $O(log(n))$: Dicotomía

Ordenamiento

• k es el número de claves diferentes.