Στόχοι: μετά από αυτό το κεφάλαιο θα μπορείτε να εκτιμάτε τη χρονική και τη χωρική πολυπλοκότητα μιας μικρής συνάρτησης· να ανταλλάσσετε χρόνο με μνήμη (ή το αντίστροφο) όταν ψάχνετε διπλότυπα σε πίνακα· να χειρίζεστε τα ψηφία ενός αριθμού με
/και%· να ξεχωρίζετε ταchar *array[],char **arrayκαιchar array[10][10]· να «επιστρέφετε» πολλές τιμές μέσω δεικτών· να βγαίνετε από εμφωλευμένους βρόχους· να φτιάχνετε δισδιάστατο πίνακα στον σωρό· να γράφετε αποδοτική αναδρομική Fibonacci· και να μετράτε μνήμη και να εξετάζετε δυαδικά αρχεία για την Εργασία #1.Προαπαιτούμενα: Κεφάλαιο 10, Κεφάλαιο 11, Κεφάλαιο 12, Κεφάλαιο 13, Κεφάλαιο 15
Χρόνος μελέτης: ~2,5 ώρες
Η διάλεξη αυτή είναι μια διάλεξη εξάσκησης, με την ίδια λογική με το Κεφάλαιο 7: δεν εισάγει νέα στοιχεία της γλώσσας, αλλά θέτει μια σειρά από μικρά προβλήματα «Θέλω μια συνάρτηση που … Πώς;» και τα λύνει ζωντανά, με εθελοντές από το ακροατήριο. Τα προβλήματα ανακυκλώνουν όλη την ύλη ως τώρα: πίνακες, ψηφία αριθμών, συμβολοσειρές, δείκτες, δισδιάστατους πίνακες, τον σωρό και την αναδρομή. Το νέο στοιχείο είναι η ερώτηση που συνοδεύει σχεδόν κάθε πρόβλημα: «Χρονική και χωρική πολυπλοκότητα;» Μετά το Κεφάλαιο 15 δεν αρκεί μια λύση που δουλεύει· θέλουμε να ξέρουμε πόσο κοστίζει και αν υπάρχει καλύτερη. Η διάλεξη κλείνει με πρακτικές απαντήσεις σε ερωτήσεις για την Εργασία #1.
Η επίλυση προβλημάτων είναι δεξιότητα, όχι γνώση που αποστηθίζεται: το «δεν δουλεύει, γιατί;» και το εξίσου ύπουλο «δουλεύει, γιατί;» απαντώνται μόνο με εξάσκηση. Οι διαφάνειες δίνουν τέσσερις λόγους: εξάσκηση, γνώση (κάθε λυμένο πρόβλημα γίνεται μοτίβο για το επόμενο), εφαρμογές (τα ίδια μοτίβα εμφανίζονται σε εργασίες, εξετάσεις και πραγματικό κώδικα) και δημιουργία / σύνθεση ιδεών. Γι’ αυτό πολλά προβλήματα της διάλεξης είναι γνωστά από προηγούμενα κεφάλαια· η αξία είναι να τα λύνετε γρήγορα και να τα αναλύετε.
flowchart LR
A["Κατανοώ το πρόβλημα<br/>(παραδείγματα, ακραίες περιπτώσεις)"] --> B["Απλή, σωστή λύση"]
B --> C["Πολυπλοκότητα<br/>χρόνου και μνήμης"]
C --> D{"Υπάρχει καλύτερη;"}
D -- "ναι" --> B
D -- "όχι" --> E["Τι μπορεί να πάει στραβά;"]
Σχήμα: η σειρά ερωτήσεων που θέτει η διάλεξη για κάθε πρόβλημα.
Η χρονική πολυπλοκότητα (time complexity) μετρά πώς μεγαλώνει το πλήθος των βημάτων όσο μεγαλώνει η είσοδος \(n\)· η χωρική πολυπλοκότητα (space complexity) μετρά πόση επιπλέον μνήμη χρειάζεται, πέρα από την είσοδο. Και οι δύο γράφονται με τον συμβολισμό \(O\) του Κεφαλαίου 15. Πρακτικοί κανόνες:
Συχνά μια λύση γίνεται ταχύτερη αν ξοδέψει μνήμη, ή το αντίστροφο: αυτό είναι το αντιστάθμισμα χρόνου–μνήμης (time–space tradeoff). Το «βρες το στοιχείο που εμφανίζεται δύο φορές» το δείχνει καθαρά:
| Ιδέα | Χρόνος | Μνήμη |
|---|---|---|
| Σύγκριση κάθε ζεύγους με δύο εμφωλευμένους βρόχους | \(O(n^2)\) | \(O(1)\) |
| Ταξινόμηση και σύγκριση γειτονικών στοιχείων | \(O(n \log n)\) | ανάλογα με την ταξινόμηση |
| Πίνακας «το έχω δει» με μία θέση ανά δυνατή τιμή | \(O(n)\) | \(O(k)\), \(k\) το εύρος των τιμών |
Η τρίτη ιδέα δουλεύει μόνο όταν οι τιμές έχουν μικρό, γνωστό εύρος (π.χ. 0–999): για
τυχαίους int θα χρειαζόταν \(2^{32}\) θέσεις. Η ταξινόμηση έρχεται στο
Κεφάλαιο 17.
Μερικές φορές μια ιδιότητα του προβλήματος δίνει και τα δύο. Όταν «όλα τα στοιχεία
είναι διπλά εκτός από ένα», αρκεί το αποκλειστικό Ή (XOR, ^) του
Κεφαλαίου 4, χάρη στις ιδιότητες
Το XOR όλων των στοιχείων μηδενίζει κάθε ζευγάρι, όποια σειρά κι αν έχουν, και αφήνει μόνο το μοναδικό: \(O(n)\) χρόνος, \(O(1)\) μνήμη.
Για μη αρνητικό ακέραιο n, το n % 10 είναι το τελευταίο ψηφίο και το n / 10
ο αριθμός χωρίς αυτό (123 → 3 και 12). Επαναλαμβάνοντας μέχρι n == 0 παίρνουμε τα
ψηφία από δεξιά προς τα αριστερά. Το αντίστροφο μοτίβο, r = 10 * r + digit, σπρώχνει
ό,τι έχουμε μία θέση αριστερά και προσθέτει ψηφίο στις μονάδες. Τα δύο μαζί δίνουν την
αντιστροφή ψηφίων, και από εκεί τον έλεγχο παλινδρομικού αριθμού (palindrome:
διαβάζεται ίδια και από τις δύο μεριές, π.χ. 12321). Ο βρόχος κάνει τόσα βήματα όσα τα
ψηφία, δηλαδή \(O(\log n)\).
Δύο προσοχές: ο αντεστραμμένος αριθμός μπορεί να μη χωρά σε int (το 1000000009 χωρά,
το 9000000001 όχι)· και για αρνητικό n το n % 10 είναι αρνητικό στη C (το πρόσημο
ακολουθεί τον διαιρετέο), οπότε το -45 γίνεται -54.
atoi και τα όριά τηςΤο ίδιο μοτίβο 10 * result + digit, με digit = c - '0', μετατρέπει μια
συμβολοσειρά ψηφίων σε ακέραιο, σε \(O(n)\) χρόνο και \(O(1)\) μνήμη
(Κεφάλαιο 11). Στο «Τι μπορεί να πάει στραβά;» η
απάντηση είναι οι υποθέσεις που ο καλών μπορεί να παραβιάσει:
"-5" ή το "12a" δίνουν σκουπίδια χωρίς ένδειξη λάθους, και ο
καλών δεν ξεχωρίζει το "0" από μια αποτυχία.INT_MAX (2147483647) ο αριθμός δεν χωρά· η υπερχείλιση
προσημασμένου ακεραίου είναι απροσδιόριστη συμπεριφορά.'\0'. Ο βρόχος διαβάζει εκτός ορίων.atoi υπάρχει ήδη στη stdlib.h και οι δύο συγκρούονται.Για το άθροισμα των τέλειων τετραγώνων στο \([a, b]\), η πρώτη ιδέα ελέγχει κάθε αριθμό του διαστήματος: \(O(b - a)\) έλεγχοι. Όμως έως το \(b\) υπάρχουν μόνο \(\lfloor\sqrt{b}\rfloor\) τετράγωνα· αν διατρέξουμε τα \(k = 1, 2, \dots\) και προσθέσουμε τα \(k^2\) του διαστήματος, κάνουμε \(O(\sqrt{b})\) βήματα: για \(b = 10^{12}\), ένα εκατομμύριο αντί για ένα τρισεκατομμύριο. Ο τύπος
\[1^2 + 2^2 + \dots + m^2 = \frac{m(m+1)(2m+1)}{6}\]δίνει την απάντηση σε σταθερό χρόνο, ως διαφορά των αθροισμάτων για
\(m = \lfloor\sqrt{b}\rfloor\) και \(m = \lfloor\sqrt{a-1}\rfloor\). Το δίδαγμα: πριν
γράψετε βρόχο, σκεφτείτε αν η δομή του προβλήματος σας γλιτώνει από το να επισκεφθείτε
όλη την είσοδο. Τα αθροίσματα μεγαλώνουν γρήγορα, οπότε χρειάζεται long long.
char *array[], char **array και char array[10][10]Και με τις τρεις γράφουμε array[i][j], αλλά περιγράφουν διαφορετικά πράγματα στη
μνήμη (Κεφάλαιο 12):
| Δήλωση | Τι είναι | sizeof (64 bit) |
|---|---|---|
char *array[3] |
πίνακας από 3 pointers, ο καθένας προς δική του συμβολοσειρά | 24 |
char **array |
μία μεταβλητή δείκτη, προς ένα char * |
8 |
char array[10][10] |
100 συνεχόμενοι χαρακτήρες σε 10 γραμμές· κανένας pointer | 100 |
flowchart LR
PP["char **pp"] --> p0
subgraph P["char *array[3]"]
p0["array[0]"]
p1["array[1]"]
p2["array[2]"]
end
p0 --> s0["h e l l o \0"]
p1 --> s1["w o r l d \0"]
p2 --> s2["! \0"]
Σχήμα: πίνακας από pointers και ένας char ** προς το πρώτο στοιχείο του· ο
char array[10][10] δεν έχει βέλη, μόνο 100 συνεχόμενα bytes.
char *array[] σε έκφραση γίνεται δείκτης στο πρώτο του στοιχείο, δηλαδή
char **. Γι’ αυτό, ως παράμετρος, το char *argv[] και το char **argv
είναι το ίδιο.char array[10][10] γίνεται δείκτης στην πρώτη γραμμή, τύπου char (*)[10],
όχι char **. Η θέση του array[i][j] υπολογίζεται (i * 10 + j), ενώ στον
char *array[] διαβάζεται πρώτα ο pointer array[i]. Σε συνάρτηση περνά ως
char array[][10], με γνωστό το πλήθος των στηλών.Μια συνάρτηση επιστρέφει με return μία τιμή, και τα ορίσματα περνούν κατά
τιμή (call by value): η συνάρτηση παίρνει αντίγραφα. Γι’ αυτό μια
void swap(int x, int y) ανταλλάσσει τα αντίγραφα και δεν αλλάζει τίποτα στον
καλούντα. Η λύση είναι να περάσουμε τις διευθύνσεις (swap(&a, &b)) και η
συνάρτηση να γράψει μέσω των δεικτών (*a = ...).
Με το ίδιο μοτίβο μια συνάρτηση «επιστρέφει» όσες τιμές θέλει: ο καλών δίνει μια
διεύθυνση για κάθε αποτέλεσμα (παράμετρος εξόδου, output parameter), και το
return μένει ελεύθερο για να πει αν η κλήση πέτυχε, όπως στη scanf. Έτσι γράφεται
η get_two_chars. Εναλλακτικά ο καλών δίνει έναν πίνακα char out[2] να γεμίσει· οι
δομές (struct), που ομαδοποιούν πολλές τιμές, έρχονται στο
Κεφάλαιο 19.
Η αναζήτηση σε δισδιάστατο πίνακα θέλει δύο εμφωλευμένους βρόχους,
\(O(\text{γραμμές} \cdot \text{στήλες})\). Η παγίδα είναι η έξοδος: το break βγάζει
μόνο από τον εσωτερικό βρόχο (Κεφάλαιο 8), οπότε ο
εξωτερικός συνεχίζει και το "yes" μπορεί να τυπωθεί πολλές φορές. Τρεις σωστοί τρόποι:
return, που βγαίνει από όλους τους βρόχους μαζί. Ο πιο καθαρός.found στις συνθήκες και των δύο βρόχων.goto σε ετικέτα μετά τους βρόχους: μία από τις λίγες αποδεκτές χρήσεις της.Όταν οι διαστάσεις γίνονται γνωστές μόνο στην εκτέλεση, ο πίνακας φτιάχνεται στον σωρό, με δύο τρόπους:
int ** με μία malloc ανά γραμμή, όπως στο Κεφάλαιο 13:
γράφουμε grid[i][j], αλλά χρειάζονται \(M + 1\) κλήσεις malloc και \(M + 1\) free
(πρώτα οι γραμμές), και οι γραμμές δεν είναι συνεχόμενες.M × N, με υπολογισμό της θέσης όπως κάνει ο μεταγλωττιστής για τους
στατικούς πίνακες: πρώτα προσπερνάμε i γραμμές και μετά j στοιχεία.int *grid = malloc(M * N * sizeof(int)); // + έλεγχος για NULL
grid[i * N + j] = 42; // το "grid[i][j]"
free(grid); // μία free για όλα
Η αναδρομική Fibonacci του ορισμού, fib(n) = fib(n-1) + fib(n-2), είναι σωστή αλλά
εκθετική: η fib(n-1) ξαναϋπολογίζει την fib(n-2) που υπολογίζει και ο δεύτερος
κλάδος, σε κάθε επίπεδο. Το πλήθος των κλήσεων μεγαλώνει όπως οι ίδιοι οι αριθμοί
Fibonacci (περίπου \(1{,}6^n\)): για fib(40) πάνω από 300 εκατομμύρια.
flowchart TD
f5["fib(5)"] --> f4["fib(4)"]
f5 --> f3a["fib(3)"]
f4 --> f3b["fib(3)"]
f4 --> f2a["fib(2)"]
f3a --> f2b["fib(2)"]
f3a --> f1a["fib(1)"]
f3b --> f2c["fib(2)"]
f3b --> f1b["fib(1)"]
Σχήμα: μέρος του δέντρου κλήσεων της απλής fib(5)· η fib(3) υπολογίζεται δύο
φορές και η fib(2) τρεις.
Στο «Γίνεται αναδρομικά και αποδοτικά;» η απάντηση είναι ναι:
memo[] την
πρώτη φορά και το επιστρέφουμε αμέσως στις επόμενες. \(O(n)\) χρόνος και μνήμη.Το ίδιο πρόβλημα είναι το ερώτημα 2.6 (fib_rec_fast) του fib.c στο
Εργαστήριο 5.
Η Εργασία #1 επεξεργάζεται αρχεία wav, έχει όριο μνήμης και διαβάζει δυαδικά δεδομένα. Η διάλεξη απαντά σε τρεις ερωτήσεις γι’ αυτήν:
/usr/bin/time -v ./prog (με όλη τη
διαδρομή, αλλιώς τρέχει η ενσωματωμένη time του shell) τυπώνει τη γραμμή «Maximum
resident set size (kbytes)», τη μέγιστη μνήμη της διεργασίας. Η memusage ./prog
δείχνει τη χρήση του σωρού (peak και κλήσεις malloc/free).cat. Οι xxd και hexdump -C δείχνουν τα
bytes σε δεκαεξαδική μορφή δίπλα στους χαρακτήρες· η hexedit τα επεξεργάζεται. Για
σύγκριση με την αναμενόμενη έξοδο, η cmp αναφέρει το πρώτο byte που διαφέρει (και
τίποτα αν τα αρχεία είναι ίδια) και η vbindiff δείχνει δύο αρχεία δίπλα-δίπλα.info στο
./soundwave info, είναι απλώς το argv[1]: ελέγχουμε πρώτα το argc και μετά
συγκρίνουμε με strcmp (0 σημαίνει ίσες) και καλούμε μια συνάρτηση ανά υποεντολή.Οι λύσεις των διαφανειών για τα δύο πρώτα προβλήματα, με πίνακα 100 ακεραίων:
int average(int grades[100]) {
int i, sum = 0;
for(i = 0; i < 100; i++) {
sum += grades[i];
}
return sum / 100;
}
int find(int haystack[100], int needle) {
int i;
for(i = 0; i < 100; i++) {
if (haystack[i] == needle) {
return i;
}
}
return -1;
}
Και οι δύο είναι \(O(n)\) χρόνος και \(O(1)\) μνήμη («Χρονική και χωρική
πολυπλοκότητα»). Στην average το sum / 100 είναι ακέραια διαίρεση (5,5 γίνεται
5)· για ακρίβεια επιστρέψτε double με sum / 100.0. Στη find το return i
σταματά στην πρώτη εμφάνιση και το -1 σημαίνει «δεν βρέθηκε», αφού δεν είναι ποτέ
έγκυρη θέση. Σε ταξινομημένο πίνακα η δυαδική αναζήτηση του
Κεφαλαίου 17 θα έκανε \(O(\log n)\).
Για το «στοιχείο που υπάρχει δύο φορές» (ο {8, 1, 5, 42, 7, 3, 42} δίνει 42), η απλή
λύση της πρώτης γραμμής του πίνακα της Θεωρίας, και για το «όλα διπλά εκτός από ένα»
η λύση με XOR:
int find_duplicate(int a[], int n) { // O(n^2) χρόνος, O(1) μνήμη
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (a[i] == a[j])
return a[i];
return -1;
}
int find_single(int a[], int n) { // O(n) χρόνος, O(1) μνήμη
int x = 0;
for (int i = 0; i < n; i++)
x ^= a[i];
return x;
}
Στη find_duplicate το j ξεκινά από i + 1, ώστε κάθε ζεύγος να ελεγχθεί μία φορά
και κανένα στοιχείο να μη συγκριθεί με τον εαυτό του. Για τον {4, 9, 2, 4, 7, 2, 9} η
find_single δίνει \((4 \oplus 4) \oplus (9 \oplus 9) \oplus (2 \oplus 2) \oplus 7 = 7\).
Με το μοτίβο «Τα ψηφία ενός αριθμού»:
int reverse(int n) {
int rev = 0;
while (n != 0) {
rev = rev * 10 + n % 10; // κόλλα το τελευταίο ψηφίο του n στο rev
n /= 10; // και πέτα το από το n
}
return rev;
}
int is_palindrome(int n) {
return n >= 0 && n == reverse(n);
}
Τα reverse(123), reverse(1200) και reverse(-45) δίνουν 321, 21 και -54· το
is_palindrome(12321) δίνει 1 και το is_palindrome(1231) 0. Το 1200 γίνεται 21
γιατί ένας ακέραιος δεν έχει αρχικά μηδενικά, κάτι που δεν πειράζει τον έλεγχο
παλινδρομικού. Εναλλακτικά, βάλτε τα ψηφία σε πίνακα και συγκρίνετε με δύο δείκτες
θέσης που κινούνται από τα άκρα προς τη μέση.
atoiΗ λύση των διαφανειών:
int atoi(char digits[]) {
int result = 0;
for(int i = 0; digits[i]; i++) {
result = 10 * result + digits[i] - '0';
}
return result;
}
Για το "123" το result γίνεται 1, 12, 123. Τα προβλήματά της αναλύονται στη
Θεωρία («Από χαρακτήρες σε αριθμό»). Μια ανθεκτικότερη εκδοχή ελέγχει κάθε χαρακτήρα
με '0' <= c && c <= '9', χειρίζεται το πρόσημο και επιστρέφει την επιτυχία χωριστά
από την τιμή (με παράμετρο εξόδου).
long long sum_squares(long long a, long long b) {
long long sum = 0;
for (long long k = 0; k * k <= b; k++)
if (k * k >= a)
sum += k * k;
return sum;
}
Η sum_squares(10, 50) δίνει \(16 + 25 + 36 + 49 = 126\). Η
sum_squares(1, 1000000000000LL) κάνει ένα εκατομμύριο βήματα, τελειώνει ακαριαία
και δίνει 333333833333500000, όσο και ο τύπος της Θεωρίας με \(m = 10^6\).
get_two_charsΔύο χαρακτήρες «επιστρέφονται» μέσω παραμέτρων εξόδου, και το return λέει αν
πέτυχε η ανάγνωση:
int get_two_chars(char *first, char *second) {
int c1 = getchar();
int c2 = getchar();
if (c1 == EOF || c2 == EOF)
return 0;
*first = c1;
*second = c2;
return 1;
}
Με char a, b; και while (get_two_chars(&a, &b)) printf("[%c%c]\n", a, b);, η
είσοδος abcde τυπώνει [ab] και [cd]· το μονό e αγνοείται. Οι c1, c2 είναι
int γιατί η getchar επιστρέφει int ώστε να χωρά το EOF
(Κεφάλαιο 9). Στην Εργασία #1, όπου οι δομές απαγορεύονται και η
είσοδος διαβάζεται μόνο με getchar, έτσι γράφονται βοηθητικές που διαβάζουν πεδία
πολλών bytes.
swapΟι διαφάνειες δίνουν τη main και ζητούν τη swap(...) που λείπει. Η λύση:
#include <stdio.h>
void swap(int *a, int *b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
int main() {
int a = 100, b = 200;
printf("%d %d\n", a, b);
swap(&a, &b);
printf("%d %d\n", a, b);
return 0;
}
$ ./swap
100 200
200 100
Η tmp χρειάζεται γιατί μετά το *a = *b η αρχική τιμή του *a έχει χαθεί. Οι
παράμετροι λέγονται κι αυτές a και b, αλλά είναι άλλες μεταβλητές (τύπου int *),
τοπικές στη swap.
Με τον πρώτο τρόπο της «Έξοδος από εμφωλευμένους βρόχους»:
int contains(int grid[ROWS][COLS], int needle) {
for (int i = 0; i < ROWS; i++)
for (int j = 0; j < COLS; j++)
if (grid[i][j] == needle)
return 1; // βγαίνει και από τους δύο βρόχους
return 0;
}
Η main κάνει if (contains(grid, 7)) printf("yes\n"); και το "yes" τυπώνεται μία
φορά. Με σημαία, οι βρόχοι θα γίνονταν for (i = 0; i < ROWS && !found; i++) και
αντίστοιχα για τον εσωτερικό.
Με απομνημόνευση («Αναδρομή χωρίς επανυπολογισμούς»):
#define MAXN 92
long long memo[MAXN + 1]; // global: αρχικοποιείται με μηδενικά
long long fib(int n) {
if (n <= 1)
return n;
if (memo[n] != 0) // το έχουμε ήδη υπολογίσει
return memo[n];
memo[n] = fib(n - 1) + fib(n - 2);
return memo[n];
}
Το 0 σημαίνει «δεν έχει υπολογιστεί», αφού για \(n \ge 2\) κανένας αριθμός Fibonacci δεν
είναι 0. Η fib(50) δίνει 12586269025 και η fib(92), ο μεγαλύτερος που χωρά σε
long long, 7540113804746346429, ακαριαία. Η απλή εκδοχή θα έκανε περίπου
\(2{,}4 \cdot 10^{19}\) κλήσεις για τη fib(92): αιώνες, ακόμη και με ένα δισεκατομμύριο
κλήσεις το δευτερόλεπτο. Η δεύτερη τεχνική, με τις δύο τελευταίες τιμές ως ορίσματα:
long long fib_acc(int n, long long a, long long b) {
return n == 0 ? a : fib_acc(n - 1, b, a + b);
}
Η fib_acc(50, 0, 1) δίνει πάλι 12586269025, με 51 κλήσεις.
argv[1]Ο σκελετός μιας main με υποεντολές, για την Εργασία #1:
#include <stdio.h>
#include <string.h>
int main(int argc, char **argv) {
if (argc < 2) {
fprintf(stderr, "Usage: %s info|rate ...\n", argv[0]);
return 1;
}
if (strcmp(argv[1], "info") == 0) {
printf("running info\n");
} else if (strcmp(argv[1], "rate") == 0 && argc == 3) {
printf("running rate with %s\n", argv[2]);
} else {
fprintf(stderr, "Unknown subcommand: %s\n", argv[1]);
return 1;
}
return 0;
}
Το ./sub rate 2.0 τυπώνει running rate with 2.0, ενώ το ./sub foo τυπώνει
μήνυμα λάθους στο stderr και τερματίζει με κωδικό 1. Στην πράξη κάθε κλάδος καλεί τη
δική του συνάρτηση (do_info(), do_rate(...)).
n % 10, n / 10 και 10 * r + digit δίνουν την αντιστροφή ψηφίων, τον
έλεγχο παλινδρομικού και την atoi.'\0'.char *array[] είναι πίνακας από pointers, ο char **array ένας pointer και ο
char array[10][10] 100 συνεχόμενοι χαρακτήρες· ως παράμετροι, μόνο οι δύο πρώτοι
είναι ισοδύναμοι.swap) ή να
«επιστρέψει» πολλές τιμές, μια συνάρτηση παίρνει τις διευθύνσεις τους.break βγάζει μόνο από τον εσωτερικό βρόχο· για εμφωλευμένους βρόχους
χρησιμοποιούμε return, σημαία ή goto.int ** με μία malloc ανά γραμμή
είτε ένα μπλοκ M × N με δείκτη i * N + j./usr/bin/time -v και memusage μετρούν μνήμη· xxd,
hexdump, hexedit, cmp και vbindiff δείχνουν και συγκρίνουν δυαδικά αρχεία·
οι υποεντολές είναι σύγκριση του argv[1] με strcmp.| Ελληνικά | English | Σύντομος ορισμός |
|---|---|---|
| χρονική πολυπλοκότητα | time complexity | Πώς αυξάνονται τα βήματα με το μέγεθος της εισόδου. |
| χωρική πολυπλοκότητα | space complexity | Πόση επιπλέον μνήμη χρειάζεται σε σχέση με την είσοδο. |
| χειρότερη περίπτωση | worst case | Η είσοδος που κάνει τον αλγόριθμο να δουλέψει περισσότερο. |
| αντιστάθμισμα χρόνου–μνήμης | time–space tradeoff | Ταχύτερη λύση με περισσότερη μνήμη, ή το αντίστροφο. |
| αποκλειστικό Ή | XOR (^) |
Bit 1 όταν τα δύο bits διαφέρουν· \(x \oplus x = 0\). |
| παλινδρομικός | palindrome | Που διαβάζεται ίδια και από τις δύο μεριές. |
| κλήση κατά τιμή | call by value | Η συνάρτηση παίρνει αντίγραφα των ορισμάτων. |
| παράμετρος εξόδου | output parameter | Δείκτης μέσω του οποίου η συνάρτηση γράφει ένα αποτέλεσμα. |
| σημαία | flag | Μεταβλητή που καταγράφει ότι συνέβη κάτι (π.χ. found). |
| απομνημόνευση | memoization | Αποθήκευση αποτελεσμάτων ώστε να μην ξαναϋπολογίζονται. |
| υποεντολή | subcommand | Λέξη στο argv[1] που επιλέγει τι θα κάνει το πρόγραμμα. |
atoi
σελ. 16–17· τέλεια τετράγωνα σελ. 18· char *array[] / char ** / char [10][10]
σελ. 19· get_two_chars σελ. 20· παλινδρομικός σελ. 21· swap σελ. 22–23·
δισδιάστατη αναζήτηση σελ. 24· δισδιάστατος στον σωρό σελ. 25· Fibonacci σελ. 26·
Εργασία #1 σελ. 27.swap).break και continue» και «Εντολή goto και ετικέτες» (K04,
σελ. 56–57).fib.c
(ερωτήματα 2.3–2.6)·
Εργαστήριο 6: άσκηση
myprog.c (αποτελέσματα μέσω δεικτών)·
Εργαστήριο 7: ασκήσεις
twodim.c και mines.c (δισδιάστατοι πίνακες, στατικοί και στον σωρό).man 1 time, man 1 memusage, man 1 xxd, man 1 hexdump, man 1 cmp,
man 3 strcmp.sum / 100 δίνει 5 αντί για 5,5. Επιστρέψτε
double με sum / 100.0.find είναι \(O(1)\) γιατί μπορεί να
το βρει πρώτο» είναι λάθος: αναλύουμε τη χειρότερη, \(O(n)\).for (j = 0; ...) αντί για j = i + 1,
το a[i] == a[j] ισχύει για i == j και «βρίσκεται» διπλό σε κάθε πίνακα.reverse(1999999999) ή atoi("99999999999") δίνουν λάθος αριθμό.
Χρησιμοποιήστε ευρύτερο τύπο ή ελέγξτε πριν πολλαπλασιάσετε με 10.swap κατά τιμή. Η void swap(int x, int y) δεν αλλάζει τίποτα στην main.
Δηλώστε int * παραμέτρους και καλέστε swap(&a, &b).char **. Το f(grid) με char grid[10][10]
δίνει incompatible pointer type (στο gcc 14 σφάλμα) και, αν τρέξει, κρασάρει.
Δηλώστε char grid[][10].break σε εμφωλευμένους βρόχους. Το "yes" τυπώνεται πολλές φορές. Βάλτε την
αναζήτηση σε συνάρτηση με return.char για το αποτέλεσμα της getchar. Το EOF δεν ξεχωρίζει αξιόπιστα.
Κρατήστε το σε int και ελέγξτε το πριν το αποθηκεύσετε.time -v αντί για /usr/bin/time -v. Η ενσωματωμένη time του shell δεν
δέχεται -v.argv[1] χωρίς έλεγχο του argc. Το ./soundwave χωρίς ορίσματα περνά NULL
στην strcmp και κρασάρει. Ελέγξτε πρώτα argc < 2.average για \(n\)
στοιχεία;14567 % 10 και 4567 / 10;[^q4]char grid[10][10] σε παράμετρο char **;[^q6]void swap(int x, int y) δεν δουλεύει;[^q7]M × N, πού βρίσκεται το στοιχείο γραμμής i, στήλης j;[^q8]fib είναι αργή, και τι κάνει η απομνημόνευση;[^q9]slides-lec16-average-complexityslides-lec16-find-complexityslides-lec16-get-two-charsslides-lec16-palindrome-numberslides-lec16-reverse-digitsslides-lec16-search-2dslides-lec16-swapslides-lec16-why-practiceslides-lec16-atoislides-lec16-char-pointer-arraysslides-lec16-fibonacci-efficientslides-lec16-find-duplicateslides-lec16-heap-2d-arrayslides-lec16-single-unpairedslides-lec16-sum-perfect-squareslab-lab05-ladderlab-lab07-olafhw-2025-bonus0-stergiosexam-2023-dec-q2exam-2023-fall-ex0-q4exam-2023-fall-ex11-q4exam-2023-fall-ex12-q4exam-2023-fall-ex13-q4exam-2024-dec-q2exam-2023-fall-ex3-q4exam-2025-jan-q6hw-2023-hw1-flawlesshw-2024-hw1-factorexam-2023-dec-q3exam-2023-fall-ex14-q4exam-2023-fall-ex2-q4\(O(n)\) χρόνος (ένα πέρασμα) και \(O(1)\) μνήμη (μόνο i και sum). ↩
Η πολυπλοκότητα αναφέρεται στη χειρότερη περίπτωση, όταν το στοιχείο λείπει
και ελέγχονται και τα \(n\).
[^q3]: Επειδή \(x \oplus x = 0\), \(x \oplus 0 = x\) και η σειρά δεν παίζει ρόλο: τα
ζευγάρια μηδενίζονται και μένει το μοναδικό.
[^q4]: 7 (το τελευταίο ψηφίο) και 456.
[^q5]: Περίπου \(\sqrt{10^{12}} = 10^6\).
[^q6]: Όχι. Ο grid γίνεται char (*)[10] και δεν περιέχει pointers· η παράμετρος
πρέπει να είναι char grid[][10].
[^q7]: Τα ορίσματα περνούν κατά τιμή: ανταλλάσσει αντίγραφα, όχι τις μεταβλητές του
καλούντος.
[^q8]: Στη θέση i * N + j.
[^q9]: Ξαναϋπολογίζει τις ίδιες τιμές, με εκθετικό πλήθος κλήσεων. Η απομνημόνευση
κρατά κάθε fib(k) σε πίνακα ώστε να υπολογίζεται μία φορά: \(O(n)\).
[^q10]: Με /usr/bin/time -v ./prog, γραμμή «Maximum resident set size». ↩