Μια ανάλυση της σύγκρισης του χρονικού κόστους των αλγορίθμων που εκτελούνται με την επίλυση ενός στιγμιότυπου κάποιου προβλήματος, με μεγάλες ποσότητες δεδομένων εισόδου, ονομάζεται ασυμπτωτικός. Ο αλγόριθμος με τη χαμηλότερη ασυμπτωτική πολυπλοκότητα είναι ο πιο αποτελεσματικός.

Στην ασυμπτωτική ανάλυση, πολυπλοκότητα αλγορίθμουείναι μια συνάρτηση που σας επιτρέπει να προσδιορίσετε πόσο γρήγορα αυξάνεται ο χρόνος εκτέλεσης του αλγορίθμου με την αύξηση της ποσότητας δεδομένων.

Οι κύριες εκτιμήσεις ανάπτυξης που συναντήθηκαν στην ασυμπτωτική ανάλυση είναι:

• Ο (L-big) είναι η ανώτερη ασυμπτωτική εκτίμηση για την αύξηση της συνάρτησης χρόνου.
• Το Ω (Ωμέγα) είναι η χαμηλότερη ασυμπτωτική εκτίμηση για την αύξηση της συνάρτησης χρόνου.
• Θ (Θήτα) είναι οι κατώτερες και οι ανώτερες ασυμπτωτικές εκτιμήσεις για την αύξηση της συνάρτησης χρόνου.

Αφήνω n– ποσότητα δεδομένων. Στη συνέχεια η ανάπτυξη της συνάρτησης αλγορίθμου φά(n) μπορεί να περιορίσει τις λειτουργίες σολ(n) ασυμπτωτικά:

Για παράδειγμα, ο χρόνος καθαρισμού ενός δωματίου εξαρτάται γραμμικά από την περιοχή του ίδιου δωματίου (Θ( μικρό)), δηλαδή με αύξηση της έκτασης σε nφορές, ο χρόνος καθαρισμού θα αυξηθεί επίσης nμια φορά. Η αναζήτηση ενός ονόματος στον τηλεφωνικό κατάλογο θα διαρκέσει γραμμικό χρόνο Ο (n), εάν χρησιμοποιείτε τον αλγόριθμο γραμμικής αναζήτησης ή τον χρόνο που εξαρτάται λογαριθμικά από τον αριθμό των εγγραφών ( Ο ( ημερολόγιο 2 ( n))), σε περίπτωση δυαδικής αναζήτησης.

Για εμάς το μεγαλύτερο ενδιαφέρον είναι Ο -λειτουργία. Επίσης, σε επόμενα κεφάλαια, η πολυπλοκότητα των αλγορίθμων θα δοθεί μόνο για το άνω ασυμπτωτικό όριο.

Κάτω από τη φράση «η πολυπλοκότητα του αλγορίθμου είναι Ο (φά(n))" σημαίνει ότι με αύξηση του όγκου των δεδομένων εισόδου n, ο χρόνος εκτέλεσης του αλγορίθμου δεν θα αυξηθεί γρηγορότερα από κάποια σταθερά πολλαπλασιαζόμενη επί φά(n).

Σημαντικοί κανόνες ασυμπτωτικής ανάλυσης:

1. Ο(κ*φά) = Ο(φά) είναι ένας σταθερός παράγοντας κ(σταθερά) απορρίπτεται, επειδή με την αύξηση του όγκου των δεδομένων, χάνεται η σημασία του, για παράδειγμα:

O(9,1n) = O(n)

1. Ο(φά*σολ) = Ο(φά)*Ο(σολ) – η εκτίμηση της πολυπλοκότητας του γινομένου δύο συναρτήσεων είναι ίση με το γινόμενο της πολυπλοκότητάς τους, για παράδειγμα:

O(5n*n) = O(5n)*O(n) = O(n)*O(n) = O(n*n) = O(n 2)

1. Ο(φά/σολ)=Ο(φά)/Ο(σολ) – η εκτίμηση της πολυπλοκότητας του πηλίκου δύο συναρτήσεων είναι ίση με το πηλίκο των πολυπλοκοτήτων τους, για παράδειγμα:

O(5n/n) = O(5n)/O(n) = O(n)/O(n) = O(n/n) = O(1)

1. Ο(φά+σολ) ισούται με την κυρίαρχη Ο(φά) Και Ο(σολ) – η εκτίμηση της πολυπλοκότητας του αθροίσματος των συναρτήσεων ορίζεται ως η εκτίμηση της πολυπλοκότητας του κυρίαρχου του πρώτου και του δεύτερου όρου, για παράδειγμα:

O(n 5 +n 10) = O(n 10)

Η καταμέτρηση του αριθμού των επεμβάσεων είναι κουραστική και, κυρίως, καθόλου υποχρεωτική. Με βάση τους παραπάνω κανόνες, για να προσδιοριστεί η πολυπλοκότητα ενός αλγορίθμου, δεν είναι απαραίτητο, όπως κάναμε πριν, να μετρήσουμε όλες τις πράξεις, αρκεί να γνωρίζουμε τι πολυπλοκότητα αυτή ή η άλλη κατασκευή του αλγορίθμου (τελεστής ή ομάδα χειριστές) έχει. Έτσι, ένας αλγόριθμος που δεν περιέχει κύκλους και αναδρομές έχει σταθερή πολυπλοκότητα Ο(1). Η πολυπλοκότητα του βρόχου που εκτελείται nεπαναλήψεις ισούται με Ο(n). Η κατασκευή δύο ένθετων βρόχων ανάλογα με την ίδια μεταβλητή n, έχει τετραγωνική πολυπλοκότητα Ο(n 2).

Μπορούν να χρησιμοποιηθούν διαφορετικές προσεγγίσεις για την αξιολόγηση της απόδοσης των αλγορίθμων. Το απλούστερο είναι να εκτελέσετε απλώς κάθε αλγόριθμο σε πολλές εργασίες και να συγκρίνετε τον χρόνο εκτέλεσης. Ένας άλλος τρόπος είναι να υπολογίσουμε μαθηματικά τον χρόνο εκτέλεσης μετρώντας πράξεις.

Θεωρήστε έναν αλγόριθμο για τον υπολογισμό της τιμής ενός πολυωνύμου βαθμού n V δεδομένο σημείο Χ.
P n (x) = a n x n + a n-1 x n-1 + ... + a i x i + ... + a 1 x 1 + a 0

Αλγόριθμος 1- για κάθε όρο, εκτός από ένα 0, αύξηση Χσε μια δεδομένη δύναμη με διαδοχικό πολλαπλασιασμό και στη συνέχεια πολλαπλασιάστε με έναν παράγοντα. Στη συνέχεια, προσθέστε τους όρους.

υπολογισμός Εγώ-ο όρος( i=1..n) απαιτεί Εγώπολλαπλασιασμούς. Συνολικά λοιπόν 1 + 2 + 3 + ... + n = n(n+1)/2πολλαπλασιασμούς. Επιπλέον, απαιτείται n+1πρόσθεση. Σύνολο n(n+1)/2 + n + 1= n 2 /2 + 3n/2 + 1επιχειρήσεις.

Αλγόριθμος 2- βγάζω Χ-s έξω από τις αγκύλες και ξαναγράψτε το πολυώνυμο στη φόρμα
P n (x) = a 0 + x(a 1 + x(a 2 + ... (a i + .. x(a n-1 + a n x))).

Για παράδειγμα,
P 3 (x) = a 3 x 3 + a 2 x 2 + a 1 x 1 + a 0 = a 0 + x(a 1 + x(a 2 + a 3 x))

Θα αξιολογήσουμε την έκφραση από μέσα. Η πιο εσωτερική παρένθεση απαιτεί 1 πολλαπλασιασμό και 1 πρόσθεση. Η τιμή του χρησιμοποιείται για την επόμενη αγκύλη... Και έτσι, 1 πολλαπλασιασμός και 1 πρόσθεση για κάθε αγκύλη, που.. n-1πράγμα. Και αφού υπολογίσετε την πιο εξωτερική αγκύλη, πολλαπλασιάστε με x και προσθέστε ένα 0. Σύνολο nπολλαπλασιασμοί + nπροσθήκες = 2nεπιχειρήσεις.

Συχνά δεν απαιτείται μια τόσο λεπτομερής αξιολόγηση. Αντίθετα, δίνεται μόνο ο ασυμπτωτικός ρυθμός αύξησης του αριθμού των πράξεων με αύξηση του n.

Συνάρτηση f(n) = n 2 /2 + 3n/2 + 1αυξάνεται περίπου όσο n 2/2(απορρίπτουμε τον σχετικά αργά αναπτυσσόμενο όρο 3n/2+1). σταθερός πολλαπλασιαστής 1/2 αφαιρούμε επίσης και λαμβάνουμε μια ασυμπτωτική εκτίμηση για τον Αλγόριθμο 1, η οποία συμβολίζεται με ένα ειδικό σύμβολο O(n2)[διαβάστε ως "O big from en Square"].

Αυτό είναι ένα ανώτερο όριο, δηλαδή ο αριθμός των λειτουργιών (και επομένως ο χρόνος εκτέλεσης) δεν αυξάνεται ταχύτερα από το τετράγωνο του αριθμού των στοιχείων. Για να πάρετε μια αίσθηση για το τι είναι αυτό, δείτε τον πίνακα, ο οποίος δείχνει αριθμούς που απεικονίζουν τον ρυθμό ανάπτυξης για πολλές διαφορετικές συναρτήσεις.

		n*log n
1	0	0	1
16	4	64	256
256	8	2,048	65,536
4,096	12	49,152	16,777,216
65,536	16	1,048,565	4,294,967,296
1,048,576	20	20,969,520	1,099,301,922,576
16,775,616	24	402,614,784	281,421,292,179,456

Αν υποθέσουμε ότι οι αριθμοί στον πίνακα αντιστοιχούν σε μικροδευτερόλεπτα, τότε για μια εργασία με n=1048576στοιχεία του αλγορίθμου με χρόνο εκτέλεσης O(log n)θα χρειαστούν 20 μικροδευτερόλεπτα, ο αλγόριθμος με την πάροδο του χρόνου Επί)- 17 λεπτά και ο αλγόριθμος με χρόνο εκτέλεσης O(n2)- περισσότερες από 12 ημέρες... Τώρα το πλεονέκτημα του αλγορίθμου 2 με εκτίμηση Επί)πριν ο Αλγόριθμος 1 είναι αρκετά προφανής.

Η καλύτερη εκτίμηση είναι O(1)... Σε αυτή την περίπτωση, ο χρόνος δεν εξαρτάται από n, δηλαδή συνεχώς για οποιοδήποτε αριθμό στοιχείων.

Ετσι, Ο()- "περικομμένη" εκτίμηση του χρόνου εκτέλεσης του αλγορίθμου, ο οποίος είναι συχνά πολύ πιο εύκολος να ληφθεί από τον ακριβή τύπο για τον αριθμό των πράξεων.

Ας διατυπώσουμε λοιπόν δύο κανόνες για τον σχηματισμό της εκτίμησης O().

Κατά την αξιολόγηση της συνάρτησης, λαμβάνεται ως συνάρτηση ο αριθμός των λειτουργιών που αυξάνεται ταχύτερα.
Δηλαδή, εάν το πρόγραμμα έχει μία συνάρτηση, για παράδειγμα, εκτελείται ο πολλαπλασιασμός Επί)φορές και προσθήκη - O(n2)φορές, τότε η συνολική πολυπλοκότητα του προγράμματος - O(n2), αφού τελικά με αύξηση nπιο γρήγορα (σε ένα ορισμένο, συνεχήςπολλές φορές) οι προσθήκες θα εκτελούνται τόσο συχνά που θα επηρεάσουν την απόδοση πολύ περισσότερο από τους αργούς αλλά σπάνιους πολλαπλασιασμούς. Σύμβολο Ο()δείχνει αποκλειστικά ασυμπτωτικά!

Κατά την αξιολόγηση του O() , οι σταθερές δεν λαμβάνονται υπόψη.
Αφήστε τον έναν αλγόριθμο να κάνει 2500n + 1000 πράξεις και ο άλλος - 2n+1. Και οι δύο βαθμολογούνται Επί), αφού ο χρόνος εκτέλεσής τους μεγαλώνει γραμμικά.

Συγκεκριμένα, εάν και οι δύο αλγόριθμοι, για παράδειγμα, O(n*log n)Ωστόσο, αυτό δεν σημαίνει ότι είναι εξίσου αποτελεσματικά. Το πρώτο μπορεί να είναι, ας πούμε, 1000 φορές πιο αποτελεσματικό. Το O() σημαίνει μόνο ότι ο χρόνος τους αυξάνεται περίπου ως συνάρτηση του n*log n.

Μια άλλη συνέπεια της παράλειψης της σταθεράς είναι ο αλγόριθμος με την πάροδο του χρόνου O(n2)μπορεί να τρέξει πολύ πιο γρήγορα από τον αλγόριθμο Επί) για μικρό ν... Λόγω του ότι ο πραγματικός αριθμός πράξεων του πρώτου αλγορίθμου μπορεί να είναι n2 + 10n + 6και το δεύτερο - 1000000n+5. Ωστόσο, ο δεύτερος αλγόριθμος θα ξεπεράσει τον πρώτο αργά ή γρήγορα... ν 2αυξάνεται πολύ πιο γρήγορα 1000000n.

Βάση λογάριθμου μέσα σε σύμβολο Ο()δεν γράφεται.
Ο λόγος για αυτό είναι αρκετά απλός. Ας έχουμε O(log2n). Αλλά log 2 n=log 3 n/log 3 2, ΕΝΑ ημερολόγιο 3 2, όπως κάθε σταθερά, το ασυμπτωτικό είναι το σύμβολο ΣΧΕΤΙΚΑ ΜΕ()δεν λαμβάνει υπόψη. Ετσι, O(log2n) = O(log 3 n).

Μπορούμε να πάμε σε οποιαδήποτε βάση με παρόμοιο τρόπο, πράγμα που σημαίνει ότι δεν έχει νόημα να το γράψουμε.

Μαθηματική ερμηνεία του συμβόλου O().

Ορισμός
O(g)- πολλές λειτουργίες φά, για τις οποίες υπάρχουν τέτοιες σταθερές ντοΚαι Ν, Τι |f(x)|<= C|g(x)| για όλα x>N.
Εγγραφή f = O(g)κυριολεκτικά σημαίνει ότι φάανήκει στο σύνολο O(g). Σε αυτή την περίπτωση, η αντίστροφη έκφραση O(g) = fδεν έχει νόημα.

Συγκεκριμένα, μπορεί κανείς να πει ότι f(n) = 50nανήκει O(n2). Εδώ έχουμε να κάνουμε με ανακριβή εκτίμηση. Φυσικά f(n)<= 50n 2 στο n>1, αλλά μια ισχυρότερη δήλωση θα ήταν f(n) = O(n), γιατί για C=50Και N=1σωστά f(n)<= Cn, n>Ν.

Άλλοι τύποι αξιολογήσεων.

Μαζί με την αξιολόγηση Επί)χρησιμοποιημένη βαθμολογία Ω(n)[διαβάστε ως "Omega big from en"]. Υποδηλώνει μια χαμηλότερη εκτίμηση για την ανάπτυξη της συνάρτησης. Για παράδειγμα, αφήστε τη συνάρτηση να περιγράφει τον αριθμό των πράξεων αλγορίθμου f(n) = Ω(n 2). Αυτό σημαίνει ότι ακόμη και στην πιο επιτυχημένη περίπτωση, θα παραχθεί όχι λιγότερο από μια τάξη μεγέθους. ν 2Ενέργειες.
...Κατά την αξιολόγηση f(n) = O(n 3)εγγυάται ότι στη χειρότερη περίπτωση οι ενέργειες θα είναι κανονικές ν 3, όχι περισσότερο.

Χρησιμοποιείται επίσης η εκτίμηση Θ(n)[«Θήτα από εν»], που είναι υβρίδιο Ο()Και Ω() .
Θ(n2)είναι ταυτόχρονα μια ανώτερη και μια κατώτερη ασυμπτωτική εκτίμηση - η σειρά ν 2επιχειρήσεις. Βαθμός Θ() υπάρχει μόνο όταν Ο()Και Ω() ταιριάζουν και ίσα.

Για τους αλγόριθμους υπολογισμού του πολυωνύμου που εξετάστηκαν παραπάνω, οι εκτιμήσεις που βρέθηκαν είναι ταυτόχρονα Ο(), Ω() Και Θ() .
Αν προσθέσουμε στον πρώτο αλγόριθμο για έλεγχο x=0σε εκθετικότητα, στη συνέχεια στα πιο επιτυχημένα αρχικά δεδομένα (όταν x=0) έχουμε τάξη nεπιταγές, 0 πολλαπλασιασμοί και 1 πρόσθεση, που δίνει μια νέα εκτίμηση Ω(n)μαζί με το παλιό O(n2).

Κατά κανόνα, η κύρια προσοχή εξακολουθεί να δίνεται στο άνω όριο Ο(), οπότε παρά τη «βελτίωση», ο Αλγόριθμος 2 παραμένει προτιμότερος.

Ετσι, Ο()- ασυμπτωτική εκτίμηση του αλγορίθμου για τα χειρότερα δεδομένα εισόδου, Ω() - στα καλύτερα δεδομένα εισόδου, Θ() - συνοπτική σημειογραφία του ίδιου Ο()Και Ω() .

Για τη θεωρητική ανάλυση, δεν είναι μια συγκεκριμένη συνάρτηση που περιγράφει την εξάρτηση του χρόνου εκτέλεσης από τον αριθμό των δεδομένων εισόδου, αλλά η σειρά ανάπτυξής του για μεγάλο Ν. που είναι η πιο κατάλληλη μέτρηση. Τα βασικά ζητήματα είναι, πρώτον, ο καθορισμός της δυνατότητας μιας λύσης υπολογιστή σε πεπερασμένο αποδεκτό χρόνο κατ' αρχήν και, δεύτερον, η σύγκριση εναλλακτικών λύσεων και η απόρριψη ακατάλληλων αλγορίθμων ακόμη και πριν καταβληθούν προσπάθειες για την επίτευξη της πλήρους ποιότητας τους. εκτέλεση.

Με άλλα λόγια, τον καθοριστικό ρόλο παίζει ασυμπτωτική εκτίμησηυπολογιστική πολυπλοκότητα του αλγορίθμου. Ας πάρουμε το όριο από την παραπάνω σχέση για τον αλγόριθμο ταξινόμησης με φυσαλίδες, με τον αριθμό των δεδομένων εισόδου N να τείνει στο άπειρο:

Στην οριακή εκτίμηση, οι χαμηλότερες δυνάμεις απορρίπτονται επειδή κυριαρχούν οι υψηλότερες δυνάμεις. Έτσι, ο χρόνος εκτέλεσης του αλγορίθμου ταξινόμησης με φυσαλίδες έχει μια τετραγωνική εξάρτηση από την ποσότητα των δεδομένων εισόδου.

ΣΕ γενική εικόνα, ο χρόνος εκτέλεσης οποιουδήποτε αλγορίθμου μπορεί να αναπαρασταθεί ως εξής:

Κατά τη μελέτη των ιδιοτήτων και τη σύγκριση αλγορίθμων, μπορούμε να απορρίψουμε τον σταθερό παράγοντα, αφού για αρκετά μεγάλο Ν, είναι η σειρά ανάπτυξης της συνάρτησης που είναι ο καθοριστικός παράγοντας. Αυτό είναι εύκολο να εξηγηθεί με ένα παράδειγμα. Ας υποθέσουμε ότι υπάρχουν 2 εναλλακτικοί αλγόριθμοι, ο πρώτος έχει τετραγωνική σειρά ανάπτυξης και ο δεύτερος περιγράφεται από μια γραμμική συνάρτηση. Υποθέτουμε επίσης ότι η υλοποίηση του πρώτου αλγορίθμου είναι κοντά στο βέλτιστο και το πρόγραμμα εκτελείται σε σύγχρονο υπολογιστή. Ταυτόχρονα, η υλοποίηση του δεύτερου αλγορίθμου απέχει πολύ από το να είναι εξαιρετική και εκτελείται σε έναν ξεπερασμένο υπολογιστή. Τέτοια ανισορροπία εξωτερικές συνθήκεςμπορεί να μοντελοποιηθεί χρησιμοποιώντας τη διαφορά σε σταθερούς παράγοντες (έστω, α, α). Για μικρό N, για παράδειγμα, με 5 δεδομένα, ο χρόνος εκτέλεσης του πρώτου αλγορίθμου θα είναι μικρότερος από τον δεύτερο:

Ωστόσο, καθώς ο αριθμός των εισόδων αυξάνεται, ο δεύτερος αλγόριθμος, ο οποίος έχει καλύτερη υπολογιστική πολυπλοκότητα, θα έχει καλύτερη απόδοση από τον πρώτο, παρά όλους τους ατυχείς παράγοντες:

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

Για αναλυτικό συλλογισμό σχετικά με ασυμπτωτικές εκτιμήσεις της υπολογιστικής πολυπλοκότητας των αλγορίθμων, πολλές μαθηματικές σημειώσεις χρησιμοποιούνται στη βιβλιογραφία ταυτόχρονα - O-estimate, -estimate και -estimate.

Η εκτίμηση είναι μια σύγκριση με ένα άπειρο σύνολο συναρτήσεων με την ίδια τάξη ανάπτυξης, που διαφέρουν κατά σταθερό παράγοντα. Μια συνάρτηση ανήκει στο σύνολο εάν υπάρχουν σταθερές u που, για αρκετά μεγάλο N, περιορίζουν τη συνάρτηση από πάνω και κάτω, η οποία περιγράφει την ταχύτητα του αλγορίθμου που αναλύθηκε. Έτσι, ισχύει η ακόλουθη σχέση:

Ο εκτιμητής Ο είναι ένα υποσύνολο του -εκτιμητή που περιορίζει τη λειτουργία του αναλυόμενου αλγορίθμου μόνο από πάνω. Με άλλα λόγια, ο εκτιμητής Ο περιγράφει ασυμπτωτικά τη χειρότερη περίπτωση για τον αναλυόμενο αλγόριθμο. Αυτή η εκτίμηση χρησιμοποιείται συχνότερα στην ανάλυση. Πολύ λιγότερο συχνά χρησιμοποιείται μια εκτίμηση που περιορίζει τη λειτουργία του αναλυόμενου αλγορίθμου από κάτω (η καλύτερη περίπτωση).

Μεταξύ των τυπικών ασυμπτωτικών εκτιμήσεων της υπολογιστικής πολυπλοκότητας των αλγορίθμων, οι ακόλουθες συναρτήσεις είναι κοινές:

γραμμικό O(N) (χρόνος ανάλογος με την αύξηση των δεδομένων).

τετραγωνικό O(N 2);

πολυωνυμική πολυπλοκότητα O(N M), ειδικότερα, κυβική πολυπλοκότητα O(N 3);

εκθετική πολυπλοκότητα O(2 N);

παραγοντική πολυπλοκότητα O(N!);

λογαριθμική πολυπλοκότητα O(log(N)) (υποδηλώνει λογάριθμο βάσης 2);

γραμμική-λογαριθμική πολυπλοκότητα O(N * log(N)) ;

σταθερή υπολογιστική πολυπλοκότητα O(1) (ο χρόνος δεν εξαρτάται από την ποσότητα των δεδομένων).

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

Η υπολογιστική πολυπλοκότητα των αναπτυγμένων αλγορίθμων θα πρέπει να είναι όσο το δυνατόν περιορισμένη. Η σχέση μεταξύ αυτών των εκτιμήσεων μπορεί να γίνει αισθητή αντιπροσωπεύοντας τον αριθμό των εντολών που εκτελούνται σε συγκεκριμένα παραδείγματα, ας πούμε σε N=5, 10, 25, 100 και 500 (υποθέτουμε ότι οι σταθεροί συντελεστές είναι οι ίδιοι για ευκολία κατανόησης). Με αυτόν τον όγκο δεδομένων, έχουμε τους ακόλουθους δείκτες:

				τόσα πολλά	τόσα πολλά
			τόσα πολλά	τόσα πολλά	τόσα πολλά

Η σταθερή υπολογιστική πολυπλοκότητα είναι μια ιδανική περίπτωση, συχνά αλγόριθμοι με τέτοια πολυπλοκότητα απλά δεν υπάρχουν για την επίλυση προβλημάτων. Η λογαριθμική συνάρτηση αναπτύσσεται επίσης σχετικά αργά. Οι γραμμικές και οι γραμμικές-λογαριθμικές συναρτήσεις αναπτύσσονται με αποδεκτό ρυθμό. Άλλες λειτουργίες αναπτύσσονται αισθητά πιο γρήγορα.

Εάν το πρόγραμμα ανήκει στην έρευνα, η μέγιστη επιτρεπόμενη πολυπλοκότητα είναι πολυωνυμική, ιδίως κυβική. Οι αλγόριθμοι με υψηλότερη υπολογιστική πολυπλοκότητα ισχύουν μόνο για μικρές τιμές του N, διαφορετικά τα προβλήματα δεν έχουν λύση υπολογιστή με εφικτό υπολογιστικό κόστος.

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

Μια επιφανειακή εκτίμηση της υπολογιστικής πολυπλοκότητας

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

Ακολουθούν μερικές συμβουλές για μια επιφανειακή εκτίμηση της υπολογιστικής πολυπλοκότητας «με το μάτι» χωρίς μια αυστηρή αναλυτική προσέγγιση.

Όλες οι στοιχειώδεις εντολές - αξιολόγηση εκφράσεων, ανάθεση μεταβλητής, είσοδος-έξοδος, επιστροφή τιμής - θα πρέπει να θεωρούνται ως τα απλούστερα μπλοκ με σταθερή υπολογιστική πολυπλοκότητα O(1).

Η υπολογιστική πολυπλοκότητα μιας ακολουθίας εντολών είναι ίση με τη μέγιστη πολυπλοκότητα των εντολών που περιλαμβάνονται σε αυτήν.

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

Εάν η εντολή βρίσκεται στο σώμα του βρόχου, ο αριθμός των επαναλήψεων του οποίου εξαρτάται από το N, τότε η υπολογιστική πολυπλοκότητα της εντολής πολλαπλασιάζεται με μια γραμμική συνάρτηση.

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

Εάν ένας αλγόριθμος χωρίζει ένα σύνολο εισόδων σε κομμάτια και στη συνέχεια τα επεξεργάζεται ξεχωριστά από τον ίδιο αλγόριθμο αναδρομικά - η υπολογιστική πολυπλοκότητα είναι λογαριθμική.

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

ενθπαραγοντικό( ενθ _Χ)

αν(_Χ< 1)

ΕΠΙΣΤΡΟΦΗ 0;

αλλιώς αν(_x==1)

ΕΠΙΣΤΡΟΦΗ 1;

ΕΠΙΣΤΡΟΦΗ _x * παραγοντικό (_x - 1);

Οι δύο πρώτοι κλάδοι της κύριας συνθήκης είναι στοιχειώδεις εντολές, η υπολογιστική τους πολυπλοκότητα εκτιμάται ως O(1). Όσο για τον τελευταίο κλάδο, η πολυπλοκότητα περιγράφεται από το λεγόμενο επαναλαμβανόμενη σχέση:

Για να ληφθεί μια εκτίμηση της υπολογιστικής πολυπλοκότητας, οι σχέσεις επανάληψης πρέπει να επεκταθούν αναλυτικά. Αντικαθιστώντας τις απαντήσεις στον υποδεικνυόμενο τύπο πολυπλοκότητας για τον παραγοντικό βήμα προς βήμα, παίρνουμε μια γραμμική σχέση.

Ανάλυση αλγορίθμου –

Είδη ανάλυσης

Χειρότερη περίπτωση: T(n)

Μεσαία περίπτωση: T(n)

Ασυμπτωτική εκτίμηση

Ο

f (n) = O(g(n))

($c > 0, n 0 >

O(g(n)) = (f (n) : $ c > 0, n 0 >

Παράδειγμα: 2n2 = O(n3)

Συγχώνευση ταξινόμησης

αν (σελ< r) //1

Δέντρο αναδρομής: T(n) = 2*T(n/2) +cn, σ –const, c>0

Τεχνική αξιολόγησης αναδρομικών αλγορίθμων.

Μέθοδος επανάληψης

Με βάση τον τύπο T(n), γράφουμε τον τύπο για το μικρότερο στοιχείο που βρίσκεται στη δεξιά πλευρά του τύπου για το T(n).

Αντικαθιστούμε τη δεξιά πλευρά του προκύπτοντος τύπου στον αρχικό τύπο

Εκτελούμε τα δύο πρώτα βήματα μέχρι να επεκτείνουμε τον τύπο σε μια σειρά χωρίς τη συνάρτηση T(n)

Υπολογίστε τη σειρά που προκύπτει με βάση μια αριθμητική ή γεωμετρική πρόοδο

Τ(η)=Τ(η-1)+η, Τ(1)=1

T(n)=θ(g(n)), g(n)=?

T(n-1)=T(n-2)+(n-1)

T(n-2)=T(n-3)+(n-2)

T(n-3)+(n-2)+(n-1)+n=…

1+…(n-2)+(n-1)+n=

Δέντρο αναδρομής - μια γραφική μέθοδος για την εμφάνιση μιας αντικατάστασης σχέσης αυτο-προς-εαυτό

T(n)=2T(n/2)+n 2

T(n/4) T(n/4) T(n/4) T(n/4)

(n/2) 2 (n/2) 2 log n (1/2)*n 2

(n/4) 2 (n/4) 2 (n/4) 2 (n/4) 2 (1/4)*n 2

Μέθοδος Αντικατάστασης

1. Μαντέψτε (προτείνετε) μια λύση
2. Ελέγξτε το διάλυμα χρησιμοποιώντας επαγωγή
3. Βρείτε και αντικαταστήστε σταθερές

T(n) = 2T(n/2) + n

T(n) = (n log n)

Προϋπόθεση επαγωγής: T(n) ≤ σ * n* log n, c>0

Ας ισχύει αυτή η εκτίμηση για n/2

T(n/2) ≤ c*(n/2)*log(n/2)

Αντικαταστήστε το στην αρχική φόρμουλα για T(n)

T(n) ≤ 2*(c*(n/2)*log(n/2))+n ≤

c*n*log(n/2)+n =

c*n*log n - c*n*log 2 +n =

c*n*log n - c*n +n ≤

c*n*log n

c≥1, n≥2

Κύριο θεώρημα για τους αναδρομικούς εκτιμητές

T (n) = aT (n/b) + f (n), a ≥ 1, b > 1, f (n) − (f (n) > 0, n > n0)

Αλγόριθμοι ταξινόμησης πινάκων σε πολυωνυμικό χρόνο

Ταξινόμηση - η διαδικασία αναδιάταξης αντικειμένων ενός δεδομένου

αδρανή με συγκεκριμένη σειρά (αύξηση

ή μειώνεται).

Ο σκοπός της διαλογής είναι συνήθως η διευκόλυνση της μετέπειτα

αναζήτηση στοιχείων σε ένα ταξινομημένο σύνολο.

Ταξινόμηση με απλές εισαγωγές

void sort_by_insertion(key a , int N)

για (i=1; i< N; i++)

για (j=i-1; (j>=0)&& (x< a[j]); j--)

a = a[j];

Ανάλυση ταξινόμησης με απλές εισαγωγές

Αριθμός συγκρίσεων:

C (N) \u003d 1 + 2 + 3 + ... + N - 1 \u003d (N * (N -1)) / 2 \u003d O (N 2)

Συνολικός χρόνος: T(N) = θ(N 2)

Ταξινόμηση με απλή ανταλλαγή. μέθοδος φούσκας.

void bubble_sort (κλειδί a , int N)

για (i=0; i

για (j=N-l; j>i; j--)

αν (a > a[j]) (

x = a[j] ; a [ j ] = a [ j -1] ; a[j-1]=x;

Απλή Ανάλυση Ταξινόμησης Ανταλλαγής

Η χειρότερη περίπτωση: παραγγέλθηκε αντίστροφη σειράπίνακας

Αριθμός συγκρίσεων:

C(N) = (N - 1) + (N - 2) + ... + 1 = (N * (N-1))/2 = O(N 2)

Συνολικός χρόνος: T(N) = θ(N 2)

Προσθήκη

Κόμβος* _Προσθήκη(Κόμβος *r, T s)

r = νέος κόμβος;

αλλιώς εάν(s< r->στ)

r->left = _Add(r->left, s);

r->right = _Add(r->right, s);

Αφαίρεση στοιχείου από το δέντρο

Δέντρο Τ με ρίζα n και κλειδί Κ.

αφαιρέστε από το δέντρο Τ τον κόμβο με το κλειδί Κ (αν υπάρχει).

Αλγόριθμος:

Εάν το δέντρο T είναι κενό, σταματήστε.

Διαφορετικά, συγκρίνετε το K με το κλειδί X του ριζικού κόμβου n.

Εάν K>X, αφαιρέστε αναδρομικά το K από το δεξί υποδέντρο του T.

Αν ο Κ

Αν K=X, τότε είναι απαραίτητο να εξεταστούν τρεις περιπτώσεις.

Εάν δεν υπάρχουν και τα δύο παιδιά, τότε διαγράφουμε τον τρέχοντα κόμβο και επαναφέρουμε τον σύνδεσμο προς αυτόν από τον γονικό κόμβο.

Εάν ένα από τα παιδιά δεν υπάρχει, τότε βάζουμε τις τιμές των πεδίων του παιδιού m αντί για τις αντίστοιχες τιμές του ριζικού κόμβου, αντικαθιστώντας τις παλιές του τιμές και ελευθερώνοντας τη μνήμη που καταλαμβάνει ο κόμβος m.

Εάν υπάρχουν και τα δύο παιδιά, τότε βρίσκουμε τον κόμβο m, ο οποίος είναι ο επόμενος μετά το δεδομένο.

αντιγράψτε τα δεδομένα (εκτός από αναφορές σε θυγατρικά στοιχεία) από m έως n.

αφαιρέστε αναδρομικά τον κόμβο m.

Το στοιχείο που ακολουθεί το δεδομένο

Δίνονται: δέντρο Τ και κλειδί x

Επιστρέφουμε έναν δείκτη στο επόμενο στοιχείο μετά το x ή NULL αν το x είναι το τελευταίο στοιχείο στο δέντρο.

Αλγόριθμος:

Εξετάζουμε δύο περιπτώσεις χωριστά.

Εάν το δεξί υποδέντρο του x δεν είναι κενό, τότε το επόμενο στοιχείο μετά το x είναι το ελάχιστο στοιχείο σε αυτό το υποδέντρο.

Διαφορετικά, αν το δεξί υποδέντρο του x είναι κενό. Ανεβαίνουμε από το x μέχρι να βρούμε μια κορυφή που είναι το αριστερό παιδί του γονέα της. Αυτός ο γονέας (αν υπάρχει) θα είναι το στοιχείο που αναζητάτε.

Εισαγωγή κόμβων

Η εισαγωγή ενός νέου κλειδιού σε ένα δέντρο AVL γίνεται με τον ίδιο τρόπο όπως γίνεται στα απλά δέντρα αναζήτησης: κατεβαίνουμε στο δέντρο, επιλέγοντας τη δεξιά ή την αριστερή κατεύθυνση κίνησης, ανάλογα με το αποτέλεσμα της σύγκρισης του κλειδιού στον τρέχοντα κόμβο και το κλειδί εισάγεται.

Η μόνη διαφορά είναι ότι όταν η αναδρομή επιστρέφει (δηλαδή μετά την εισαγωγή του κλειδιού είτε στο δεξί είτε στο αριστερό υποδέντρο), ο τρέχων κόμβος εξισορροπείται. Η ανισορροπία που προκύπτει από μια τέτοια εισαγωγή σε οποιονδήποτε κόμβο κατά μήκος της διαδρομής κίνησης δεν υπερβαίνει τα δύο, πράγμα που σημαίνει ότι η εφαρμογή της συνάρτησης εξισορρόπησης που περιγράφεται παραπάνω είναι σωστή.

Αφαίρεση κόμβων

Για να αφαιρέσετε μια κορυφή από ένα δέντρο AVL, λαμβάνεται ως βάση ένας αλγόριθμος, ο οποίος χρησιμοποιείται συνήθως κατά την αφαίρεση κόμβων από ένα τυπικό δυαδικό δέντρο αναζήτησης. Βρίσκουμε τον κόμβο p με το δεδομένο κλειδί k, στο δεξί υποδέντρο βρίσκουμε τον κόμβο min με το μικρότερο κλειδί και αντικαθιστούμε τον κόμβο p που αφαιρέθηκε με τον κόμβο min που βρέθηκε.

Υπάρχουν πολλές επιλογές για υλοποίηση. Πρώτα απ 'όλα, εάν ο κόμβος p που βρέθηκε δεν έχει δεξί υποδέντρο, τότε, λόγω της ιδιότητας του δέντρου AVL, αυτός ο κόμβος μπορεί να έχει μόνο έναν θυγατρικό κόμβο (ένα δέντρο ύψους 1) στα αριστερά ή τον κόμβο p στο γενική είναι ένα φύλλο. Και στις δύο αυτές περιπτώσεις, χρειάζεται απλώς να διαγράψετε τον κόμβο p και να επιστρέψετε έναν δείκτη στον αριστερό θυγατρικό κόμβο του κόμβου p ως αποτέλεσμα.

Τώρα ας έχει το p ένα δεξί υποδέντρο. Βρείτε το ελάχιστο κλειδί σε αυτό το υποδέντρο. Ως ιδιότητα ενός δυαδικού δέντρου αναζήτησης, αυτό το κλειδί βρίσκεται στο τέλος του αριστερού κλάδου, ξεκινώντας από τη ρίζα του δέντρου. Χρησιμοποιούμε την αναδρομική συνάρτηση findmin.

Συνάρτηση removemin - αφαιρώντας το ελάχιστο στοιχείο από το δεδομένο δέντρο. Με την ιδιότητα ενός δέντρου AVL, το ελάχιστο στοιχείο στα δεξιά είτε έχει έναν μόνο κόμβο είτε είναι κενό. Και στις δύο περιπτώσεις, χρειάζεται απλώς να επιστρέψετε έναν δείκτη στον δεξιό κόμβο και να εκτελέσετε εξισορρόπηση κατά την επιστροφή (όταν επιστρέφετε από την αναδρομή).

Τραπέζια κατακερματισμού, μέθοδος αλυσίδων

Η άμεση διευθυνσιοδότηση χρησιμοποιείται για μικρά σετ κλειδιών. Απαιτείται να καθοριστεί ένα δυναμικό σύνολο, κάθε στοιχείο του οποίου έχει ένα κλειδί από το σύνολο U = (0,1,..., m - 1), όπου το m δεν είναι πολύ μεγάλο, κανένα στοιχείο δεν έχει τα ίδια κλειδιά.

Για την αναπαράσταση ενός δυναμικού συνόλου, χρησιμοποιείται ένας πίνακας (πίνακας με άμεση διευθυνσιοδότηση), T , κάθε θέση ή κελί του οποίου αντιστοιχεί σε ένα κλειδί από το χώρο κλειδιού U.

Το κελί k δείχνει σε ένα στοιχείο του συνόλου με το κλειδί k. Εάν το σύνολο δεν περιέχει στοιχείο με κλειδί k, τότε Т[k] = NULL.

Η λειτουργία αναζήτησης κλειδιού απαιτεί χρόνο O(1)

Μειονεκτήματα της άμεσης διεύθυνσης:

Εάν ο χώρος κλειδιού U είναι μεγάλος, αποθηκεύστε τον πίνακα T με μέγεθος |U| μη πρακτικό, αν όχι αδύνατο, ανάλογα με την ποσότητα της διαθέσιμης μνήμης και το μέγεθος του χώρου πλήκτρων

Το σύνολο K των πραγματικά αποθηκευμένων κλειδιών μπορεί να είναι μικρό σε σύγκριση με το χώρο κλειδιών U, οπότε η μνήμη που εκχωρείται στον πίνακα T σπαταλιέται κυρίως.

Μια συνάρτηση κατακερματισμού είναι μια συνάρτηση h που εντοπίζει τα στοιχεία του συνόλου U στον πίνακα T.

Στον κατακερματισμό, το στοιχείο με το κλειδί k αποθηκεύεται στη θέση h(k), η συνάρτηση κατακερματισμού h χρησιμοποιείται για τον υπολογισμό της θέσης για το δεδομένο κλειδί k. Η συνάρτηση h αντιστοιχίζει το χώρο κλειδιού U στα κελιά του πίνακα κατακερματισμού T [O..m - 1]:

h: U → (0,1,...,m-1).

η τιμή h(k) ονομάζεται τιμή κατακερματισμού του κλειδιού k.

Όταν το σύνολο K των κλειδιών που είναι αποθηκευμένο σε ένα λεξικό είναι πολύ μικρότερο από το χώρο των πιθανών κλειδιών U, ο πίνακας κατακερματισμού απαιτεί σημαντικά λιγότερο χώρο από έναν απευθείας διευθύνσιμο πίνακα.

Ο σκοπός της συνάρτησης κατακερματισμού είναι να μειώσει το εύρος εργασίας των δεικτών πίνακα και αντί για |U| τιμές, μπορείτε να τα βγάλετε πέρα ​​μόνο με τιμές m.

Οι απαιτήσεις μνήμης μπορούν να μειωθούν σε θ(|K|), ενώ ο χρόνος αναζήτησης ενός στοιχείου σε έναν πίνακα κατακερματισμού παραμένει O(1) - αυτό είναι το όριο στον μέσο χρόνο αναζήτησης, ενώ στην περίπτωση ενός πίνακα με άμεση διεύθυνση, αυτό το όριο ισχύει για τη χειρότερη περίπτωση.

Μια σύγκρουση είναι μια κατάσταση όπου δύο πλήκτρα αντιστοιχίζονται στο ίδιο κελί.

Για παράδειγμα, h(43) = h(89) = h(112) = k

Μέθοδος αλυσίδας:

Ιδέα: Αποθηκεύστε στοιχεία ενός συνόλου με την ίδια τιμή κατακερματισμού με μια λίστα.

h(51) = h(49) = h(63) = i

Ανάλυση

Η χειρότερη περίπτωση: εάν η συνάρτηση κατακερματισμού για όλα τα στοιχεία του συνόλου παράγει την ίδια τιμή. Ο χρόνος πρόσβασης είναι Θ(n), για |U | = n.

Μεσαία περίπτωση: Για την περίπτωση που οι τιμές κατακερματισμού είναι ομοιόμορφα κατανεμημένες.

Κάθε κλειδί με ίση πιθανότητα μπορεί να μπει σε οποιοδήποτε κελί του πίνακα, ανεξάρτητα από το πού βρέθηκαν τα άλλα κλειδιά.

Ας δοθεί ο πίνακας T και n κλειδιά αποθηκεύονται σε αυτόν.

Τότε, a = n/m είναι ο μέσος αριθμός κλειδιών στα κελιά του πίνακα.

Ο χρόνος αναζήτησης για το στοιχείο που λείπει είναι Θ(1 + α).

Ο σταθερός χρόνος για τον υπολογισμό της τιμής κατακερματισμού συν το χρόνο για να περάσετε από τη λίστα μέχρι το τέλος, επειδή το μέσο μήκος της λίστας είναι α, τότε το αποτέλεσμα είναι Θ(1) + Θ(α) = Θ(1 + α)

Εάν ο αριθμός των κελιών του πίνακα είναι ανάλογος με τον αριθμό των στοιχείων που είναι αποθηκευμένα σε αυτόν, τότε n = O(m) και, επομένως, α = n/m = O(m)/m = O(1), που σημαίνει ότι το Η αναζήτηση ενός στοιχείου στον πίνακα κατακερματισμού απαιτεί κατά μέσο όρο χρόνο Θ(1).

Λειτουργίες

Εισαγωγή στοιχείου σε πίνακα

Μετακίνηση

απαιτούν επίσης χρόνο O(1).

Επιλογή συνάρτησης κατακερματισμού

Τα κλειδιά πρέπει να κατανέμονται ομοιόμορφα σε όλα τα κελιά

Το μοτίβο διανομής κλειδιού κατακερματισμού δεν πρέπει να συσχετίζεται με μοτίβα δεδομένων. (Για παράδειγμα, τα δεδομένα είναι ζυγοί αριθμοί.)

Μέθοδοι:

μέθοδος διαίρεσης

μέθοδος πολλαπλασιασμού

μέθοδος διαίρεσης

h(k) = k mod m

Πρόβλημα μικρού διαιρέτη m

Παράδειγμα #1. m = 2και όλα τα κλειδιά είναι ζυγά Þ τα περιττά κελιά δεν είναι

γέματο.

Παράδειγμα #2. m = 2rΟ κατακερματισμός είναι ανεξάρτητος από τα bit στο παραπάνω r.

μέθοδος πολλαπλασιασμού

Αφήνω Μ= 2 r , τα πλήκτρα είναι λέξεις w-bit.

h(k) = (A k mod 2 w) >> (w - r),Οπου

A mod 2 = 1 ∩ 2 w-1< A< 2 w

Δεν πρέπει να επιλέξει ΕΝΑκοντά σε 2 w-1Και 2w

Αυτή η μέθοδος ταχύτερη μέθοδοςδιαίρεση

Μέθοδος πολλαπλασιασμού: παράδειγμα

m = 8 = 2 3, w = 7

Άνοιγμα διευθυνσιοδότησης: αναζήτηση

Η αναζήτηση είναι επίσης διαδοχική έρευνα

Επιτυχία όταν βρεθεί το νόημα

Αποτυχία όταν βρέθηκε ένα κενό κελί ή πέρασε ολόκληρος ο πίνακας.

Στρατηγικές έρευνας

Γραμμικός -

h(k, i) = (h′(k) + i) mod m

Αυτή η στρατηγική είναι εύκολο να εφαρμοστεί, αλλά υπόκειται στο πρόβλημα

πρωτογενής ομαδοποίηση που σχετίζεται με τη δημιουργία μιας μεγάλης ακολουθίας

αριθμός κατειλημμένων κελιών, γεγονός που αυξάνει τον μέσο χρόνο αναζήτησης.

τετραγωνικός

h(k, i) = (h′(k) + с 1 i+ с 2 i 2) mod m

όπου h′(k) είναι η συνήθης συνάρτηση κατακερματισμού

Διπλός κατακερματισμός -

h(k,i) = (h 1 (k) + i h 2 (k)) mod m.

διπλός κατακερματισμός

Αυτή η μέθοδος δίνει εξαιρετικά αποτελέσματα, αλλά το h 2 (k) πρέπει να είναι σχετικά πρώτο στο m.

Αυτό μπορεί να επιτευχθεί:

χρησιμοποιώντας δυνάμεις του 2 ως m και κάνοντας h 2 (k) παράγουμε μόνο περιττούς αριθμούς

m = 2 r και h 2 (k)- Περιττός.

Μ- πρώτος αριθμός, τιμές Οι h 2 είναι θετικοί ακέραιοι μικρότεροι από m

Για απλά m μπορεί να εγκατασταθεί

h1(k)=k mod m

h2(k)=1+(k mod m')

Το m' είναι μικρότερο από το m (m' =m-1 ή m-2)

Ανοίξτε τη Διεύθυνση: Επικόλληση Παράδειγμα

Έστω ο πίνακας Α:

διπλός κατακερματισμός

h2(k)=1+(k mod 11)

Πού θα ενσωματωθεί το στοιχείο;

Ανοιχτή ανάλυση διευθύνσεων

Μια επιπλέον υπόθεση για ομοιόμορφο κατακερματισμό είναι ότι κάθε κλειδί είναι εξίσου πιθανό να λάβει οποιοδήποτε από τα m! μεταθέσεις ακολουθιών μελέτης πίνακα

ανεξάρτητα από άλλα κλειδιά.

Εύρεση στοιχείου που λείπει

Αριθμός ανιχνευτών για μια επιτυχημένη αναζήτηση

ανοιχτή διεύθυνση

ΕΝΑ< 1 - const Þ O(1)

Πώς συμπεριφέρεται ΕΝΑ:

Ο πίνακας ολοκληρώθηκε μελέτη 50% Þ2

Πίνακας 90% πλήρης Þ 10 μελέτες

Πίνακας 100% ολοκληρωμένες μελέτες Þ m

Η αρχή της άπληστης επιλογής

Λέγεται ότι για ένα πρόβλημα βελτιστοποίησης εφαρμόζουμε αρχή της άπληστης επιλογής, εάν η ακολουθία είναι τοπική βέλτιστες επιλογέςδίνει μια παγκόσμια βέλτιστη λύση.

Σε μια τυπική περίπτωση, η απόδειξη βελτιστοποίησης ακολουθεί το ακόλουθο σχήμα:

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

Αποδεικνύεται ότι το υποπρόβλημα που προκύπτει μετά την άπληστη επιλογή στο πρώτο βήμα είναι παρόμοιο με το αρχικό.

Το επιχείρημα τελειώνει με επαγωγή.

Βελτιστότητα για δευτερεύουσες εργασίες

Το καθήκον λέγεται ότι έχει την ιδιοκτησία βέλτιστη για υποπροβλήματα, εάν η βέλτιστη λύση του προβλήματος περιέχει τις βέλτιστες λύσεις για όλα τα υποπροβλήματά του.

Δημιουργία του κώδικα Huffman

Οποιοδήποτε μήνυμα αποτελείται από μια ακολουθία χαρακτήρων κάποιου αλφαβήτου. Συχνά, για να εξοικονομήσετε μνήμη, για να αυξήσετε την ταχύτητα μεταφοράς πληροφοριών, προκύπτει το έργο της συμπίεσης πληροφοριών. Σε αυτή την περίπτωση, χρησιμοποιούνται ειδικές μέθοδοι κωδικοποίησης χαρακτήρων. Σε αυτούς περιλαμβάνονται οι κώδικες Huffman, οι οποίοι δίνουν συμπίεση από 20% έως 90% ανάλογα με τον τύπο της πληροφορίας.

Ο αλγόριθμος Huffman βρίσκει τους βέλτιστους κωδικούς χαρακτήρων με βάση τη συχνότητα των χαρακτήρων στο συμπιεσμένο κείμενο.

Ο αλγόριθμος του Huffman είναι ένα παράδειγμα ενός άπληστου αλγορίθμου.

Αφήστε τις συχνότητες χαρακτήρων να είναι γνωστές σε ένα αρχείο μήκους 100000 χαρακτήρων:

Πρέπει να δημιουργήσουμε έναν δυαδικό κώδικα στον οποίο κάθε χαρακτήρας αναπαρίσταται ως μια πεπερασμένη ακολουθία bit, που ονομάζεται κωδική λέξη. Όταν χρησιμοποιείτε έναν ενιαίο κώδικα, στον οποίο όλες οι κωδικές λέξεις έχουν το ίδιο μήκος, δαπανώνται τουλάχιστον τρία bit σε κάθε χαρακτήρα και 300.000 bit σε ολόκληρο το αρχείο.

Ένας ανομοιόμορφος κώδικας θα είναι πιο οικονομικός εάν οι συχνά εμφανιζόμενοι χαρακτήρες κωδικοποιούνται με σύντομες ακολουθίες bit και οι χαρακτήρες που εμφανίζονται σπάνια με μακριές. Κατά την κωδικοποίηση ολόκληρου του αρχείου, θα χρειαστεί (45*1 + 13*3 + 12*3 + 16*3 + 9*4 + 5*4)*1000 = 224000. Δηλαδή, ένας ανομοιόμορφος κωδικός δίνει περίπου 25% εξοικονόμηση .

Κωδικοί προθέματος

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

Κατά την κωδικοποίηση, κάθε χαρακτήρας αντικαθίσταται από τον δικό του κωδικό. Για παράδειγμα, η συμβολοσειρά abc μοιάζει με 0101100. Για έναν κωδικό προθέματος, η αποκωδικοποίηση είναι μοναδική και γίνεται από αριστερά προς τα δεξιά.

Ο πρώτος χαρακτήρας ενός κειμένου που κωδικοποιείται με κωδικό προθέματος καθορίζεται μοναδικά, καθώς η κωδική λέξη του δεν μπορεί να είναι η αρχή οποιουδήποτε άλλου χαρακτήρα. Έχοντας καθορίσει αυτόν τον χαρακτήρα και απορρίψαμε την κωδική του λέξη, επαναλαμβάνουμε τη διαδικασία για τα υπόλοιπα bit κ.ο.κ.

Για να εφαρμόσετε αποτελεσματικά την αποκωδικοποίηση, πρέπει να αποθηκεύσετε πληροφορίες σχετικά με τον κώδικα σε μια βολική μορφή. Μια δυνατότητα είναι να αναπαραστήσετε τον κώδικα στη φόρμα δυαδικό δέντρο κώδικα, τα φύλλα του οποίου αντιστοιχούν στους κωδικοποιημένους χαρακτήρες. Σε αυτήν την περίπτωση, η διαδρομή από τη ρίζα προς τον κωδικοποιημένο χαρακτήρα καθορίζει την κωδικοποιητική ακολουθία των bit: η κίνηση κατά μήκος του δέντρου προς τα αριστερά δίνει 0 και η μετακίνηση προς τα δεξιά δίνει 1.

Οι εσωτερικοί κόμβοι δείχνουν το άθροισμα των συχνοτήτων για τα φύλλα του αντίστοιχου υποδέντρου.

Ο βέλτιστος κώδικας για ένα δεδομένο αρχείο αντιστοιχεί πάντα σε ένα δυαδικό δέντρο στο οποίο κάθε κορυφή που δεν είναι φύλλο έχει δύο γιους. Ο ενιαίος κωδικός δεν είναι βέλτιστος επειδή το αντίστοιχο δέντρο περιέχει έναν κόμβο με ένα παιδί.

Ένα βέλτιστο δέντρο κώδικα προθέματος για ένα αρχείο που χρησιμοποιεί όλους τους χαρακτήρες από κάποιο σύνολο C και μόνο αυτοί περιέχουν ακριβώς | C | φύλλα, ένα για κάθε χαρακτήρα και ακριβώς | C | - 1 κόμβοι που δεν είναι φύλλα.

Γνωρίζοντας το δέντρο T που αντιστοιχεί στον κωδικό του προθέματος, είναι εύκολο να βρείτε τον αριθμό των bit που απαιτούνται για την κωδικοποίηση του αρχείου. Για κάθε χαρακτήρα c από το αλφάβητο C, έστω f[c] ο αριθμός των φορών που εμφανίζεται στο αρχείο και dT(c) το βάθος του αντίστοιχου φύλλου του και επομένως το μήκος της ακολουθίας bit που κωδικοποιεί το c. Στη συνέχεια, για να κωδικοποιήσετε το αρχείο θα χρειαστείτε:

Αυτή η τιμή ονομάζεται κόστος του δέντρου T. Είναι απαραίτητο να ελαχιστοποιηθεί αυτή η τιμή.

Huffmanπρότεινε έναν άπληστο αλγόριθμο που δημιουργεί έναν βέλτιστο κώδικα προθέματος. Ο αλγόριθμος δημιουργεί ένα δέντρο T που αντιστοιχεί στον βέλτιστο κώδικα από κάτω προς τα πάνω, ξεκινώντας με ένα σύνολο | C | φύλλα και φτιάχνοντας | C | - 1 συγχώνευση.

Για κάθε σύμβολο δίνεται η συχνότητά του f [c]. Για να βρείτε δύο αντικείμενα προς συγχώνευση, χρησιμοποιείται μια ουρά προτεραιότητας Q, χρησιμοποιώντας τις συχνότητες f ως προτεραιότητες - τα δύο αντικείμενα με τις χαμηλότερες συχνότητες συγχωνεύονται.

Ως αποτέλεσμα της συγχώνευσης, προκύπτει ένα νέο αντικείμενο (εσωτερική κορυφή), η συχνότητα του οποίου θεωρείται ίση με το άθροισμα των συχνοτήτων των δύο συγχωνευμένων αντικειμένων. Αυτή η κορυφή προστίθεται στην ουρά.

Χάφμαν ντο)

1.n ←│C│ │ ντο │- ισχύς С

2.Q ← ντο Q - ουρά προτεραιότητας

3. Για i ← 1 προς την n-1

4. κάνω z ← Create_Node() z είναι ένας κόμβος που αποτελείται από πεδία f, αριστερά, δεξιά

5. x ← αριστερά [z] ← Dequeue(Ε)

6. y ← δεξιά [z] ← Dequeue(Ε)

7. f[z] ← f[x] + f[y]

8. Ουρά(Q, z)

9. επιστροφή Dequeue(Ε) επιστροφή ρίζα δέντρου

Βαθμός

Η ουρά υλοποιείται ως δυαδικός σωρός.

Μπορείτε να δημιουργήσετε μια ουρά στο O(n).

Ο αλγόριθμος αποτελείται από έναν βρόχο που εκτελείται n-1 φορές.

Κάθε λειτουργία ουράς παίρνει O(log n).

Συνολικός χρόνος λειτουργίας O(n log n).

Το πρόβλημα της κατασκευής δικτύου

Περιοχές προέλευσης: επικοινωνιακά και οδικά δίκτυα.

Δεδομένος:σύνολο κόμβων δικτύου (κεντρικοί υπολογιστές, πόλεις).

Απαραίτητη:κατασκευή δικτύου με το μικρότερο συνολικό βάρος ακμών (μήκος καλωδίων δικτύου, μήκος δρόμων).

Μοντέλο γραφήματος:οι κόμβοι δικτύου είναι κόμβοι γραφημάτων, E = V2, γνωρίζουμε τα βάρη όλων των άκρων.

Αποτέλεσμα:ελεύθερο δέντρο.

Προσέγγιση αναζήτησης MOD

Κατασκευάζουμε το δέντρο Α προσθέτοντας μία ακμή κάθε φορά και πριν από κάθε επανάληψη, το τρέχον δέντρο είναι ένα υποσύνολο κάποιου MOD.

Σε κάθε βήμα του αλγορίθμου, ορίζουμε μια ακμή (u, v) που μπορεί να προστεθεί στο A χωρίς να παραβιαστεί αυτή η ιδιότητα. Θα ονομάσουμε μια τέτοια άκρη ασφαλή.

GenericMST(G, w)

2 ενώ το Α δεν είναι mod

3 βρείτε μια ακμή (u, v) που είναι ασφαλής για το A

4 A ← A U ((u, v))

____________________________________________________________________________

Ταξινόμηση πλευρών

1. νευρώσεις δέντρων(ακμές δέντρου) είναι οι ακμές του γραφήματος G. Μια ακμή (u, v) είναι μια άκρη δέντρου εάν το v ανακαλυφθεί κατά την εξερεύνηση αυτής της ακμής.

2. Αντίστροφες νευρώσεις(πίσω άκρα) είναι ακμές (u,v) που συνδέουν την κορυφή u με τον πρόγονό της v στο δέντρο αναζήτησης πρώτου βάθους. Οι κύκλοι ακμών που μπορεί να προκύψουν σε κατευθυνόμενα γραφήματα αντιμετωπίζονται ως πίσω ακμές.

3. ευθείες νευρώσεις(προς τα εμπρός άκρα) είναι ακμές που δεν είναι δέντρο (u,v) που συνδέουν την κορυφή u με τον απόγονό της v στο δέντρο αναζήτησης πρώτου βάθους.

4. Σταυρωτά παϊδάκια(σταυρωτές άκρες) - όλες οι άλλες άκρες του γραφήματος. Μπορούν να ενώσουν κορυφές στο ίδιο δέντρο DFS όταν καμία από τις κορυφές δεν είναι πρόγονος της άλλης ή να ενώσουν κορυφές σε διαφορετικά δέντρα.

Ο αλγόριθμος DFS μπορεί να τροποποιηθεί με τέτοιο τρόπο ώστε να ταξινομεί τις ακμές που συναντώνται κατά τη λειτουργία. Η βασική ιδέα είναι ότι κάθε ακμή (u, v) μπορεί να ταξινομηθεί με βάση το χρώμα της κορυφής v την πρώτη φορά που εξετάζεται (ωστόσο, οι ευθείες και οι σταυρωτές ακμές δεν διακρίνονται).

1. άσπρο χρώμαλέει ότι αυτή είναι μια άκρη ενός δέντρου.
2. Το γκρι χρώμα ορίζει την πίσω άκρη.
3. Το μαύρο υποδηλώνει ευθεία ή εγκάρσια άκρη.

Η πρώτη περίπτωση προκύπτει άμεσα από τον ορισμό του αλγορίθμου.

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

Στην τρίτη περίπτωση, έχουμε να κάνουμε με τις υπόλοιπες ακμές που δεν εμπίπτουν στην πρώτη ή τη δεύτερη περίπτωση. Μια ακμή (u, v) μπορεί να φανεί ευθεία αν d [u]< d [v], и перекрестным, если d [u] >d[v]

___________________________________________________________________________

Τοπολογική ταξινόμηση

ΣΕ στήλη προτεραιότηταςκάθε ακμή (u, v) σημαίνει ότι το u προηγείται του v

Τοπολογική ταξινόμησηγράφημα είναι η κατασκευή μιας ακολουθίας a, όπου για όλα τα a i και ένα j $(а i ,а j) Þ i< j.

Το τοπολογικό είδος ενός κατευθυνόμενου άκυκλου γραφήματος G = (V, E) είναι μια γραμμική διάταξη όλων των κορυφών του, έτσι ώστε αν το γράφημα G περιέχει μια ακμή (u, v) τότε το u βρίσκεται πριν από το v κάτω από αυτή τη σειρά (εάν το γράφημα δεν είναι άκυκλη, τέτοια ταξινόμηση δεν είναι δυνατή). Η τοπολογική ταξινόμηση ενός γραφήματος μπορεί να θεωρηθεί ότι ταξινομεί τις κορυφές του κατά μήκος μιας οριζόντιας γραμμής έτσι ώστε όλες οι ακμές να κατευθύνονται από αριστερά προς τα δεξιά.

Ταξινομημένη ακολουθία: C2, C6, C7, C1, C3, C4, C5, C8

για κάθε(u σε V) χρώμα[u] = λευκό; // αρχικοποίηση

L = new linked_list; // Το L είναι μια κενή συνδεδεμένη λίστα

για καθένα (u σε V)

εάν (χρώμα[u] == λευκό) TopVisit(u);

επιστροφή L; // Το L δίνει την τελική εντολή

TopVisit(u) ( // ξεκινήστε μια αναζήτηση στο u

χρώμα[u] = γκρι; // επισημάνετε ότι έχετε επισκεφθεί

για κάθε (v στο Adj(u))

εάν (χρώμα[v] == λευκό) TopVisit(v);

Προσάρτηση u στο μπροστινό μέρος του L. // όταν τελειώσετε, προσθέστε στη λίστα

T (n) = Θ(V + E)

Διαδικασίες

Δημιουργία - Ορισμός (u)- δημιουργήστε ένα σύνολο από μία κορυφή u.

Εύρεση - Σετ (u)- βρείτε το σύνολο στο οποίο ανήκει η κορυφή uεπιστρέφει σε ποιο σετβρίσκεται το καθορισμένο στοιχείο. Στην πραγματικότητα, αυτό επιστρέφει ένα από τα στοιχεία του συνόλου (καλούμενο εκπρόσωποςή ηγέτης). Αυτός ο αντιπρόσωπος επιλέγεται σε κάθε σύνολο από την ίδια τη δομή δεδομένων (και μπορεί να αλλάξει με την πάροδο του χρόνου, συγκεκριμένα μετά από κλήσεις Ενωση).

Εάν η κλήση Find - Set για οποιαδήποτε δύο στοιχεία επέστρεψε την ίδια τιμή, τότε αυτό σημαίνει ότι αυτά τα στοιχεία βρίσκονται στο ίδιο σύνολο, διαφορετικά βρίσκονται σε διαφορετικά σύνολα.

Ένωση (u,v)- συγχώνευση συνόλων που περιέχουν κορυφές uΚαι v

Τα σύνολα στοιχείων θα αποθηκευτούν στη φόρμα δέντρα: ένα δέντρο αντιστοιχεί σε ένα σύνολο. Η ρίζα του δέντρου είναι ο εκπρόσωπος (αρχηγός) του συνόλου.

Όταν υλοποιείται, αυτό σημαίνει ότι παίρνουμε έναν πίνακα μητρική εταιρεία, στο οποίο για κάθε στοιχείο αποθηκεύουμε μια αναφορά στον πρόγονό του στο δέντρο. Για τις ρίζες των δέντρων, θα υποθέσουμε ότι ο πρόγονός τους είναι ο εαυτός τους (δηλαδή, ο σύνδεσμος βρίσκεται σε αυτό το μέρος).

Για να δημιουργήσετε ένα νέο στοιχείο (λειτουργία Δημιουργία-Σετ), απλά δημιουργούμε ένα δέντρο με ρίζες στον κόμβο v, σημειώνοντας ότι ο πρόγονός του είναι ο ίδιος.

Για να συγχωνεύσετε δύο σύνολα (λειτουργία ένωση(α,β)), βρίσκουμε πρώτα τους οδηγούς του συνόλου που περιέχει το α και του συνόλου που περιέχει το β. Εάν οι ηγέτες συμπίπτουν, τότε δεν κάνουμε τίποτα - αυτό σημαίνει ότι τα σετ έχουν ήδη ενωθεί. Διαφορετικά, μπορείτε απλά να καθορίσετε ότι ο πρόγονος του κόμβου b είναι ίσος με f (ή αντίστροφα) - ενώνοντας έτσι το ένα δέντρο με το άλλο.

Τέλος, η υλοποίηση της επιχείρησης αναζήτησης ηγέτη ( Εύρεση - Σύνολο(v)) είναι απλό: ανεβαίνουμε τους προγόνους από την κορυφή v μέχρι να φτάσουμε στη ρίζα, δηλ. έως ότου συμπεριφέρεται η αναφορά προγονικού. Αυτή η λειτουργία είναι πιο βολική για την αναδρομική εφαρμογή.

Ευρετική συμπίεση διαδρομής

Αυτό το ευρετικό έχει σχεδιαστεί για να επιταχύνει τα πράγματα Εύρεση - Set() .

Βρίσκεται στο γεγονός ότι όταν, μετά την κλήση Εύρεση - Σύνολο(v)θα βρούμε τον αρχηγό που ψάχνουμε Πορίστε, στη συνέχεια να θυμάστε ότι η κορυφή vκαι όλες οι κορυφές πέρασαν στην πορεία - είναι αυτός ο ηγέτης Π. Ο ευκολότερος τρόπος για να το κάνετε αυτό είναι να τα ανακατευθύνετε μητρική εταιρείασε αυτή την κορυφή Π .

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

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

Έτσι σε μια συστοιχία μητρική εταιρείαθα πρέπει να αντιμετωπίζονται ακριβώς όπως μια συστοιχία προγόνων, πιθανώς μερικώς συμπιεσμένη.

Εφαρμογή ευρετικών συμπίεσης διαδρομής επιτρέπει σε κάποιον να επιτύχει τις λογαριθμικές ασυμπτωτικές: ανά αίτημα κατά μέσο όρο

Ανάλυση

Αρχικοποίηση - O(V)

Ο βρόχος εκτελείται V φορές και κάθε λειτουργία extractMin διαρκεί - O(logV) φορές, συνολικό O(V logV) φορές

Ο βρόχος for εκτελείται O(E) φορές, το smallKey παίρνει χρόνο O(logV).

Συνολικός χρόνος λειτουργίας - O(V log V +E logV)= O(E logV)

Ιδιότητα συντομότερης διαδρομής

Αφήνω p = (v 1 , v 2 ..... v k)- η συντομότερη διαδρομή από την κορυφή v 1 στην κορυφή v kσε ένα δεδομένο σταθμισμένο κατευθυνόμενο γράφημα G=(Η.Ε.)με λειτουργία βάρους w: E → Rένα p ij = (v i , v i+1 .....v j)- μερική διαδρομή της διαδρομής p που πηγαίνει από την κορυφή v iστην κορυφή vjγια αυθαίρετα i και j (1 ≤ i< j ≤ k). Επειτα p ijείναι το συντομότερο μονοπάτι από την κορυφή v iΠρος την v i

Dijkstra(G, w, s) (

για κάθε (u σε V) ( // αρχικοποίηση

d [u] = +άπειρο

χρώμα[u] = λευκό

d[s] =0 // η απόσταση από την πηγή είναι 0

Q = νέο PriQueue(V) // βάλτε όλες τις κορυφές στο Q

ενώ (Q.nonEmpty()) ( // έως ότου υποβληθούν σε επεξεργασία όλες οι κορυφές

u = Q. extractMin() // επιλέξτε u πιο κοντά στο s

για κάθε (v στο Adj[u]) (

αν (d[u] + w(u,v)< d[v]) { // Relax(u,v)

d[v] = d[u] + w(u,v)

Q.decreaseKey(v, d[v])

χρώμα[u] = μαύρο

Βαθμολογία δυσκολίας

Ο αλγόριθμος Bellman-Ford ολοκληρώνει το έργο του εντός χρόνου O(V*E), αφού η αρχικοποίηση στη γραμμή 1 παίρνει χρόνο O(V), για κάθε |V| - 1 περπάτημα άκρης στις γραμμές 2-4 παίρνει χρόνο O(E) και ο βρόχος for στις γραμμές 5-7 παίρνει χρόνο O(E). .

Ασυμπτωτική εκτίμηση του αλγορίθμου

Ανάλυση αλγορίθμου –θεωρητική μελέτη της απόδοσης των προγραμμάτων ηλεκτρονικών υπολογιστών και των πόρων που καταναλώνουν.

Ταχύτητα - ο χρόνος του αλγορίθμου, ανάλογα με την ποσότητα των δεδομένων εισόδου.

Καθορίζεται από τη συνάρτηση T(n), όπου n είναι η ποσότητα των δεδομένων εισόδου

Είδη ανάλυσης

Χειρότερη περίπτωση: T(n)είναι ο μέγιστος χρόνος για οποιαδήποτε δεδομένα εισόδου μεγέθους n.

Μεσαία περίπτωση: T(n)είναι ο αναμενόμενος χρόνος για οποιαδήποτε είσοδο μεγέθους n.

Η καλύτερη περίπτωση είναι ο ελάχιστος χρόνος λειτουργίας.

Ασυμπτωτική εκτίμηση

Ο- σημειογραφία: ασυμπτωτικό άνω φράγμα

f (n) = O(g(n))

($c > 0, n 0 > 0 z 0 ≤ f (n) ≤ c g(n), n ≥ n 0)

O(g(n)) = (f (n) : $ c > 0, n 0 > 0 z 0 ≤ f (n) ≤ c g(n), n ≥ n 0 )

Παράδειγμα: 2n2 = O(n3)

Αναδρομικοί αλγόριθμοι, κατασκευή ασυμπτωτικής εκτίμησης. Παράδειγμα

Συγχώνευση ταξινόμησης

sort(А,p,r) //p - η αρχή του πίνακα, r - το τέλος του πίνακα T(n)

αν (σελ< r) //1

q=(p + r)/2; // Υπολογίστε τη μέση του πίνακα 1

sort(A, p, q); //ταξινόμηση της αριστερής πλευράς του T(n/2)

sort(A,q+1,r); //ταξινόμηση της δεξιάς πλευράς του T(n/2)

συγχώνευση(p,q,r); //συγχωνεύστε δύο πίνακες σε έναν n