Olá lá! Finalmente estou de volta depois de mais de 2 meses sem escrever/tocar o código. Fui apanhado com toda a preparação e planeamento do casamento. É difícil arrancar um casamento no estrangeiro sem um organizador de casamentos. Mas tudo valeu a pena, já que o nosso casamento foi um para os livros! A febre do casamento acabou e agora é hora de relembrar meus pensamentos e voltar ao código (ainda em Swift).
Foi difícil decidir o que rever primeiro antes de começar a procurar emprego. Achei que deveria começar com os clássicos – algoritmos e estruturas de dados, o núcleo da programação. Em qualquer sistema, conforme os dados crescem, o desempenho não deve ser um problema se o algoritmo correto tiver sido usado.
Hoje, estou escrevendo um blog rápido sobre 2 tipos de grandes notas O, algoritmos Lineares e Logarítmicos.
Um pequeno fundo sobre a Notação Big O primeiro.
Análise Assintótica
Análise Assintótica é baseada em cálculos matemáticos que basicamente medem a eficiência de um algoritmo à medida que o conjunto de dados de entrada cresce (obrigado Wikipedia!). Existem outros tipos de análise assimptótica dependendo de onde ela é aplicada, mas em Ciência da Computação, ela é normalmente formatada como Big O Notation.
Linear vs. Logarítmica
Para entender facilmente Big O Notation, vamos comparar estes dois algoritmos: Linear – O(n) e Logarítmico – O(log n).
Como exemplo, vamos tentar procurar por um número em um array ordenado.
let numberList =
Linear O(n) – o desempenho torna-se menos eficiente à medida que os dados crescem.
Na técnica Linear ou “força bruta”, o desempenho depende do tamanho da entrada. Para o nosso exemplo, vamos ler cada item do array e procurar pelo número que precisamos. Easy peasy!
//Logarithmic Time - O(n)func linear(key: Int) {
for (index, number) in numberList.enumerated() {
if number == key {
print("Value found in index \(index)")
break
}
}
}
Of course that’s going to work for our small dataet, but it’s not very efficient once you have thousands, even millions of data.
Logaritmo O(log N) – reduz a pesquisa pela metade repetidamente até encontrar o valor alvo.
Usando a pesquisa binária – que é uma forma de algoritmo logarítmico, encontra a mediana no array e a compara com o valor alvo. O algoritmo irá atravessar ou para cima ou para baixo dependendo do valor alvo ser maior, menor ou igual à 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")
}
}
O grosso deste algoritmo está no início, mas lentamente vai-se aplanando à medida que descartamos o intervalo irrelevante do array e continuamos a reduzir para metade até encontrarmos o valor alvo.
Por meio do gráfico abaixo, podemos facilmente comparar como a maioria dos algoritmos tem desempenho semelhante com conjuntos de dados menores, mas diferem continuamente à medida que os dados crescem.
Como você pode ver existem outros tipos de Notação Big O que eu discutirei nos próximos dias. Ciao por agora!