Dobrý den! Po více než dvou měsících nepsaní/dotýkání se kódu jsem konečně zpátky. Zastihly mě všechny ty svatební přípravy a plánování. Je těžké táhnout zahraniční svatbu bez svatebního plánovače. Ale stálo to za to, protože naše svatba byla jedna z nejlepších! Svatební horečka je pryč a teď je čas vzpamatovat se a vrátit se ke kódování (stále ještě ve Swiftu).
Bylo těžké se rozhodnout, co zkontrolovat jako první, než začnu hledat práci. Napadlo mě, že bych měl začít klasikou – algoritmy a datovými strukturami, jádrem programování. V každém systému by s růstem dat neměl být problém s výkonem, pokud byl použit správný algoritmus.
Dnes napíšu krátký blog o 2 typech zápisu velkého O, lineárních a logaritmických algoritmech.
Nejprve něco málo o notaci Big O.
Asymptotická analýza
Asymptotická analýza je založena na matematických výpočtech, které v podstatě měří efektivitu algoritmu s růstem vstupního souboru dat (díky Wikipedie!). Existují i jiné typy asymptotické analýzy podle toho, kde se používá, ale v informatice se běžně formátuje jako Big O Notation.
Lineární vs. logaritmický
Pro snadnější pochopení Big O Notation porovnáme tyto dva algoritmy: Lineární – O(n) a Logaritmický – O(log n).
Na příkladu se pokusíme vyhledat číslo v setříděném poli.
let numberList =
Lineární O(n) – s rostoucím objemem dat se výkon snižuje.
U lineární techniky neboli techniky „hrubé síly“ je výkon závislý na velikosti vstupu. V našem příkladu budeme číst každou položku v poli a hledat číslo, které potřebujeme. 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
}
}
}
To samozřejmě bude fungovat pro náš malý soubor dat, ale jakmile máte tisíce, nebo dokonce miliony dat, není to příliš efektivní.
Logaritmický O(log N) – zužuje hledání opakovaným půlením souboru dat, dokud nenajdete cílovou hodnotu.
Pomocí binárního hledání – což je forma logaritmického algoritmu, najde medián v poli a porovná ho s cílovou hodnotou. Algoritmus prochází buď směrem nahoru, nebo dolů v závislosti na tom, zda je cílová hodnota vyšší, nižší nebo rovna mediánu.
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")
}
}
Největší část tohoto algoritmu je na začátku, ale pomalu se zplošťuje, jak z pole vyřazujeme irelevantní rozsah a pokračujeme v půlení, dokud nenajdeme cílovou hodnotu.
Pomocí níže uvedeného grafu můžeme snadno porovnat, jak má většina algoritmů podobný výkon při menších souborech dat, ale průběžně se liší, jak data rostou.
Jak vidíte, existují i další typy zápisu Big O, které proberu v dalších dnech. Zatím čau!