Αποστολέας Θέμα: Άσκηση 9, σελ. 120, οδηγίες μελέτη μαθητή  (Αναγνώστηκε 2068 φορές)

akalest0s

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 247
Απ: Άσκηση 9, σελ. 120, οδηγίες μελέτη μαθητή
« Απάντηση #15 στις: 27 Φεβ 2020, 02:00:01 μμ »
Αν επιτρέπεται δυο παρατηρήσεις:

1. μια βελτίωση για τη ΔΙΑΔΙΚΑΣΙΑ εισαγωγή(ΤΚ, ν)
 
Αν θέλουμε ο πίνακας να είναι ταξινομημένος (δεν απαιτείται από την εκφώνηση του βιβλίου, αλλά έστω ότι έτσι θέλουμε) αυτό που θα έπρεπε να κάνει η "εισαγωγή" θα ήταν να εισάγει το νέο συνδρομητή στη σωστή γραμμή του ταξινομημένου πίνακα μεταφέροντας τους συνδρομητές που πρέπει (αυτούς με όνομα μεγαλύτερο του ονόματος του συνδρομητή που θέλουμε να εισάγουμε) μία γραμμή προς τα κάτω (με σκεπτικό παρόμοιο με αυτό της ταξινόμησης ευθείας εισαγωγής) Αυτό έχει πολυπλοκότητα Ο(ν) και λύνεται με ένα ΟΣΟ.
Διαφορετικά έχουμε Ο(ν2)

2.Στη ΔΙΑΔΙΚΑΣΙΑ αναζήτηση(ΤΚ, ν, θ)
Δε μπορεί να γίνει δυαδική αναζήτηση στα τηλέφωνα γιατί δεν είναι ταξινομημένα.
1. Σύμφωνοι, αν και η πολυπλοκότητα είναι εκτός.
2. Προφανώς ήταν δική μου απροσεξία. Κάνεις μια σειριακή και οκ.
"Abstraction is not the first stage, but the last stage, in a mathematical development." MK
"I don't want to write about a high level thing, unless I fully understand about a low level thing" DK