Αποδοτικότητα των αλγορίθμων

Η απόδοση ενός προγράμματος εξαρτάται κύρια από τους αλγορίθμους και τις δομές δεδομένων που χρησιμοποιεί.

Πολλές φορές μπορούμε να βελτιώσουμε την απόδοση ενός αλγορίθμου αλλάζοντας εντολές.

Παράδειγμα 1:
// Return the position of X in the first N elements of A; -1 if not found
for (i = 0; i < N; i++)
if (A[i] == X)
return i;
return -1;
Παράδειγμα 2:
A[N] = X;
for (i = 0; A[i] != X; i++)
        ;
if (i == N)
        return -1;
else
        return i;
Παρατηρήστε τη διαφορά εντολών από το πρώτο στο δεύτερο παράδειγμα.
Μπορεί να υπάρχει αποδοτικότερος αλγόριθμος;

Για μεγάλο όγκο δεδομένων οι παραπάνω διαφορές είναι ασήμαντες.

Για να μετρήσουμε την απόδοση χρησιμοποιούμε τη σημειογραφία Ο().

Αυτή δείχνει την τάξη του χρόνου ή της μνήμης που απαιτεί ένας αλγόριθμος χωρίς να λαμβάνονται υπόψη σταθεροί (ανεξάρτητοι του ν) παράγοντες.

Παραδείγματα:

Γραμμική ανίχνευση Ο(ν)
Δυαδική ανίχνευση Ο(log ν)
Διπλός βρόχος Ο(ν²)

Όταν δύο Ο() διαφέρουν μεταξύ τους θα υπάρχει πάντα κάποιος όγκος δεδομένων για τον οποίο η διαφορά θα είναι αντιληπτή και στην πράξη.

Η σημειογραφία χρησιμοποιείται για να εξετάσουμε τόσο το χρόνο, όσο και το χώρο που απαιτεί ένας αλγόριθμος.

Παράδειγμα

Πρώτη λύση

for (i = L.begin(); i != L.end(); i++) {
        for (j = L2.begin(); j != L2.end(); j++)
                if (*j == i)
                        return true;
        L2.push_back(i);
}
return false;

Ο(ν²) χρόνος, Ο(ν) χώρος

Δεύτερη λύση

for (i = L.begin(), ci = 0; i != L.end(); i++, ci++)
        for (j = L.begin(), cj= 0; j < i; j++, cj++) {
                for (k = j + 1, ck = 0; ck < ci - cj; k++, ck++)
                        if (k == j)
                                return true;
return false;

Ο(ν³) χρόνος, Ο(1) χώρος

Τρίτη λύση

for (i = L.begin(), j = L.begin(); j != L.end(); i++, j++, j++)
if (j == i)
return true;
return false;

Ο(ν) χρόνος, Ο(1) χώρος