• barr
    #125
    check this!

    Nagyvonalakban ez az a megközelítés amivel az algoritmizálási problémákat hatékonyság szempontjából le lehet írni. Ezzel az elemzéssel és jelöléssel a feladat számítási idejének a karakterisztikáját figyeled, ami tetszőleges számú és legkevésbé kedvező bemenet esetén előfordulhat, ami ad egy mindenkori felső limitet a futási időre(vagy pl. memóriaigényt is lehet hasonló módon elemezni...). Emellett megállapítható egy mindenkori legoptimálisabb futási idő is, így a probléma (bemenet, azok rendezettsége, memóriaigény...) jellegétől függően válaszhatsz egy számodra megfelelő eljárást. Így amikor van egy bonyolultabb algoritmusod a fenti megközelítés ad egy tulajdonképpeni profilt a problémára.Pl::
    Type of Sort Best Worst Average
    ...
    QuickSort O(N log N) O(N2) O(N log N)
    HeapSort O(N log N) O(N log N) O(N log N)

    A fentiek közül a HeapSort jellemzően lassabb mint a QuickS, de az előfordulható legkedvezőtlenebb bemenetre sokkal jobb eredményt ad.
    Nézz meg pl. gráf-bejáró algoritmusokat ha érdekel az hogy milyen különbségek lehetnek az egyes megoldások közt, futási idő szempontjából...

    Jah igen, és gyakran már a használt adatszerkezet szintjén eldől az hogy mmennyire optimális a programod. Pl piros-fekete fák használatával garantálhatod hogy a keresés iszonyatos gyors lesz, viszont a fa előállítás utáni módosítása elég költséges...

    És végül Donald Knuth örökzöldje::"...premature optimization is the root of all evil"