Στόχοι: μετά από αυτό το κεφάλαιο θα μπορείτε να εξηγείτε τι μετρά η χρονική και η χωρική πολυπλοκότητα ενός αλγορίθμου· να διαβάζετε τους συμβολισμούς \(O\), \(\Omega\) και \(\Theta\) και να κατατάσσετε τις συνηθισμένες κλάσεις πολυπλοκότητας· να εκτιμάτε την πολυπλοκότητα βρόχων, εμφωλευμένων βρόχων και αναδρομικών συναρτήσεων· και να χρησιμοποιείτε τον προεπεξεργαστή (
#include,#define,#if,#ifdef,gcc -E,-D).Προαπαιτούμενα: Κεφάλαιο 0, Κεφάλαιο 11, Κεφάλαιο 12, Κεφάλαιο 14
Χρόνος μελέτης: ~2 ώρες
Η διάλεξη έχει δύο μέρη. Στο πρώτο μαθαίνουμε να συγκρίνουμε αλγορίθμους με την
πολυπλοκότητα: πώς μεγαλώνει ο χρόνος εκτέλεσης και η μνήμη που χρειάζονται
καθώς μεγαλώνει το μέγεθος του προβλήματος. Ο συμβολισμός Big-O μάς επιτρέπει να
αγνοούμε σταθερές και λεπτομέρειες του μηχανήματος και να κρατάμε μόνο τον ρυθμό
αύξησης. Στη συνέχεια εφαρμόζουμε την ιδέα σε προγράμματα που έχουμε ήδη δει (βρόχοι,
atoi, strlen, strcmp, αναδρομή) και βλέπουμε ότι ένα καλύτερο σκεπτικό μπορεί
να ρίξει την πολυπλοκότητα από \(O(n)\) σε \(O(\sqrt{n})\). Στο δεύτερο μέρος γνωρίζουμε
τον προεπεξεργαστή, το πρώτο στάδιο του gcc, που μετασχηματίζει τον πηγαίο
κώδικα πριν από τη μεταγλώττιση με τις οδηγίες #include, #define και τις οδηγίες
μεταγλώττισης υπό συνθήκη.
Για να συγκρίνουμε δύο αυτοκίνητα κοιτάμε μετρήσιμα χαρακτηριστικά: τελική ταχύτητα, επιτάχυνση, κατανάλωση. Για να συγκρίνουμε δύο αλγορίθμους χρειαζόμαστε επίσης ένα μέτρο. Η πολυπλοκότητα (complexity) είναι ένα μέτρο εκτίμησης της απόδοσης ενός αλγορίθμου ως συνάρτηση του μεγέθους του προβλήματος που λύνει. Δύο είναι οι βασικές μετρικές:
Αν \(n\) είναι το μέγεθος του προβλήματος (το πλήθος των στοιχείων ενός πίνακα, το μήκος μιας συμβολοσειράς, η τιμή ενός αριθμού), θέλουμε να εκφράσουμε τον χρόνο εκτέλεσης ως \(t = f(n)\).
Ο χρόνος σε δευτερόλεπτα δεν είναι καλό μέτρο: το ίδιο πρόγραμμα κάνει ένα λεπτό σε έναν αργό υπολογιστή και δευτερόλεπτα σε έναν γρήγορο. Γι’ αυτό μετράμε βήματα (πόσες φορές εκτελείται ένας βρόχος, πόσες κλήσεις γίνονται) και μας ενδιαφέρει πώς αυξάνονται όταν αυξάνεται το \(n\), όχι ο ακριβής αριθμός τους. Η θεωρία της πολυπλοκότητας είναι ολόκληρος κλάδος της πληροφορικής· ένας από τους πιο γνωστούς ερευνητές του είναι ο Χρίστος Παπαδημητρίου, συν-συγγραφέας και του κόμικ Logicomix.
Οι κλάσεις πολυπλοκότητας ορίζονται με τρεις συμβολισμούς. Για δύο συναρτήσεις \(f\) και \(g\) του μεγέθους \(n\):
Διαβάστε τον ορισμό του \(O\) ως εξής: από κάποιο σημείο \(n_0\) και μετά, η \(g\) δεν ξεπερνά ποτέ ένα σταθερό πολλαπλάσιο της \(f\). Πριν από το \(n_0\) μπορεί να συμβαίνει οτιδήποτε· οι μικρές είσοδοι δεν μετράνε. Η σταθερά \(c\) «απορροφά» τους σταθερούς παράγοντες: ένας βρόχος που κάνει \(n/2\) ή \(3n + 5\) βήματα είναι και οι δύο \(O(n)\). Το \(\Omega\) λέει το αντίστροφο (η \(g\) μεγαλώνει τουλάχιστον όσο η \(f\)), και το \(\Theta\) ότι ισχύουν και τα δύο, δηλαδή η \(g\) μεγαλώνει ακριβώς με τον ρυθμό της \(f\). Στην πράξη, όταν λέμε «ο αλγόριθμος είναι \(O(n)\)», εννοούμε συνήθως το πιο σφικτό άνω όριο που ξέρουμε.
Η γραφική παράσταση των διαφανειών το δείχνει: οι καμπύλες \(f(x)\) και \(c \cdot g(x)\) διασταυρώνονται αρκετές φορές, αλλά μετά από ένα σημείο \(x_0\) η \(c \cdot g(x)\) μένει πάντα πάνω από την \(f(x)\), άρα \(f(x) = O(g(x))\).
Οι συνηθισμένες κλάσεις, από την ταχύτερη στην πιο αργή, είναι:
\[O(1) < O(\log n) < O(\sqrt{n}) < O(n) < O(n \log n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)\]| Κλάση | Όνομα | Παράδειγμα από τη διάλεξη |
|---|---|---|
| \(O(1)\) | σταθερή (constant) | υπολογισμός βαθμού με έναν τύπο |
| \(O(\log n)\) | λογαριθμική (logarithmic) | κατοπτρικός αριθμός (ψηφία του \(n\)) |
| \(O(\sqrt{n})\) | τετραγωνική ρίζα | άθροισμα τέλειων τετραγώνων, 2η εκδοχή |
| \(O(n)\) | γραμμική (linear) | strlen, atoi, παραγοντικό |
| \(O(n \log n)\) | log-linear | (καλές ταξινομήσεις, Κεφάλαιο 17) |
| \(O(n^2)\) | τετραγωνική (quadratic) | μέγιστο σε πίνακα \(n \times n\) |
| \(O(n^3)\) | κυβική, πολυωνυμική | τρεις εμφωλευμένοι βρόχοι |
| \(O(2^n)\) | εκθετική (exponential) | αναδρομικό Fibonacci |
| \(O(n!)\) | παραγοντική | όλες οι διατάξεις \(n\) στοιχείων |
Οι γραφικές παραστάσεις των διαφανειών δείχνουν πόσο γρήγορα απομακρύνονται οι καμπύλες: για \(n = 100\) η \(\log_2 n\) είναι περίπου 7 και η \(\sqrt{n}\) είναι 10, ενώ η \(n^2\) είναι 10.000 και η \(2^n\) έχει 31 ψηφία. Οι αλγόριθμοι μέχρι το πολυωνυμικό επίπεδο είναι συνήθως πρακτικοί· οι εκθετικοί και οι παραγοντικοί γίνονται άχρηστοι ήδη για μερικές δεκάδες στοιχεία.
Μερικοί απλοί κανόνες καλύπτουν όλα τα παραδείγματα της διάλεξης:
i += 2 κάνει \(n/2\) επαναλήψεις, που είναι πάλι \(O(n)\).n /= 10):
τρέχει τόσες φορές όσα τα ψηφία, \(O(\log n)\).Για τη μνήμη μετράμε ό,τι μεγαλώνει με το \(n\): έναν πίνακα \(n\) θέσεων (π.χ. με
malloc) και, στην αναδρομή, τα πλαίσια στη στοίβα (stack): κάθε ενεργή κλήση
κρατά τις δικές της τοπικές μεταβλητές, οπότε βάθος αναδρομής \(n\) σημαίνει \(O(n)\)
μνήμη. Σταθερό πλήθος μεταβλητών είναι \(O(1)\) χώρος.
Προσέξτε ως προς τι μετράτε: στην atoi το \(n\) είναι το πλήθος των ψηφίων, στην
mirror η τιμή του αριθμού, στην strcmp τα μήκη δύο συμβολοσειρών.
Μεταγλωττιστής (compiler) είναι ένα πρόγραμμα που μετατρέπει εντολές μιας γλώσσας
προγραμματισμού σε κώδικα μηχανής, ώστε να μπορεί να τον διαβάσει και να τον τρέξει
ο υπολογιστής (Κεφάλαιο 0). Με την εντολή
gcc hello.c -o hello ο πηγαίος κώδικας (source code) hello.c γίνεται δυαδικό
πρόγραμμα (binary program) hello.
Ο gcc δεν δουλεύει σε ένα βήμα: εσωτερικά περνά τον κώδικα από διαδοχικά στάδια. Το
πρώτο είναι ο προεπεξεργαστής (preprocessor), ένα υποσύστημα του μεταγλωττιστή
που καλείται αυτόματα πριν από την πραγματική μεταγλώττιση. Παίρνει ένα αρχείο C και
παράγει ένα άλλο αρχείο C, εφαρμόζοντας τις οδηγίες που απευθύνονται σε αυτόν.
Δουλεύει μόνο με κείμενο: δεν ξέρει τι είναι μεταβλητή ή τύπος.
flowchart LR
S["Πηγαίος κώδικας<br/>hello.c"] --> P
subgraph G["gcc"]
P["Προεπεξεργαστής"] --> C["Μεταγλώττιση"] --> L["Υπόλοιπα στάδια"]
end
L --> B["Δυαδικό πρόγραμμα<br/>hello"]
Σχήμα: ο προεπεξεργαστής είναι το πρώτο στάδιο μέσα στον gcc.
Την έξοδο του προεπεξεργαστή τη βλέπουμε με την επιλογή -E του gcc ή τρέχοντας
απευθείας το πρόγραμμα του προεπεξεργαστή, cpp:
gcc -E hello.c -o processed.c
cpp hello.c -o processed.c
Το processed.c είναι ο προεπεξεργασμένος πηγαίος κώδικας (preprocessed source
code): αυτό που πραγματικά μεταγλωττίζεται. Οι γραμμές που αρχίζουν με # στην
έξοδο (π.χ. # 1 "hello.c") είναι σημειώσεις για τον μεταγλωττιστή σχετικά με το
από ποιο αρχείο και ποια γραμμή προήλθε κάθε κομμάτι.
Όλες οι οδηγίες προς τον προεπεξεργαστή (preprocessor directives) αρχίζουν με το
σύμβολο #. Οι πιο συνηθισμένες είναι:
#include: εισαγωγή αρχείου.#define: ορισμός μακροεντολών.#if, #else, #elif, #endif: μεταγλώττιση υπό συνθήκη.#ifdef, #ifndef: έλεγχος αν έχει οριστεί μια μακροεντολή.Δεν τελειώνουν με ;, γιατί δεν είναι εντολές της C.
#includeΗ #include <file.h> εισάγει τα περιεχόμενα του αρχείου file.h στο σημείο όπου
γράφτηκε η οδηγία, σαν να τα είχαμε αντιγράψει εκεί. Τα αρχεία αυτά είναι συνήθως
αρχεία επικεφαλίδας (header files) με δηλώσεις συναρτήσεων, σταθερές και
μακροεντολές· για παράδειγμα, το stdio.h δηλώνει την printf.
Πού βρίσκονται; Η μορφή με < > τα ψάχνει σε προκαθορισμένους φακέλους του
λειτουργικού (π.χ. /usr/include) ή σε φακέλους που δίνουμε με το όρισμα -I του
gcc. Η δεύτερη μορφή, #include "file.h", ψάχνει πρώτα στον φάκελο όπου
βρίσκεται το πηγαίο αρχείο και μετά στους ίδιους φακέλους με τη μορφή < >. Η πρώτη
μορφή είναι για τις βιβλιοθήκες του συστήματος, η δεύτερη για τα δικά μας αρχεία.
Η οργάνωση ενός προγράμματος σε πολλά αρχεία έρχεται στο
Κεφάλαιο 23.
#define και οι μακροεντολέςΗ #define ορίζει μακροεντολές (macros): ονόματα που ο προεπεξεργαστής
αντικαθιστά με το κείμενο που τους αντιστοιχίσαμε, όπου τα βρει ως ξεχωριστή λέξη
(όχι μέσα σε "..." ή σε σχόλια). Δύο χρήσεις:
#define TRUE 1. Κάθε TRUE γίνεται 1.#define MAX(A, B) ((A) > (B) ? (A) : (B))
Το MAX(x + 1, y) γίνεται ((x + 1) > (y) ? (x + 1) : (y)). Μοιάζει με κλήση
συνάρτησης, αλλά δεν είναι: δεν υπάρχουν τύποι ούτε κλήση, μόνο αντικατάσταση
κειμένου πριν από τη μεταγλώττιση. Γι’ αυτό:
PROD).MAX(i++, j++) αυξάνει μία από τις δύο μεταβλητές δύο φορές.Η τιμή μιας μακροεντολής μπορεί να δοθεί και από τη γραμμή εντολών, με τη σύνταξη
-DMACRO=VALUE του gcc· το σκέτο -DMACRO την ορίζει με τιμή 1. Έτσι ένα
πρόγραμμα αλλάζει συμπεριφορά χωρίς να αλλάξει ούτε γράμμα του κώδικα.
#if, #else, #endifΟι οδηγίες #if / #else / #endif μοιάζουν με το if της C, αλλά δρουν στο
επίπεδο του κώδικα: δεν αποφασίζουν τι θα εκτελεστεί, αλλά ποιες γραμμές θα
μείνουν στο αρχείο που θα μεταγλωττιστεί. Ό,τι βρίσκεται ανάμεσα σε #if και
#endif κρατιέται μόνο αν η ακέραια παράσταση μετά το #if είναι μη μηδενική· αλλιώς
κρατιέται το τμήμα του #else. Το #elif είναι συντομογραφία για #else που
περιέχει άλλο #if. Η παράσταση υπολογίζεται από τον προεπεξεργαστή, άρα πρέπει να
περιέχει σταθερές και μακροεντολές, όχι μεταβλητές του προγράμματος.
Μια συνηθισμένη χρήση είναι το #if 0 ... #endif, που «σβήνει» προσωρινά ένα κομμάτι
κώδικα χωρίς να το σβήσουμε πραγματικά.
#ifdef και #ifndefΜε το #ifdef NAME ελέγχουμε αν η μακροεντολή NAME έχει οριστεί (με #define ή
με -DNAME), ανεξάρτητα από την τιμή της· το #ifndef NAME ελέγχει το αντίθετο.
Ισοδύναμα γράφεται #if defined(NAME) και #if !defined(NAME). Τυπικές χρήσεις:
-DDEBUG και
εξαφανίζονται εντελώς από το τελικό πρόγραμμα όταν δεν το δίνουμε.#ifndef NAME_H / #define NAME_H / #endif, ώστε τα περιεχόμενά του να
συμπεριληφθούν μόνο μία φορά (δείτε το Παράρτημα του Εργαστηρίου 10).Εφαρμόζει: «Πώς εκτιμούμε την πολυπλοκότητα». Θέλουμε το γινόμενο όλων των
περιττών από το 1 μέχρι το N που διαιρούνται με το 7 (το πρόβλημα του
Κεφαλαίου 7). Ένας βρόχος με μια μεταβλητή που αυξάνεται
κατά 2 και έλεγχο για % 7 == 0:
for (product = 1, i = 1; i < N; i += 2) {
if (i % 7 == 0)
product *= i;
}
Χρόνος: \(O(N)\), χώρος: \(O(1)\). Ο βρόχος κάνει περίπου \(N/2\) επαναλήψεις, και η
σταθερά \(1/2\) δεν αλλάζει την κλάση. Ο χώρος είναι δύο μεταβλητές, όσο μεγάλο κι αν
είναι το N. (Αν το «μέχρι το N» περιλαμβάνει το N, η συνθήκη πρέπει να είναι
i <= N.)
atoiΕφαρμόζει: έναν βρόχο ανά στοιχείο. Η συνάρτηση του Κεφαλαίου 10 μετατρέπει έναν πίνακα χαρακτήρων (μόνο ψηφία) σε ακέραιο:
int atoi(char digits[]) {
int result = 0;
for (int i = 0; digits[i]; i++) {
result = 10 * result + digits[i] - '0';
}
return result;
}
Χρόνος: \(O(N)\), χώρος: \(O(1)\), όπου \(N\) το πλήθος των ψηφίων: μία επανάληψη ανά
ψηφίο και μόνο δύο τοπικές μεταβλητές. (Το όνομα atoi συμπίπτει με τη συνάρτηση
της stdlib.h· εδώ είναι δική μας υλοποίηση.)
getcharΕφαρμόζει: βρόχος ανά χαρακτήρα εισόδου. Διαδοχικές κλήσεις της getchar()
διαβάζουν διαδοχικούς χαρακτήρες (Κεφάλαιο 9). Το πρόγραμμα
ξανατυπώνει μια γραμμή και μετρά τους χαρακτήρες της:
#include <stdio.h>
int main() {
int ch, sum = 0;
printf("Enter characters: ");
while ((ch = getchar()) != '\n' && ch != EOF) {
printf("%c", ch);
sum++;
}
printf("\nTotal characters: %d\n", sum);
return 0;
}
$ echo hello | ./count
Enter characters: hello
Total characters: 5
Χρόνος: \(O(N)\), χώρος: \(O(1)\), με \(N\) το μήκος της γραμμής: το πρόγραμμα δεν αποθηκεύει τη γραμμή, κρατά μόνο τον τρέχοντα χαρακτήρα και τον μετρητή.
mallocΕφαρμόζει: χωρική πολυπλοκότητα. Με τους δείκτες μπορούμε να φτιάξουμε δυναμικούς πίνακες, το μέγεθος των οποίων αποφασίζεται τη στιγμή που τρέχει το πρόγραμμα (Κεφάλαιο 12, Κεφάλαιο 13):
int *array = malloc(N * sizeof(int));
for (int i = 0; i < N; i++)
array[i] = i * i;
Χρόνος: \(O(N)\), χώρος: \(O(N)\). Εδώ ο χώρος μεγαλώνει με το N, γιατί
δεσμεύουμε N ακεραίους. (Σε πλήρες πρόγραμμα ελέγχουμε αν η malloc επέστρεψε
NULL και καλούμε free στο τέλος.)
Εφαρμόζει: \(O(1)\). Το γνωστό μας παράδειγμα από τα Κεφάλαια 4 και 5:
// Compute grades using the class formula
int grade(int final_exam, int homework, int lab, int year) {
if (year <= 1) {
return final_exam * 50 / 100 + homework * 30 / 100 + lab * 20 / 100;
} else {
return final_exam * 70 / 100 + homework * 30 / 100;
}
}
Χρόνος: \(O(1)\), χώρος: \(O(1)\). Δεν υπάρχει βρόχος ούτε αναδρομή· ο αριθμός των πράξεων είναι ο ίδιος για κάθε είσοδο.
Εφαρμόζει: εμφωλευμένοι βρόχοι.
int find_max(int **matrix, size_t n) {
int i, j, max = -1;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
if (matrix[i][j] > max) max = matrix[i][j];
}
}
return max;
}
Χρόνος: \(O(n^2)\), χώρος: \(O(1)\). Ο εσωτερικός βρόχος τρέχει \(n\) φορές για κάθε
μία από τις \(n\) επαναλήψεις του εξωτερικού: \(n \cdot n\) συγκρίσεις. Προσέξτε ότι η
αρχική τιμή max = -1 δουλεύει μόνο αν όλα τα στοιχεία είναι μη αρνητικά· η γενική
λύση είναι max = matrix[0][0].
Εφαρμόζει: πολυπλοκότητα αναδρομής (Κεφάλαιο 11).
int factorial(int n) {
if (n == 0) return 1;
return n * factorial(n - 1);
}
Χρόνος: \(O(n)\), χώρος: \(O(n)\). Το factorial(n) κάνει μία αλυσίδα \(n + 1\)
κλήσεων. Ο χώρος δεν είναι \(O(1)\): πριν επιστρέψει η πρώτη κλήση, και οι \(n + 1\)
κλήσεις είναι ενεργές ταυτόχρονα, η καθεμία με το δικό της πλαίσιο στη στοίβα.
int fib(int n) {
if (n == 0 || n == 1) return 1;
return fib(n - 1) + fib(n - 2);
}
Χρόνος: \(O(2^n)\), χώρος: \(O(n)\). Κάθε κλήση κάνει δύο αναδρομικές κλήσεις, οπότε οι κλήσεις σχηματίζουν δέντρο που σχεδόν διπλασιάζεται σε κάθε επίπεδο, και οι ίδιες τιμές υπολογίζονται ξανά και ξανά:
flowchart TD
A["fib(4)"] --> B["fib(3)"]
A --> C["fib(2)"]
B --> D["fib(2)"]
B --> E["fib(1)"]
D --> F["fib(1)"]
D --> G["fib(0)"]
C --> H["fib(1)"]
C --> I["fib(0)"]
Σχήμα: το δέντρο κλήσεων του fib(4)· το fib(2) υπολογίζεται δύο φορές.
Η μνήμη όμως μένει \(O(n)\): σε κάθε στιγμή είναι ενεργές μόνο οι κλήσεις ενός μονοπατιού από τη ρίζα ως ένα φύλλο, και το μακρύτερο μονοπάτι έχει μήκος \(n\).
strlen και strcmpΕφαρμόζει: βρόχος ανά χαρακτήρα. Μια πιθανή υλοποίηση της strlen
(Κεφάλαιο 14):
size_t strlen(char *str) {
size_t length = 0;
while (*str++) length++;
return length;
}
Χρόνος: \(O(n)\), χώρος: \(O(1)\), όπου \(n\) το μήκος της συμβολοσειράς. Η C δεν
αποθηκεύει πουθενά το μήκος· για να το βρει, η strlen πρέπει να διατρέξει όλη τη
συμβολοσειρά μέχρι το '\0'.
int strcmp(char *str1, char *str2) {
while (*str1 && (*str1 == *str2)) {
str1++;
str2++;
}
return *str1 - *str2;
}
Χρόνος: \(O(\min(m, n))\), χώρος: \(O(1)\), για συμβολοσειρές μήκους \(n\) και \(m\). Ο βρόχος σταματά στην πρώτη διαφορά ή στο τέλος της συντομότερης, άρα δεν μπορεί να κάνει περισσότερα βήματα από το μικρότερο μήκος.
Εφαρμόζει: κλήση μέσα σε βρόχο και βελτίωση πολυπλοκότητας. Θέλουμε το άθροισμα
των τέλειων τετραγώνων στο διάστημα [low, high], με τα όρια από τη γραμμή εντολών.
Πρώτη εκδοχή: ελέγχουμε κάθε αριθμό.
int isPerfectSquare(int num) {
int root = sqrt(num);
return root * root == num;
}
// ... στη main:
int low = atoi(argv[1]);
int high = atoi(argv[2]);
int i, sum = 0;
for (i = low; i <= high; i++) {
if (isPerfectSquare(i))
sum += i;
}
Χρόνος: \(O(n)\), χώρος: \(O(1)\), όπου \(n\) το πλήθος των αριθμών του διαστήματος
(η sqrt μετράει εδώ ως ένα βήμα). Δεύτερη εκδοχή: αντί να ψάχνουμε ποιοι αριθμοί
είναι τετράγωνα, παράγουμε απευθείας τα τετράγωνα \(i^2\) για \(i\) από \(\sqrt{low}\) ως
\(\sqrt{high}\):
int low = atoi(argv[1]);
int high = atoi(argv[2]);
int i, sum = 0;
for (i = sqrt(low); i <= sqrt(high); i++)
sum += i * i;
Χρόνος: \(O(\sqrt{n})\), χώρος: \(O(1)\). Για διάστημα ενός εκατομμυρίου αριθμών ο βρόχος κάνει περίπου χίλιες επαναλήψεις αντί για ένα εκατομμύριο. Το δίδαγμα: η μεγαλύτερη βελτίωση έρχεται από καλύτερο σκεπτικό, όχι από «γρηγορότερο» κώδικα.
Προσοχή σε μια λεπτομέρεια: η ανάθεση i = sqrt(low) κόβει το δεκαδικό μέρος. Αν το
low δεν είναι τέλειο τετράγωνο, π.χ. low = 5, το i ξεκινά από το 2 και το
άθροισμα περιλαμβάνει το 4, που είναι εκτός διαστήματος. Η σωστή αρχή είναι το
μικρότερο i με i * i >= low. Και οι δύο εκδοχές χρειάζονται #include <math.h>
και μεταγλώττιση με -lm.
Εφαρμόζει: \(O(\log n)\). Η mirror επιστρέφει τον αριθμό με τα ψηφία ανάποδα
(1234 → 4321):
int mirror(int n) {
int result = 0, tmp;
while (n > 0) {
tmp = n % 10;
result = 10 * result + tmp;
n /= 10;
}
return result;
}
Χρόνος: \(O(\log n)\), χώρος: \(O(1)\). Κάθε επανάληψη διαιρεί το n με το 10, οπότε
ο βρόχος τρέχει τόσες φορές όσα είναι τα ψηφία του \(n\), δηλαδή περίπου \(\log_{10} n\).
Εδώ το «μέγεθος» είναι η τιμή του \(n\), όχι το πλήθος των ψηφίων του.
Η διάλεξη κλείνει το μέρος αυτό με ένα ανοιχτό ερώτημα: τι χρονική πολυπλοκότητα έχει ο έλεγχος αν ένας αριθμός είναι πρώτος; Σκεφτείτε μέχρι πού χρειάζεται να δοκιμάσετε διαιρέτες (δείτε την αντίστοιχη άσκηση).
PRODΕφαρμόζει: «Η οδηγία #define», gcc -E. Τι επιστρέφει το παρακάτω πρόγραμμα;
#define PROD 2*5
int main() {
return 20 / PROD;
}
Η πρώτη σκέψη είναι \(20 / 10 = 2\). Ο προεπεξεργαστής όμως αντικαθιστά κείμενο:
$ cpp prod.c
# 0 "prod.c"
# 0 "<built-in>"
# 0 "<command-line>"
# 1 "/usr/include/stdc-predef.h" 1 3 4
# 0 "<command-line>" 2
# 1 "prod.c"
int main() {
return 20 / 2*5;
}
$ gcc -o prod prod.c
$ ./prod
$ echo $?
50
Το 20 / 2*5 υπολογίζεται από αριστερά προς τα δεξιά: (20 / 2) * 5 = 50. Με
#define PROD (2*5) το αποτέλεσμα θα ήταν 2. Την τιμή που επιστρέφει η main τη
βλέπουμε με echo $? (Κεφάλαιο 1).
Αν σβήσουμε τη γραμμή #define και δώσουμε την τιμή από τη γραμμή εντολών:
$ gcc -DPROD=10 -o prod prod.c
$ ./prod
$ echo $?
2
#if 0 / #elseΕφαρμόζει: «Μεταγλώττιση υπό συνθήκη». Σε τι θα προεπεξεργαστεί το πρόγραμμα;
int main() {
#if 0
return 42;
#else
return 1;
#endif
}
$ gcc -E example.c
# 0 "example.c"
# 0 "<built-in>"
# 0 "<command-line>"
# 1 "/usr/include/stdc-predef.h" 1 3 4
# 0 "<command-line>" 2
# 1 "example.c"
int main() {
return 1;
}
Το return 42; δεν υπάρχει καν στον κώδικα που φτάνει στον μεταγλωττιστή· στη θέση
των οδηγιών και του κομματιού που αφαιρέθηκε μένουν κενές γραμμές, ώστε οι αριθμοί
γραμμών στα μηνύματα λάθους να ταιριάζουν με το αρχικό αρχείο.
#ifdef DEBUGΕφαρμόζει: «Οι οδηγίες #ifdef και #ifndef».
#define DEBUG
#ifdef DEBUG
printf("debugging is on\n");
#else
printf("debugging is off\n");
#endif
#ifndef DEBUG
printf("optimizations are on\n");
#endif
Με το #define DEBUG στην αρχή τυπώνεται μόνο debugging is on. Αν σβήσουμε αυτή τη
γραμμή, τυπώνονται debugging is off και optimizations are on. Αντί να αλλάζουμε
τον κώδικα, μπορούμε να αφήσουμε έξω το #define DEBUG και να μεταγλωττίζουμε με
gcc -DDEBUG όταν θέλουμε τα μηνύματα.
strlen είναι \(O(n)\) και η strcmp \(O(\min(m, n))\).gcc· μετασχηματίζει το κείμενο του
προγράμματος πριν από τη μεταγλώττιση, και την έξοδό του τη βλέπουμε με gcc -E ή
cpp.#: #include, #define, #if/#else/#elif/
#endif, #ifdef/#ifndef.#include <...> ψάχνει στους φακέλους του συστήματος και του -I· το
#include "..." πρώτα στον φάκελο του πηγαίου αρχείου.#define PROD 2*5 το 20 / PROD κάνει 50.-DMACRO=VALUE δίνουμε τιμή σε μακροεντολή από τη γραμμή εντολών, και με
#ifdef / #ifndef ενεργοποιούμε κώδικα, π.χ. μηνύματα αποσφαλμάτωσης.| Ελληνικά | English | Σύντομος ορισμός |
|---|---|---|
| πολυπλοκότητα | complexity | Μέτρο απόδοσης ενός αλγορίθμου ως συνάρτηση του μεγέθους του προβλήματος. |
| χρονική / χωρική πολυπλοκότητα | time / space complexity | Πώς αυξάνεται ο χρόνος / η μνήμη με το \(n\). |
| άνω όριο | upper bound, Big-O | \(g = O(f)\): η \(g\) δεν ξεπερνά τη \(c \cdot f\) για μεγάλα \(n\). |
| κάτω όριο | lower bound, \(\Omega\) | \(g = \Omega(f)\): η \(g\) είναι τουλάχιστον \(c \cdot f\) για μεγάλα \(n\). |
| τάξη μεγέθους | order of growth, \(\Theta\) | Ισχύουν ταυτόχρονα \(O\) και \(\Omega\). |
| σταθερή / λογαριθμική / γραμμική | constant / logarithmic / linear | \(O(1)\) / \(O(\log n)\) / \(O(n)\). |
| τετραγωνική / εκθετική | quadratic / exponential | \(O(n^2)\) / \(O(2^n)\). |
| μεταγλωττιστής | compiler | Μετατρέπει πηγαίο κώδικα σε κώδικα μηχανής. |
| προεπεξεργαστής | preprocessor | Πρώτο στάδιο του μεταγλωττιστή· μετασχηματίζει το κείμενο του κώδικα. |
| οδηγία προεπεξεργαστή | preprocessor directive | Γραμμή που αρχίζει με #, π.χ. #include. |
| αρχείο επικεφαλίδας | header file | Αρχείο .h με δηλώσεις, που εισάγεται με #include. |
| μακροεντολή | macro | Όνομα (με ή χωρίς παραμέτρους) που αντικαθίσταται με κείμενο. |
| μεταγλώττιση υπό συνθήκη | conditional compilation | Κράτημα ή αφαίρεση κώδικα με #if / #ifdef. |
sieve.c (μέγεθος πίνακα με #define, πρώτοι αριθμοί)·
Εργαστήριο 10: Παράρτημα
«Οργάνωση προγράμματος σε πολλαπλά αρχεία» (αρχεία επικεφαλίδας, include guards).man cpp, man gcc (επιλογές -E, -D, -I).i += 2 είναι \(O(n/2)\)». Οι σταθερές παραλείπονται: είναι \(O(n)\).factorial δεν έχει πίνακα, αλλά χρειάζεται
\(O(n)\) μνήμη για τις \(n\) ενεργές κλήσεις.for (i = 0; i < strlen(s); i++) καλεί την strlen
σε κάθε επανάληψη, άρα γίνεται \(O(n^2)\). Υπολογίστε το μήκος μία φορά πριν από τον
βρόχο.#define PROD 2*5 και 20 / PROD δίνει 50, όχι
2· #define SQUARE(X) X * X και SQUARE(a + 1) δίνει a + 1 * a + 1. Γράψτε
(2*5) και ((X) * (X)).MAX(i++, j++) αυξάνει μία μεταβλητή
δύο φορές. Μην περνάτε ++, -- ή κλήσεις συναρτήσεων σε μακροεντολές.; στο τέλος του #define. #define N 10; κάνει το int a[N]; να γίνει
int a[10;]; και ο gcc βγάζει συντακτικό λάθος σε γραμμή που φαίνεται σωστή.
Κοιτάξτε την έξοδο του gcc -E.undefined reference to 'sqrt'. Οι συναρτήσεις της math.h χρειάζονται
-lm στη μεταγλώττιση: gcc squares.c -o squares -lm.i = sqrt(low) κόβει προς τα κάτω και προσθέτει τετράγωνο εκτός διαστήματος
όταν το low δεν είναι τέλειο τετράγωνο (π.χ. low = 5 προσθέτει το 4).#include "stdio.h" αντί για <stdio.h> (δουλεύει, αλλά ψάχνει πρώτα στον
φάκελό σας) ή #include <myfile.h> για δικό σας αρχείο (fatal error:
myfile.h: No such file or directory, εκτός αν δώσετε -I.).Από τα Kahoot των διαλέξεων: οι ερωτήσεις όπου μια λάθος απάντηση μάζεψε πολλές ψήφους, με το ποσοστό σωστών απαντήσεων.
n
με σώμα \(O(1)\);3factorial έχει χωρική πολυπλοκότητα \(O(n)\) ενώ ο επαναληπτικός
υπολογισμός έχει \(O(1)\);4MAX(a, b + 1) με τον ορισμό της διάλεξης;5#include <file.h> και #include "file.h";6#ifdef DEBUG (χωρίς τη γραμμή
#define DEBUG) ώστε να τυπώσει debugging is on;7Ερωτήσεις που παίχτηκαν στις διαλέξεις, με το ποσοστό των φοιτητών που απάντησαν σωστά.
slides-lec15-complexity-atoislides-lec15-complexity-find-max-2dslides-lec15-complexity-gradeslides-lec15-complexity-mallocslides-lec15-complexity-odd-multiples-of-7slides-lec15-complexity-strlenslides-lec15-getchar-countslides-lec15-macro-prodslides-lec15-preprocess-if-elseslides-lec15-complexity-factorialslides-lec15-complexity-fibonaccislides-lec15-complexity-mirrorslides-lec15-complexity-perfect-squaresslides-lec15-complexity-strcmpslides-lec15-prime-complexityhw-2023-hw1-mirrorhw-2024-hw1-factorexam-2023-fall-ex7-q3lab-lab05-fibexam-2025-jan-q5exam-2024-sep-q3exam-2024-sep-q5exam-2025-sep-q4exam-2026-sep-q4exam-2024-jul-q4exam-2025-jan-q4exam-2026-jan-q4exam-2023-dec-q4exam-2024-jul-q3exam-2026-jun-q3exam-2026-sep-q5Ο χρόνος εκτέλεσης και ο χώρος μνήμης. Τα δευτερόλεπτα εξαρτώνται από το μηχάνημα· μας ενδιαφέρει πώς αυξάνονται τα βήματα με το \(n\). ↩
Ναι, με \(c = 6\) για \(n > 3\). Όχι· το \(n^2\) ξεπερνά κάθε \(c \cdot n\). ↩
Χρόνος \(O(n^2)\), χώρος \(O(1)\). ↩
Κάθε αναδρομική κλήση κρατά πλαίσιο στη στοίβα, και οι \(n + 1\) κλήσεις είναι ενεργές ταυτόχρονα· ο βρόχος χρησιμοποιεί σταθερό πλήθος μεταβλητών. ↩
((a) > (b + 1) ? (a) : (b + 1)). ↩
Η μορφή με < > ψάχνει στους φακέλους του συστήματος και του -I· η μορφή με " " ψάχνει πρώτα στον φάκελο του πηγαίου αρχείου. ↩
gcc -DDEBUG prog.c -o prog. ↩