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 Θ(n2) 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.
Jegyzetek
[szerkesztés]- ↑ Naive_algorithm. wcipeg.com. [2013. június 6-i dátummal az eredetiből archiválva]. (Hozzáférés: 2013. április 11.)
- ↑ What is a “naive” algorithm, and what is a “closed - form” solution?. stackoverflow.com. (Hozzáférés: 2014. április 11.)
- ↑ Sorting with BubbleSort. Bourns College of Engineering. [2008. november 20-i dátummal az eredetiből archiválva]. (Hozzáférés: 2014. április 11.)
- ↑ Sorting Algorithms. Rochester Institute of Technology, Computer Science Department. (Hozzáférés: 2014. április 11.)
- ↑ Sorting Algorithms. University of British Columbia. [2006. október 8-i dátummal az eredetiből archiválva]. (Hozzáférés: 2014. április 11.)
- ↑ Sorting Algorithm Animations. sorting-algorithms.com. (Hozzáférés: 2014. április 11.)
