Algoritmus függő a futási idő

Default book

Akit eddig nem győzött meg az algoritmusok használatának fontossága.

Az alábbi grafikonon egy Excel táblát előállító kód futási idejei találhatók. A vízszintes tengelyen az előállítandó Excel tábla sorai találhatók és a függőleges tengelyen a hozzá szükséges idő.

Látszik, hogy a futási idő a barnával jelölt adatsornál négyzetesen nő a sorok számával. Ezt az alábbi kód produkálta:

for($i=0;$i< $n;++$i){
   $puffer = $puffer . $data;
}

A kék adatsort az alábbi kód hozta létre:

for($i=0;$i< $n;++$i){
   $puffer .= $data;
}

Mi a magyarázat? Az első esetben a memóriához kétszer nyúl hozzá a program, mert kiveszi a memóriából, hozzáadja a kisebb stringet és visszaírja a helyére!

A második esetben a puffer korábbi tartalmát nem bántja a program, hanem a végének a mutatóját veszi és lefoglal plusz memóriát és hozzáírja az adatot.

Futásiidő analízis!