Naiv algoritmus

A problémát egyszerű módon megoldó, azonban nagy idő- és tárbonyolultságú algoritmusokat nevezzük naiv algoritmusoknak.^[1] 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.^[2]

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 Θ(n²) az időbonyolultsága.^[3] 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.^[4][5][6] A naiv algoritmusok általában nem fogadhatóak el éles üzemi, teljesítménykritikus alkalmazásokban, használatuk jellemzően prototípusok készítésére korlátozódik.