¡Hola! Por fin he vuelto después de más de 2 meses sin escribir/tocar código. Me ha pillado la preparación y planificación de la boda. Es difícil llevar a cabo una boda en el extranjero sin un planificador de bodas. Pero valió la pena, ya que nuestra boda fue un éxito. La fiebre de la boda ha terminado y ahora es el momento de recoger mis pensamientos y volver a la codificación (todavía en Swift).
Fue difícil decidir qué revisar primero antes de empezar a buscar trabajo. Pensé que debía empezar con los clásicos: algoritmos y estructuras de datos, el núcleo de la programación. En cualquier sistema, a medida que los datos crecen, el rendimiento no debería ser un problema si se ha utilizado el algoritmo correcto.
Hoy, estoy escribiendo un blog rápido sobre 2 tipos de notaciones Big O, algoritmos lineales y logarítmicos.
Primero, un poco de información sobre la Notación Big O.
Análisis asintótico
El análisis asintótico se basa en cálculos matemáticos que básicamente miden la eficiencia de un algoritmo a medida que crece el conjunto de datos de entrada (¡gracias Wikipedia!). Hay otros tipos de análisis asintótico dependiendo de dónde se aplique, pero en Ciencias de la Computación, se formatea comúnmente como Notación Big O.
Lineal vs. Logarítmica
Para entender fácilmente la Notación Big O, compararemos estos dos algoritmos: Lineal – O(n) y Logarítmico – O(log n).
Como ejemplo, intentaremos buscar un número en un array ordenado.
let numberList =
Lineal O(n) – el rendimiento se vuelve menos eficiente a medida que los datos crecen.
En la técnica Lineal o de «fuerza bruta», el rendimiento depende del tamaño de la entrada. Para nuestro ejemplo, leeremos cada elemento de la matriz y buscaremos el número que necesitamos. Fácil,
//Logarithmic Time - O(n)func linear(key: Int) {
for (index, number) in numberList.enumerated() {
if number == key {
print("Value found in index \(index)")
break
}
}
}
Por supuesto que va a trabajar para nuestro pequeño conjunto de datos, pero no es muy eficiente una vez que usted tiene miles, incluso millones de datos.
Logarítmico O(log N) – reduce la búsqueda reduciendo repetidamente a la mitad el conjunto de datos hasta encontrar el valor objetivo.
Usando la búsqueda binaria – que es una forma de algoritmo logarítmico, encuentra la mediana en la matriz y la compara con el valor objetivo. El algoritmo recorrerá hacia arriba o hacia abajo dependiendo de que el valor objetivo sea mayor, menor o igual que la mediana.
func binarySearch(key: Int, iminIndex: Int, imaxIndex: Int) {let midIndex = round(Double(iminIndex + imaxIndex)/2)
let midNumber = numberList
var result = ""//using recursion, we can go up or down the array and reduce the range
if midNumber > key { //target is less than the median so traverse downwards binarySearch(key: key, iminIndex: iminIndex, imaxIndex: Int(midIndex) - 1) } else if midNumber < key { //target is greater than the median so traverse upwards binarySearch(key: key, iminIndex: Int(midIndex) + 1, imaxIndex: imaxIndex) } else if midNumber == key { //Found it!
print("Found it at index \(midIndex)")} else {
print("Value \(key) not found")
}
}
El grueso de este algoritmo se encuentra al principio, pero se va aplanando poco a poco a medida que descartamos el rango irrelevante del array y continuamos reduciendo a la mitad hasta encontrar el valor objetivo.
A través del gráfico siguiente, podemos comparar fácilmente cómo la mayoría de los algoritmos tienen un rendimiento similar con conjuntos de datos más pequeños, pero difiere continuamente a medida que los datos crecen.
Como puedes ver hay otros tipos de notación Big O que discutiré en los próximos días. Por ahora, hasta la vista
.