Άσκηση 9, σελ. 120, οδηγίες μελέτη μαθητή

Ξεκίνησε από gergerman, 20 Φεβ 2020, 05:36:59 ΜΜ

« προηγούμενο - επόμενο »

akalest0s

Παράθεση από: ολγα στις 26 Φεβ 2020, 06:00:08 ΜΜ
Αν επιτρέπεται δυο παρατηρήσεις:

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