A nagy számonkéréseken elvi hibának, halálfejes hibáknak nevezzük azokat a hibákat, melyek egyértelműen az alapvető ismeretek hiányáról tanúskodnak.
/* sorminták */
int a, b, c, d, ...;
scanf("%d", &a);
–||– ("%d", &b);
–||– c);
...
printf("%d", c);
–||– ("%d", b);
–||– ("%d", a);
/* nem kért I/O */
void paros_e(void) {
int szam;
scanf("%d", &szam);
if (szam % 2 == 0)
printf("páros");
else
printf("páratlan");
}
/* bitek / pow */ x = y | pow(2, 3);
/* tömbméret? */ char s1[]; gets(s1); char *s2; gets(s2);
| hatékonyság | örülünk-e |
|---|---|
| Θ(1), konstans | 
|
| Θ(log n), logaritmikus | 
|
| Θ(n), lineáris | 
|
| Θ(n2), négyzetes | 
|
| Θ(en), exponenciális | 
|
Lineáris keresés: Θ(n)
- Lehet, hogy egyből megtaláljuk, lehet, hogy a végén lesz
- Átlagosan a felét kell végignézni
- A keresési idő egyenesen arányos a tömb méretével
Bináris keresés: Θ(log2n)
- Minden lépésben felezzük az intervallumot
- A keresési idő ~ log2méret. 1 millió → 20 lépés!
Algoritmusok hatékonysága általában
Az Θ(n) jelöléssel szoktuk jellemezni egy algoritmus gyorsaságát. A jelölésben az n a bemenet hosszát, a bemeneti adatok számát jelenti. Θ(n) azt jelenti, hogy a lépésszám nagyjából lineárisan, Θ(n2) pedig, hogy nagyjából négyzetesen függ a bemeneti adatok számától.
szerepelt
Egy algoritmus lépésszáma annak vizsgálatával becsülhető, esetleg pontosan meg is határozható. Az így kapott függvénynél csak a leggyorsabban végtelenhez tartó tagot vesszük figyelembe, mert nagy bemenet esetén az a döntő. Az n2 gyorsabban tart a végtelenhez („bikább”), mint az n, mivel bármilyen nagy konstans szorzó, pl. 10000n esetén is lehet olyan n-et találni, amelyre n2>10000n. Az exponenciális függvény tart leggyorsabban a végtelenhez, míg a logaritmus függvény értéke pedig mindegyik közül a leglassabban.
Emiatt részesítjük előnyben az olyan algoritmusokat, amelyek Θ(1), Θ(log n) vagy Θ(n) időben futnak. Az Θ(n2) nagy n-ek esetén már lassú lehet; Θ(en) pedig valószínűleg lassú már kis n-ek esetén is. Éppen erre épülnek a titkosítások: ha jó az algoritmus, akkor a megfejtés csak próbálkozásra épülhet – ami viszont viszonylag kis kulcs esetén is beláthatatlanul hosszú ideig tart. (Titkosítás: ha a jelszó (titkosítás kulcsa) 128 bites, a végigpróbálandó lehetőségek száma: 2128=340282366920938463463374607431768211456 darab.)
Lényege: egymás melletti elemek összehasonlítása és cseréje.
Egy sor csere által a legnagyobb elem a végére kerül.
A buborékrendezés egymás melletti elemeket hasonlít össze. Lépései:
- Hasonlítsuk össze az első két elemet. Ha nincsenek jó sorrendben, cseréljük meg.
- Hasonlítsuk össze a második párt (második és harmadik elem). Esetleg csere.
- Folytassuk így a tömb végéig.
- A legnagyobb elem ezáltal a tömb végére kerül, még akkor is, ha legelöl volt. Az már a végleges helye.
- Csináljuk meg ugyanezt még egyszer, a tömb elejétől az utolsó előttiig. Az utolsóhoz már nem kell nyúlni, hiszen az a legnagyobb.
- Aztán ugyanezt megint, de az utolsó kettőhöz már nem nyúlunk stb.
Futás közben így a tömb két részre oszlik: egy már rendezett és egy még rendezetlen részletre. A rendezetlen részlet egyre csökken; azon belül kell összehasonlítani és esetleg cserélni a párokat. Ezért az algoritmus két ciklust tartalmaz. A külső ciklus az egyre kisebb rendezetlen részt határozza meg; a belsejében lévő pedig az egymás melletti párok összehasonlítását vezérli.
void buborek(double *t, int db) {
/* egyre rövidebb tömbrészletek ciklusa */
for (int i = db-1; i > 0; --i) {
/* egymás utáni párok ciklusa */
for (int j = 0; j < i; ++j) {
if (t[j] > t[j+1]) {
double temp = t[j];
t[j] = t[j+1];
t[j+1] = temp;
}
}
}
}Javított buborékrendezés (improved bubble sort)
Figyeli, hogy egy fésülés során volt-e csere. Ha nem, leállítható.
Azért lehet ezt megtenni, mert a fésülések közben mindig ugyanazt a listarészletet vizsgáljuk, vagyis mindig annak egy egyre rövidebb darabját. Ha az egészet végignézve nem kellett cserélni, akkor egy kisebb részt vizsgálva sem fog kelleni.
Keverő rendezés (cocktail sort)
A sima buborékrendezésnél: nyulak és teknősök.
- nyulak (rabbits)
- nagy értékű elemek, amelyek a hamar a helyükre kerülnek
- teknősök (turtles)
- kicsi értékűek, amelyek lassan vándorolnak a tömb elejére
Ötlet: a rendezést felváltva egyik-másik irányba végezzük.
Tömbök rendezésekor két problémába ütközhetünk. Az egyik, ha nagyon nagyok a tömbelemek (pl. nagy struktúrák), akkor a rendezés nagyon lassú lehet. A másik, hogy esetleg egyszerre többféle rendezettségre is szükségünk lehet. Pl. egy névsornál ábécé sorrendre, és kor szerinti, azaz születési évszám szerinti sorrendre. Vagy egy szótárprogramban az angol és a magyar szó szerinti ábécé rendet is fenntartanánk egyszerre.
Ötlet: egy indexelő tömböt rendezzünk, ne az eredetit!
Az indexelő tömb lényege, hogy a tényleges, adatokat tároló
tömböt nem közvetlenül indexeljük, hanem veszünk mellé egy int-eket
tároló tömböt is. Annak „szemüvegén” keresztül nézzük az eredeti tömböt. Így az
indexelő tömbbe tett számok sorrendje határozza meg azt, hogy az adatelemeinket
milyen sorrendben látjuk.
Ember nevsor[100];
int index[100]; // ugyanakkora
printf("%s", nevsor[index[3]].nev);
/* nevsor[nev_idx[i]] → név szerinti */
/* nevsor[szuletesi_datum_idx[i]] → dátum szerinti */Ha nem az eredeti tömböt rendezzük, hanem az indexelő tömböt, akkor sokkal gyorsabbak a cserék, és ezáltal a rendezések is. Az indexelő tömb ötlete megoldja a többféle rendezettség problémáját is: elég csak két indexelő tömböt használni. Sőt, az adatokat sem kell duplán tárolni!
Ugyanez megvalósítható lenne pointereket tartalmazó tömbbel is.
Lényege: ha az egymás mellettiek rossz sorrendben vannak, akkor csere, amúgy léphetünk egyet előre. Ha a csere által rossz sorrend keletkezik, az csak a csere előtt lehet, ezért visszafelé kell lépni egyet.
void torperendez(double *t, int db) {
int i = 0;
while (i < db) {
if (i == 0 || t[i-1] <= t[i]) { // jó sorrend?
i++; /* előre */
} else {
double tmp = t[i]; /* csere */
t[i] = t[i-1];
t[i-1] = tmp;
i--; /* vissza */
}
}
}Rekurzió
Az elv, hogy meg lehet hívni egy függvényből egy másikat, rögtön felveti a kérdést: vajon saját magát is?
Pl. mi lenne, ha egy faktoriálist számító masina így nézne ki belülről:
┌
│ 1, ha n=0
n! = ┤
│ n·(n-1)!, ha n>0
└
Ez helyes, hiszen ha N=0, a faktoriálisa 1, ha nem 0, akkor pedig N faktoriálisa N szorozva N-1 faktoriálisával.
Ha beteszünk a nagy faktoriális gépbe egy miniatűr faktoriális gépet (működjön az bárhogy is), egy jó megoldást kapunk.
A verem nevű memóriaterületre kerülnek függvényhíváskor a paraméterek és a visszatérés adatai. Ide kerülnek a lokális változók is.
Ezt a memóriaterületet azért nevezik veremnek, mivel ugyanúgy telik meg, mint egy verem (gödör). Amit legutoljára betettünk, azt látjuk legfelül, és kivenni is azt tudjuk legelőször.
Érdekesség: a vermet is Alan Turing találta ki. Amikor egy értéket az általa tervezett gép betett a verembe, azt a műveletet BURY-nek, azaz eltemetésnek nevezte. A kivétel pedig az UNBURY, vagyis a kiásás.
A paramétereket a hívó programrész helyezi el a verembe. A visszatérési értéknek a helyét is a hívó foglalja le. Ezért a függvényhívás után ennek a dolga ezeket a területeket felszabadítani is. A hívott függvény foglal helyet a saját lokális változói számára, és így ennek a dolga az is, hogy felszabadítsa azt. Mindezzel nekünk semmi dolgunk nincsen, a fordító hozza létre ezeket a programrészeket a háttérben. Ezért ezeket automatikus kezelésű változóknak is szokták nevezni.
Minden függvényhíváskor létrejön tehát egy rész a veremben, amely az adott híváshoz tartozik, és visszatéréskor megszűnik. Ennek neve: keret (stack frame). Ha a függvényből egy másik függvényt is meghívunk, akkor egy ahhoz tartozó keret is létrejön a veremben – mindig legfelül, természetesen.
Alább egy függvényhívás látható, a hozzá kialakuló veremszerkezettel.
#include <stdio.h>
int fakti(int n) {
int szorzat = 1;
for (int i=2; i<=n; ++i)
szorzat *= i;
return szorzat;
}
int main(void) {
int x = fakti(5);
printf("%d", x);
return 0;
}
A függvényhívás előtt a következő történik:
- A hívó
main()beteszi a verembe a paramétereket. - Helyet csinál a visszatérési értéknek is.
- Meghívja a függvényt, ami által bekerül a verembe a visszatérés címe (vagyis hogy hol kell folytatni a programot a függvényből visszatérvén).
A fakti() függvényben a működés:
- Létrehozza magának a lokális változókat a veremben.
- A paramétereit a veremben találja.
- A visszatérési értéket a verembe teszi, a megfelelő memóriaterület felülírásával.
- Amikor visszatér, akkor a hívóhoz ugrik vissza – a cím a veremben.
A függvényhívás után a hívó:
- A veremben megtalálja a visszatérési értéket. Ezt felhasználja, ha szeretné.
- Kitörli a veremből az általa betett függvényparamétereket, hiszen azokra már nincsen szükség.
Ahogy a ciklusoknak is van egy feltételük, amely nem teljesülése esetén megállnak az iterációk, a rekurziónál is előbb-utóbb el kell jutnunk egy olyan pontra, amikor a függvény már nem hívja meg magát. Különben sose térne vissza. A rekurziónál ezt báziskritériumnak nevezzük.
Leállási feltétel
- Kell legyen egy báziskritérium: amikor már nem hívja meg magát.
- Minden lépésben közeledni kell a báziskritériumhoz.
Klasszikus példa a rekurzióra az ún. Fibonacci számsor. Ebben a számsorban minden elem az őt megelőző két elem összege.
┌
│n, ha n<2
Fib(n)┤
│Fib(n-2)+Fib(n-1) amúgy
└
int fib(int n)
{
if (n < 2) // báziskritérium
return n;
else
return fib(n-2) + fib(n-1);
}A fenti függvényben teljesül a leállási feltétel: n<2
esetén a függvény nem hívja meg már magát, és a hívások során mindig kisebb n
szám a paraméter. A számsor kiszámítására amúgy ez nem túl hatékony megoldás, inkább
csak az egyszerűsége miatt szép a függvény. Vegyük észre a rajzon: pl. a fib(2)
értékét többször is kiszámoljuk. (Sőt a függvényhívások száma exponenciálisan növekszik.)
lesz róla szó