Naiv algoritmus
A Wikipédiából, a szabad lexikonból.
A problémát egyszerű módon megoldó, azonban nagy idő- és tárbonyolultságú algoritmusokat nevezzük naiv algoritmusoknak. A naiv jelző arra utal, hogy a megoldás nem optimális, mert „okosabb” algoritmussal a probléma kisebb idő- és tárköltséggel is megoldható. A naiv algoritmusoknak általában nagy az erőforrásigénye, azonban egyszerű megérteni és implementálni őket.
Jellegzetes példája a naiv algoritmusnak a buborékrendezés, amely mindössze néhány sorból áll, így könnyű megérteni, viszont Θ(n2) az időbonyolultsága. A quicksort algoritmus ennél „okosabb” és valamivel nehezebb megérteni, viszont az időigénye csak Θ(n log n). Például egy 100 elemű lista rendezéséhez a buborékrendezésnek 10 000 iterációs lépésre van szüksége, míg a quicksort mindössze 110 iterációval oldja meg ugyanazt a feladatot.
Ahogy a példa is mutatja, a naiv algoritmusokat leginkább prototípusok készítésénél használják, és általában nem elfogadhatóak éles üzemi, teljesítménykritikus alkalmazásokban.
Based on work by