Notación “BIG - O”
Evidencia 4 – Equipo 4
Estructura de Datos
Integrantes:
• Nancy Nahomi García Peña – 2024245 – IAS
• Omar Alejandro Proa Salazar – 1968540 – IAS
• Deyanira Simón Acosta – 2016006 – IAS
• Jackzenny Yamileth Monsiváis Villanueva - 2017221
Docente: Noel Alejandro Hortiales Corona
Grupo: 008
San Nicolás de los Garza, Nuevo León, 18 de Noviembre del 2022
La notación Big – O es una función que permite determinar la complejidad de un
algoritmo, es decir, si el algoritmo seleccionado está totalmente óptimo para que se
pueda utilizar en diferentes circunstancias. Esta notación permite examinar varias
cosas dentro de su rango, un ejemplo es si el espacio en el disco es el correcto, si
los pasos están bien escritos o ejecutados y (el más importante) que tanto se tarda
en ejecutar el programa.
Este es muy importante ya que se supone que los algoritmos deben de estar
diseñados para que cualquiera los pueda usar, por lo tanto, al usarlos se espera
que sea más rápido. Si el algoritmo tarda un poco en ejecutarse no es malo pero
depende mucho en cuanto puedas tratar de hacer que funcione bien, es por eso
que se decide por la opción de usar está notación para crearlo desde cero.
En estos casos (hablando de tiempo) hay funciones que son más “caras” de utilizar,
por eso: a mayor tiempo, más caro será el algoritmo. Esto quiere decir que si te
empeñas en diseñarlo con buena presentación o con cualquier función que no se
haya visto antes pero olvidas las funciones principales del algoritmo entonces tienes
un pequeño problema, ya que el algoritmo debe ser específico en sus instrucciones
y verbos. Por estas razones se utiliza la notación Big – O.
También puede resultar que el caso mencionado pueda ser al revés, te empeñas a
que resulte lo más rápido posible pero se necesita más para que funcione. Todo
esto te lo puede decir la notación, ya que se encarga de decirte que es lo que falta
o lo que le agregas, ya depende de cuales sean las instrucciones específicas del
para que se necesita. Se debe de adaptar a lo que te pidan en caso de que sea para
personas que saben del tema o programación.
Hay términos que la notación debe de cumplir para que sea más utilizado
• O(1): Complejidad Constante
Esta complejidad nos dice que sin importar el dónde, el que y cómo lo
ejecutes, los resultados deben ser los mismos por lo tanto el tiempo y
ejecución del programa deben de ser los mismos.
• O(n): Complejidad Lineal
Esta ejecución tiene el significado de que su tiempo, usos y tamaño son
lineales por lo que es proporcional a sus usos, esto quiere decir que
siguen una línea recta al ejecutarse.
• O(log n): Complejidad logarítmica
Esta complejidad es equivalente, es decir, si un dato tiene un tamaño
determinado, el tiempo en que lo ejecutes será equivalente a ese tamaño
del peso y así seguidamente.
• O(n^2): Complejidad Cuadrática
Esta complejidad sigue la misma lógica que la complejidad logarítmica,
sólo que está multiplica al cuadrado el tiempo. Si tenemos un dato tamaño
2 su tiempo será de 4 segundos. Esta complejidad se relaciona con el
método burbuja y método de selección.
• O(2^n): Complejidad Exponencial
En esta complejidad se debe de escanear para saber si es compatible con
la misma; es caso de, el tamaño se incremental al doble, al igual si le
agregamos más datos y así sucesivamente.
Ejemplos
• O(n): Complejidad Lineal
function consoleNumbersTo(n) {
for (let i = 1; i <= n; i++) {
console.log(i)
consoleNumbersTo(10)
• O(n^2): Complejidad Cuadrática
function consoleMultiplicationOf(n) {
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= n; j++) {
console.log(`${i} * ${j} = ${i * j}`)
consoleMultiplicationOf(10)
• Peor de los casos
function consoleMultiplicationOf(n) {
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= n; j++) {
console.log(`${i} * ${j} = ${i * j}`)
}
}
}
consoleMultiplicationOf(10)
