Η ερώτηση
Πώς να βρείτε τη χρονική πολυπλοκότητα ενός αλγορίθμου;
Τι έχω κάνει πριν δημοσιεύσω μια ερώτηση στο SO;
Έψαξα αυτό, αυτό και πολλούς άλλους συνδέσμους.
Αλλά πουθενά δεν μπόρεσα να βρω μια σαφή και απλή εξήγηση για το πώς να υπολογίσω τη χρονική πολυπλοκότητα.
Τι ξέρω εγώ;
Ας πούμε για έναν κώδικα τόσο απλό όσο ο παρακάτω:
char h = 'y'; // This will be executed 1 time
int abc = 0; // This will be executed 1 time
Ας πούμε για έναν βρόχο όπως ο παρακάτω:
for (int i = 0; i < N; i++) {
Console.Write('Hello World !');
}
int i=0; Αυτό θα εκτελεστεί μόνο μια φορά.
Ο χρόνος στην πραγματικότητα υπολογίζεται στο i=0
και όχι στη δήλωση.
i < N; Αυτό θα εκτελεστεί N+1 φορές.
i++ ; Αυτό θα εκτελεστεί N φορές
Έτσι, ο αριθμός των πράξεων που απαιτούνται από αυτόν τον βρόχο είναι
{1+(N+1)+N} = 2N+2
Σημείωση: Αυτό μπορεί ακόμα να είναι λάθος, καθώς δεν είμαι σίγουρος για την κατανόησή μου σχετικά με τον υπολογισμό της χρονικής πολυπλοκότητας.
**Τι θέλω να μάθω;
Εντάξει, αυτούς τους μικρούς βασικούς υπολογισμούς νομίζω ότι τους ξέρω, αλλά στις περισσότερες περιπτώσεις έχω δει τη χρονική πολυπλοκότητα ως
O(N), O(n2), O(log n), O(n!).... και πολλά άλλα,
Μπορεί κάποιος να με βοηθήσει να καταλάβω πώς υπολογίζεται η χρονική πολυπλοκότητα ενός αλγορίθμου; Είμαι σίγουρος ότι υπάρχουν πολλοί αρχάριοι σαν εμένα που θέλουν να το μάθουν αυτό.
Αυτό είναι ένα εξαιρετικό άρθρο : http://www.daniweb.com/software-development/computer-science/threads/13488/time-complexity-of-algorithm
Η παρακάτω απάντηση αντιγράφεται από τα παραπάνω (σε περίπτωση που ο εξαιρετικός σύνδεσμος χαθεί)
Η πιο συνηθισμένη μετρική για τον υπολογισμό της χρονικής πολυπλοκότητας είναι η σημειογραφία Big O. Αυτό αφαιρεί όλους τους σταθερούς παράγοντες, έτσι ώστε ο χρόνος εκτέλεσης να μπορεί να εκτιμηθεί σε σχέση με το Ν καθώς το Ν πλησιάζει στο άπειρο. Σε γενικές γραμμές μπορείτε να το σκεφτείτε ως εξής:
statement;
Είναι σταθερός. Ο χρόνος εκτέλεσης της εντολής δεν θα αλλάξει σε σχέση με το N.
for ( i = 0; i < N; i++ )
statement;
Είναι γραμμική. Ο χρόνος εκτέλεσης του βρόχου είναι ευθέως ανάλογος του N. Όταν το N διπλασιάζεται, το ίδιο συμβαίνει και με τον χρόνο εκτέλεσης.
for ( i = 0; i < N; i++ ) {
for ( j = 0; j < N; j++ )
statement;
}
Είναι τετραγωνικός. Ο χρόνος εκτέλεσης των δύο βρόχων είναι ανάλογος του τετραγώνου του N. Όταν το N διπλασιάζεται, ο χρόνος εκτέλεσης αυξάνεται κατά N * N.
while ( low <= high ) {
mid = ( low + high ) / 2;
if ( target < list[mid] )
high = mid - 1;
else if ( target > list[mid] )
low = mid + 1;
else break;
}
Είναι λογαριθμική. Ο χρόνος εκτέλεσης του αλγορίθμου είναι ανάλογος με τον αριθμό των φορών που το Ν μπορεί να διαιρεθεί με το 2. Αυτό συμβαίνει επειδή ο αλγόριθμος διαιρεί την περιοχή εργασίας στο μισό με κάθε επανάληψη.
void quicksort ( int list[], int left, int right )
{
int pivot = partition ( list, left, right );
quicksort ( list, left, pivot - 1 );
quicksort ( list, pivot + 1, right );
}
Είναι N * log ( N ). Ο χρόνος εκτέλεσης αποτελείται από Ν βρόχους (επαναληπτικούς ή αναδρομικούς) που είναι λογαριθμικοί, επομένως ο αλγόριθμος είναι ένας συνδυασμός γραμμικού και λογαριθμικού.
Γενικά, το να κάνεις κάτι με κάθε στοιχείο σε μία διάσταση είναι γραμμικό, το να κάνεις κάτι με κάθε στοιχείο σε δύο διαστάσεις είναι τετραγωνικό και το να διαιρείς την περιοχή εργασίας στη μέση είναι λογαριθμικό. Υπάρχουν και άλλα μέτρα Big O, όπως το κυβικό, το εκθετικό και η τετραγωνική ρίζα, αλλά δεν είναι τόσο συνηθισμένα. Ο συμβολισμός Big O περιγράφεται ως O (
Σημειώστε ότι σε όλα αυτά δεν έχουν ληφθεί υπόψη τα μέτρα καλύτερης, μέσης και χειρότερης περίπτωσης. Κάθε ένα από αυτά θα είχε το δικό του συμβολισμό Big O. Σημειώστε επίσης ότι αυτή είναι μια ΠΟΛΥ απλοϊκή εξήγηση. Το Big O είναι το πιο συνηθισμένο, αλλά είναι επίσης πιο πολύπλοκο από ό,τι έχω δείξει. Υπάρχουν επίσης άλλες σημειώσεις όπως το μεγάλο ωμέγα, το μικρό ο και το μεγάλο θήτα. Πιθανότατα δεν θα τις συναντήσετε εκτός ενός μαθήματος ανάλυσης αλγορίθμων. ;)
Πώς να βρείτε τη χρονική πολυπλοκότητα ενός αλγορίθμου
Προσθέτετε πόσες εντολές μηχανής θα εκτελέσει σε συνάρτηση με το μέγεθος της εισόδου του και στη συνέχεια απλοποιείτε την έκφραση στον μεγαλύτερο (όταν το Ν είναι πολύ μεγάλο) όρο και μπορείτε να συμπεριλάβετε οποιονδήποτε απλοποιητικό σταθερό παράγοντα.
Για παράδειγμα, ας δούμε πώς απλοποιούμε τις 2N + 2
εντολές μηχανής για να το περιγράψουμε ως απλά O(N)
.
**Γιατί αφαιρούμε τα δύο "2";
Μας ενδιαφέρει η απόδοση του αλγορίθμου καθώς το Ν γίνεται μεγάλο.
Θεωρήστε τους δύο όρους 2N και 2.
Ποια είναι η σχετική επιρροή αυτών των δύο όρων καθώς το Ν γίνεται μεγάλο; Ας υποθέσουμε ότι το Ν είναι ένα εκατομμύριο.
Τότε ο πρώτος όρος είναι 2 εκατομμύρια και ο δεύτερος όρος είναι μόνο 2.
Για το λόγο αυτό, εγκαταλείπουμε όλους τους όρους εκτός από τους μεγαλύτερους για μεγάλο Ν.
Έτσι, τώρα έχουμε περάσει από το "2N + 2" στο "2N".
Παραδοσιακά, μας ενδιαφέρει μόνο η απόδοση μέχρι σταθερούς συντελεστές.
Αυτό σημαίνει ότι δεν μας ενδιαφέρει πραγματικά αν υπάρχει κάποιο σταθερό πολλαπλάσιο της διαφοράς στην απόδοση όταν το N είναι μεγάλο. Η μονάδα του 2N δεν είναι καλά καθορισμένη ούτως ή άλλως. Έτσι μπορούμε να πολλαπλασιάσουμε ή να διαιρέσουμε με έναν σταθερό παράγοντα για να φτάσουμε στην απλούστερη έκφραση.
Έτσι το "2N" γίνεται απλά "N".
O(n) είναι ο μεγάλος συμβολισμός O που χρησιμοποιείται για τη γραφή της χρονικής πολυπλοκότητας ενός αλγορίθμου. Όταν αθροίζετε τον αριθμό των εκτελέσεων σε έναν αλγόριθμο θα λάβετε μια έκφραση στο αποτέλεσμα όπως 2N+2, σε αυτή την έκφραση το N είναι ο κυρίαρχος όρος (ο όρος που έχει τη μεγαλύτερη επίδραση στην έκφραση αν η τιμή του αυξάνεται ή μειώνεται). Τώρα O(N) είναι η χρονική πολυπλοκότητα ενώ το N είναι ο κυρίαρχος όρος. Παράδειγμα
For i= 1 to n;
j= 0;
while(j<=n);
j=j+1;
εδώ ο συνολικός αριθμός εκτελέσεων για τον εσωτερικό βρόχο είναι n+1 και ο συνολικός αριθμός εκτελέσεων για τον εξωτερικό βρόχο είναι n(n+1)/2, οπότε ο συνολικός αριθμός εκτελέσεων για ολόκληρο τον αλγόριθμο είναι n+1+n(n+1/2) = (n^2+3n)/2. εδώ το n^2 είναι ο κυρίαρχος όρος, οπότε η χρονική πολυπλοκότητα για αυτόν τον αλγόριθμο είναι O(n^2)