Το κόστος ενός αλγορίθμου

Μέτρηση πράξεων

Το δεύτερο ερώτημα

Τα μαθήματα Σχεδίαση σωστών βρόχων και Αναδρομή δίδαξαν πώς αποδεικνύεται ότι ένας αλγόριθμος είναι σωστός: ότι τερματίζει και ότι το αποτέλεσμά του ικανοποιεί τη μετασυνθήκη. Όμως το μάθημα Αριθμητικοί αλγόριθμοι έδειξε δύο εξίσου σωστούς ελέγχους πρώτου, έναν με περίπου $n$ διαιρέσεις και έναν με περίπου $\sqrt{n}$, και το μάθημα Αναδρομή δύο σωστούς τρόπους να υπολογιστεί το $F_{30}$, έναν με $2\,692\,537$ κλήσεις και έναν με 29 προσθέσεις. Αν αυτό ισχύει, η ορθότητα δεν αρκεί για να επιλέξουμε: ανάμεσα σε δύο σωστούς αλγορίθμους, ο ένας μπορεί να απαντήσει σε μια στιγμή και ο άλλος να μην τερματίσει πριν η απάντηση πάψει να έχει σημασία. Το δεύτερο ερώτημα που θέτουμε σε έναν αλγόριθμο είναι, επομένως, πόσο κοστίζει.

Το κόστος θα μπορούσε να μετρηθεί με ένα ρολόι, και η τέταρτη παράγραφος θα το κάνει. Όμως ο χρόνος μιας εκτέλεσης εξαρτάται από το μηχάνημα, από τον μεταγλωττιστή, από τις επιλογές του και από ό,τι κάνει ο υπολογιστής την ίδια στιγμή· από αυτόν δεν έπεται τίποτα για τον αλγόριθμο σε άλλο μηχάνημα. Αυτό που δεν εξαρτάται από τίποτα από αυτά είναι το πλήθος των βημάτων που κάνει ο αλγόριθμος. Από αυτό έπεται η πρώτη απόφαση του μαθήματος: να μετράμε το κόστος απαριθμώντας, και να αφήσουμε το ρολόι για να ελέγξουμε την απαρίθμηση.

Το μέγεθος και η κυρίαρχη πράξη

Η απαρίθμηση όλων των βημάτων (κάθε πρόσθεσης, κάθε σύγκρισης, κάθε αύξησης του δείκτη, κάθε πρόσβασης στη μνήμη) θα ήταν κουραστική και άχρηστη, γιατί σχεδόν όλα συνοδεύουν ένα κύριο βήμα σε σταθερή αναλογία. Επιλέγουμε, επομένως, την κυρίαρχη πράξη: εκείνη που εκτελείται τουλάχιστον τόσες φορές όσες οποιαδήποτε άλλη, με ακρίβεια σταθερού παράγοντα, και που γι’ αυτό αντιπροσωπεύει όλες. Στο άθροισμα των στοιχείων ενός διανύσματος είναι η πρόσθεση· στην αναζήτηση ενός μεγίστου, η σύγκριση· σε έναν έλεγχο πρώτου, η διαίρεση. Το πλήθος των εκτελέσεών της εκφράζεται ως συνάρτηση του μεγέθους εισόδου, που το ονομάζουμε $n$: το πλήθος των στοιχείων του διανύσματος, ο αριθμός που ελέγχεται, το πλήθος των ψηφίων.

Ένας απλός βρόχος που διατρέχει ένα διάνυσμα $n$ στοιχείων και κάνει με το καθένα σταθερή ποσότητα εργασίας εκτελεί την κυρίαρχη πράξη του $n$ φορές. Η εύρεση του μεγίστου ενός μη κενού διανύσματος, αντίθετα, ξεκινά με το πρώτο στοιχείο ως υποψήφιο και συγκρίνει καθένα από τα υπόλοιπα: $n - 1$ συγκρίσεις. Η διαφορά ανάμεσα σε $n$ και $n - 1$ είναι πραγματική, αλλά, όπως θα φανεί στην τρίτη παράγραφο, δεν αλλάζει τίποτα από όσα έχουν σημασία.

Η χειρότερη περίπτωση

Μερικοί αλγόριθμοι δεν εκτελούν πάντα το ίδιο πλήθος πράξεων με δεδομένα του ίδιου μεγέθους. Η αναζήτηση μιας τιμής σε ένα διάνυσμα, διατρέχοντάς το ώσπου να τη βρει, κάνει μία μόνο σύγκριση αν η τιμή βρίσκεται στην πρώτη θέση και $n$ αν δεν υπάρχει. Για να μιλήσουμε για το κόστος της επιλέγουμε μία από τις δύο καταστάσεις, και η συνήθης επιλογή είναι η χειρότερη περίπτωση: το μέγιστο πλήθος πράξεων ανάμεσα σε όλες τις εισόδους μεγέθους $n$. Ο λόγος είναι ο ίδιος για τον οποίο μια σύμβαση γράφεται για όλες τις εισόδους που ικανοποιούν την προσυνθήκη: η χειρότερη περίπτωση είναι εγγύηση, και η καλύτερη, ελπίδα. Έτσι η γραμμική αναζήτηση κοστίζει $n$ συγκρίσεις στη χειρότερη περίπτωση, και όταν το μάθημα αυτό λέει «το κόστος» χωρίς άλλο προσδιορισμό, εννοεί το κόστος της χειρότερης περίπτωσης.

Εμφωλευμένοι βρόχοι

Το μάθημα Βρόχοι δίδαξε πώς μετρώνται οι γύροι δύο εμφωλευμένων βρόχων. Αν ο εσωτερικός κάνει πάντα $m$ γύρους για καθέναν από τους $n$ γύρους του εξωτερικού, το εσωτερικό σώμα εκτελείται $n \cdot m$ φορές. Αν ο εσωτερικός εξαρτάται από τον εξωτερικό, αθροίζουμε γραμμή προς γραμμή. Η περίπτωση που εμφανίζεται συχνότερα όταν δουλεύουμε με συλλογές είναι εκείνη των όλων των ζευγών: να συγκρίνουμε κάθε στοιχείο με καθένα από όσα το ακολουθούν, όπως όταν ψάχνουμε αν ένα διάνυσμα έχει διπλότυπα.

#include <print>​int main(){    for (int n{10}; n <= 10'000; n *= 10) {        long long comparisons{0};        for (int i{0}; i < n; ++i) {            for (int j{i + 1}; j < n; ++j) {                ++comparisons;            }        }        std::println("n = {:>6}: {:>10} συγκρίσεις, n(n - 1)/2 = {}",                     n, comparisons, static_cast<long long>(n) * (n - 1) / 2);    }}

n =     10:         45 συγκρίσεις, n(n - 1)/2 = 45n =    100:       4950 συγκρίσεις, n(n - 1)/2 = 4950n =   1000:     499500 συγκρίσεις, n(n - 1)/2 = 499500n =  10000:   49995000 συγκρίσεις, n(n - 1)/2 = 49995000

Ο μετρητής παίρνει τη θέση της σύγκρισης που θα έκανε ο πραγματικός αλγόριθμος. Στον γύρο $i$ του εξωτερικού, ο εσωτερικός πηγαίνει από $i + 1$ έως $n - 1$ και κάνει $n - 1 - i$ γύρους· έτσι το σύνολο είναι $(n - 1) + (n - 2) + \cdots + 1 + 0$, το άθροισμα του μαθήματος Βρόχοι:

Η έξοδος επιβεβαιώνει τον τύπο για κάθε μέγεθος. Ο μετρητής είναι long long γιατί από $n$ περίπου εξήντα πέντε χιλιάδες και πάνω το πλήθος των ζευγών ξεπερνά το μέγιστο του int (των 32 bit σε αυτή την πλατφόρμα), και ο τύπος πολλαπλασιάζει μετά τη μετατροπή για τον ίδιο λόγο: ο μετρητής ενός τετραγωνικού αλγορίθμου υπερχειλίζει πολύ νωρίτερα από τα δεδομένα.

Ας παρατηρήσουμε ήδη αυτό που θα γενικεύσει η τρίτη παράγραφος: όταν το $n$ πολλαπλασιάζεται επί 10, οι συγκρίσεις πολλαπλασιάζονται περίπου επί 100. Με δέκα δεδομένα, 45 συγκρίσεις· με δέκα χιλιάδες, σχεδόν πενήντα εκατομμύρια.