Απαιτήσεις: Πρέπει να ορίσετε έναν τύπο συλλογής μόνο για ανάγνωση, ο οποίος δεν θα προσθέτει, θα διαγράφει ή θα τροποποιεί τη συλλογή, αλλά θα υποβάλλει ερωτήματα μόνο στη συλλογή. ΕλπίζουμεΌσο πιο γρήγορο είναι το ερώτημα, τόσο το καλύτερο。
Κοινές συγκρίσεις συνόλων
Κατά την περιγραφή της πολυπλοκότητας του αλγορίθμου, τα o(1), o(n), o(logn), o(logn), o(nlogn) χρησιμοποιούνται συνήθως για να εκφράσουν τη χρονική πολυπλοκότητα του αντίστοιχου αλγορίθμου, που είναι η έκφραση της χωροχρονικής πολυπλοκότητας του αλγορίθμου. Χρησιμοποιείται όχι μόνο για να αναπαραστήσει τη χρονική πολυπλοκότητα, αλλά και για να αναπαραστήσει τη χωρική πολυπλοκότητα.
Το O ακολουθείται από μια συνάρτηση σε παρένθεση που υποδεικνύει τη σχέση μεταξύ του χρόνου/χώρου που καταναλώνεται από έναν αλγόριθμο και της ποσότητας των δεδομένων που αναπτύσσονται. όπου n αντιπροσωπεύει την ποσότητα των δεδομένων εισόδου.
Για παράδειγμα, εάν η χρονική πολυπλοκότητα είναι O(n), σημαίνει ότι ο όγκος των δεδομένων αυξάνεται αρκετές φορές και η κατανάλωση χρόνου αυξάνεται επίσης αρκετές φορές. Για παράδειγμα, κοινοί αλγόριθμοι διέλευσης. Ένα άλλο παράδειγμα είναι η χρονική πολυπλοκότητα O(n^2), που σημαίνει ότι όταν ο όγκος δεδομένων αυξάνεται n φορές, χρειάζεται χρόνος για να αυξηθεί n τετραγωνικές φορές, που είναι μεγαλύτερη χρονική πολυπλοκότητα από τη γραμμική. Για παράδειγμα, η ταξινόμηση με φυσαλίδες είναι ένας τυπικός αλγόριθμος O(n^2), ο οποίος πρέπει να σαρωθεί n × n φορές για να ταξινομηθούν n αριθμοί.
Ένα άλλο παράδειγμα είναι το O(logn), όταν τα δεδομένα αυξάνονται n φορές, χρειάζεται χρόνος για να αυξηθούν οι χρόνοι logn (το αρχείο καταγραφής εδώ βασίζεται στο 2, για παράδειγμα, όταν τα δεδομένα αυξάνονται κατά 256 φορές, ο απαιτούμενος χρόνος αυξάνεται μόνο κατά 8 φορές, που είναι χαμηλότερος από τον γραμμικό. Η δυαδική αναζήτηση είναι ο αλγόριθμος του O (logn), ο οποίος εξαλείφει τις μισές πιθανότητες κάθε φορά που βρίσκεται και η αναζήτηση σε 256 δεδομένα χρειάζεται να βρεθεί μόνο 8 φορές για να βρεθεί ο στόχος.
O(nlogn) είναι το ίδιο, δηλαδή n πολλαπλασιασμένο με logn, όταν τα δεδομένα αυξάνονται κατά 256 φορές, η κατανάλωση χρόνου αυξάνεται κατά 256 * 8 = 2048 φορές. Αυτή η πολυπλοκότητα είναι υψηλότερη από τη γραμμικότητα κάτω από το τετράγωνο. Η συγχώνευση και η ταξινόμηση είναι η χρονική πολυπλοκότητα του O(nlogn).
O(1) είναι η χαμηλότερη χωροχρονική πολυπλοκότητα, δηλαδή ο χρόνος/χώρος που καταναλώνεται είναι ανεξάρτητος από το μέγεθος των δεδομένων εισόδου, ανεξάρτητα από το πόσες φορές αυξάνονται τα δεδομένα εισόδου, ο χρόνος/χώρος που καταναλώνεται παραμένει αμετάβλητος. Ο αλγόριθμος κατακερματισμού είναι μια τυπική χρονική πολυπλοκότητα O(1), η οποία μπορεί να βρει τον στόχο μετά από έναν μόνο υπολογισμό (ανεξάρτητα από τις συγκρούσεις), ανεξάρτητα από το πόσο μεγάλα είναι τα δεδομένα.
Αυτό το άρθρο χρησιμοποιεί το ζεύγος BenchmarkDotNetΛίστα, HashSet, SortedSet, ΛεξικόΕρώτημα για συγκριτική αξιολόγηση, ανατρέξτε στα ακόλουθα:
Ο κωδικός έχει ως εξής:
Αποτέλεσμα δοκιμής: Η εύρεση ενός κλειδιού σε ένα λεξικό ή ένα HashSet είναι πολύ πιο γρήγορη από την αναζήτηση σε μια λίστα και ένα SortedSet. Η χρονική πολυπλοκότητα των αλγορίθμων Dictionary και HashSet είναι O(1) και για να εξοικονομήσουμε μνήμη, η τιμή του λεξικού δεν μας χρησιμεύει, οπότε επέλεξα την αποθήκευση HashSet.
|
Δημοσιεύτηκε στις 7/3/2022 4:47:50 μ.μ.
|
|
|
|
Δημοσιεύτηκε στις 7/3/2022 11:09:48 μ.μ.
|
Σπιτονοικοκύρης|
Δημοσιεύτηκε στις 9/3/2022 9:55:12 π.μ.
|
