Witam! W końcu wróciłem po ponad 2 miesiącach nie pisania/dotykania kodu. Zostałem złapany przez wszystkie przygotowania i planowanie ślubu. Ciężko jest zorganizować zagraniczny ślub bez wedding plannera. Ale wszystko było tego warte, ponieważ nasz ślub był niezapomniany! Gorączka ślubna się skończyła i teraz nadszedł czas, aby zebrać moje myśli i wrócić do kodowania (wciąż w Swift).
Ciężko było zdecydować, co przejrzeć najpierw, zanim zacznę szukać pracy. Uznałem, że powinienem zacząć od klasyki – algorytmów i struktur danych, czyli rdzenia programowania. W każdym systemie, gdy danych przybywa, wydajność nie powinna być problemem, jeśli użyto właściwego algorytmu.
Dzisiaj piszę szybkiego bloga o 2 typach notacji Big O, algorytmach liniowych i logarytmicznych.
Na początek trochę tła na temat notacji Big O.
Analiza asymptotyczna
Analiza asymptotyczna opiera się na obliczeniach matematycznych, które zasadniczo mierzą wydajność algorytmu, gdy zbiór danych wejściowych rośnie (dzięki Wikipedii!). Istnieją inne rodzaje analizy asymptotycznej w zależności od tego, gdzie jest stosowana, ale w informatyce jest ona powszechnie formatowana jako Big O Notation.
Liniowa vs. Logarytmiczna
Aby łatwo zrozumieć Big O Notation, porównamy te dwa algorytmy: Linear – O(n) i Logarithmic – O(log n).
Na przykładzie spróbujemy poszukać liczby w posortowanej tablicy.
let numberList =
Linear O(n) – wydajność staje się mniejsza wraz ze wzrostem danych.
W technice Linear lub „brute force” wydajność zależy od rozmiaru danych wejściowych. Dla naszego przykładu, będziemy czytać przez każdy element w tablicy i szukać liczby, której potrzebujemy. 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
}
}
}
Oczywiście to zadziała dla naszego małego zbioru danych, ale nie jest to bardzo wydajne, gdy masz tysiące, a nawet miliony danych.
Logarytmiczny O(log N) – zawęża wyszukiwanie przez wielokrotne zmniejszanie zbioru danych o połowę, aż do znalezienia wartości docelowej.
Użycie wyszukiwania binarnego – które jest formą algorytmu logarytmicznego, znajduje medianę w tablicy i porównuje ją z wartością docelową. Algorytm będzie się przemieszczał w górę lub w dół w zależności od tego, czy wartość docelowa jest wyższa, niższa lub równa medianie.
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")
}
}
Większa część tego algorytmu jest na początku, ale powoli spłaszcza się, gdy odrzucamy nieistotny zakres z tablicy i kontynuujemy przepoławianie, dopóki nie znajdziemy wartości docelowej.
Poprzez poniższy wykres możemy łatwo porównać, jak większość algorytmów ma podobną wydajność z mniejszymi zestawami danych, ale stale różni się, gdy dane rosną.
Jak widać istnieją inne rodzaje notacji Big O, które omówię w następnych dniach. Ciao na razie!