Απλά στο γέμισμα του διδιάστατου πίνακα χρησιμοποιείς Ν στοιχεία. Άρα γίνεται γραμμικά. Γενικά κάθε είσοδος στοιχείων δε μπορεί παρα να είναι γραμμική.
Τώρα για το bubblesort γίνονται (n-1)+(n-2)+2+1 πράξεις. Άρα συνολικά (n(n-1))/2 πράξεις που ασυμπτωτικά είναι Ο(n²).
Τώρα για την πολυπλοκότητα γενικά.
Ένας απλός ορισμός για την πολυπλοκότητα θα μπορούσε να είναι ο παρακάτω:
Πολυπλοκότητα ενός αλγορίθμου με είσοδο Ν στοιχείων ορίζεται ως ο χρόνος/χώρος (ή γενικα οποιοδήποτε χαρακτηριστικό επιθυμούμε) που χρειαζεται ο αλγόριθμος για να εκτελεστεί συναρτήσει του μεγέθους εισόδου.
Έτσι όταν έχουμε για παράδειγμα τον παρακάτω αλγόριθμο:
- Κώδικας: Επιλογή όλων
ΑΛΓΟΡΙΘΜΟΣ Χ (είσοδος Ν στοιχεία)
χ = 1;
υ = 2;
Εμφάνισε χ + υ;
Είναι προφανές ότι ο αλγόριθμος αυτός αν και έχει Ν στοιχεία θα εκτελείτε πάντα σε 3 βήματα, όσες και οι εντολές του αλγορίθμου. Επομένως η πολυπλοκότητά του θα είναι σταθερή αφού δεν εξαρτάται απ το Ν. (Δε να ανακατέψω ακόμα ασυμπτωτικούς συμβολισμούς.)
Ο αλγόριθμος εισαγωγής στοιχείων στον πίνακα είναι όντως γραμμικός, γιατί με είσοδο Ν στοιχεία θα πραγματοποιηθούν Ν πράξεις για την εκτέλεσή του.
Τώρα αν υποθέσουμε ότι έχουμε τον παρακάτω αλγόριθμο:
- Κώδικας: Επιλογή όλων
ΑΛΓΟΡΙΘΜΟΣ Υ (είσοδος Ν στοιχεία)
Για i απο 1 μεχρι Ν
Για j από 1 μέχρι Ν
ΕΚΤΕΛΕΣΕ ΚΑΠΟΙΑ ΠΡΑΞΗ ΠΑΝΩ ΣΤΑ ΔΕΔΟΜΕΝΑ ΕΙΣΟΔΟΥ ΜΑΣ.
Είναι προφανές ότι ενώ έχουμε είσοδο Ν στοιχεία ο αλγόριθμός μας θα κάνει Ν² βήματα για να φέρει σε πέρας τον υπολογισμό μας. Είναι δηλαδή τετραγωνικής πολυπλοκότητας ως προς το Ν.
Αν τώρα πάρουμε έναν αλγόριθμου που θα υπολογίζει όλες τις δυνατές μεταθέσεις Ν στοιχείων (οι οποίες είναι Ν!) θα χρειαστούν σίγουρα και τουλάχιστον Ν! βήματα μόνο για την εμφάνιση των μεταθέσεων. Άρα είναι εκθετικής πολυπλοκότητας (και καλύτερα μη δοκιμάσει κανείς να δώσει είσοδο πάνω από 15 στοιχεία.
).
Για τυχών διευκρινήσεις μη διστάσεις να ρωτήσεις.
