Hello! Végre visszatértem, miután több mint 2 hónapig nem írtam/érintettem kódot. Elkapott az összes esküvői előkészítés és tervezés. Nehéz egy tengerentúli esküvőt esküvőszervező nélkül lebonyolítani. De minden megérte, hiszen az esküvőnk a könyvekbe illő volt! Az esküvői láznak vége, és most itt az ideje, hogy összeszedjem a gondolataimat, és visszatérjek a kódoláshoz (még mindig Swiftben).
Nehéz volt eldönteni, mit nézzek át először, mielőtt elkezdeném az álláskeresést. Úgy gondoltam, hogy a klasszikusokkal kell kezdenem – algoritmusok és adatszerkezetek, a programozás magja. Minden rendszerben, ahogy az adatok nőnek, a teljesítmény nem lehet probléma, ha a megfelelő algoritmust használták.
Ma egy gyors blogot írok a Big O jelölések 2 típusáról, a lineáris és a logaritmikus algoritmusokról.
Először egy kis háttér a Big O jelölésről.
Aszimptotikus analízis
Az aszimptotikus analízis matematikai számításokon alapul, amely alapvetően egy algoritmus hatékonyságát méri a bemeneti adathalmaz növekedésével (köszönet a Wikipédiának!). Az aszimptotikus analízisnek más típusai is léteznek attól függően, hogy hol alkalmazzák, de az informatikában általában Big O jelölésként formázzák.
Lineáris vs. logaritmikus
A Big O jelölés könnyű megértéséhez ezt a két algoritmust fogjuk összehasonlítani: Lineáris – O(n) és Logaritmikus – O(log n).
Példaként megpróbálunk megkeresni egy számot egy rendezett tömbben.
let numberList =
Lineáris O(n) – a teljesítmény az adatok növekedésével egyre kevésbé hatékony.
A lineáris vagy “nyers erő” technikában a teljesítmény a bemeneti mérettől függ. Példánkban végigolvassuk a tömb minden egyes elemét, és megkeressük a szükséges számot. 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
}
}
}
Ez persze a mi kis adathalmazunk esetében működni fog, de nem túl hatékony, amint több ezer, sőt milliónyi adatunk van.
Logaritmikus O(log N) – szűkíti a keresést az adathalmaz ismételt megfelezésével, amíg meg nem találjuk a célértéket.
Bináris keresés – ami a logaritmikus algoritmus egy formája, megtalálja a mediánt a tömbben, és összehasonlítja a célértékkel. Az algoritmus felfelé vagy lefelé halad attól függően, hogy a célérték nagyobb, kisebb vagy egyenlő a mediánnál.
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")
}
}
Az algoritmus nagy része az elején van, de lassan ellaposodik, ahogy a nem releváns tartományt kidobjuk a tömbből, és folytatjuk a megfelezést, amíg meg nem találjuk a célértéket.
A lenti grafikonon keresztül könnyen összehasonlíthatjuk, hogy a legtöbb algoritmus teljesítménye kisebb adathalmazok esetén hasonló, de az adatok növekedésével folyamatosan különbözik.
Mint láthatjuk, a Big O jelölésnek vannak más típusai is, amelyeket a következő napokban fogok tárgyalni. Ciao egyelőre!