Δημοσιεύτηκε: 15 Οκτ 2011, 17:08
Tasos09 έγραψε:Μία παρατήρηση για το παράδειγμα της τετραγωνικής πολυπλοκότητας.
Η πολυπλοκότητα για την εκχώρηση στοιχείων σε έναν διδιάστατο πίνακα μπορεί μεν να χρησιμοποιεί 2 for για να επιτευχθεί αλλά αυτό δεν το κάνει να έχει τετραγωνική πολυπλοκότητα. Η πολυπλοκότητα είναι σταθερή ως προς το μέγεθος της εισόδου, αφού ως είσοδος θα υπάρχουν ΝχΝ στοιχεία, και όχι Ν.
Μπορείς να αλλάξεις το παράδειγμα με τον αλγόριθμο bubblesort για ταξινόμηση που είναι Ο(n²).
Nαι ο bubble sort ειναι Ο(n²) αλλα δεν τον έβαλα. Ναι ειχα διαβασει πως η πολυπλοκοτητα βγαινει και συναρτήσει της εισόδου. Για να καταλαβω καλυτερα το προβλημα σε αυτο που έχω βάλει ειναι η δήλωση στατικού πίνακα? Στον bubble sort δεν τον κανει να έχει τετραγωνικη πολυπλοκότητα οι 2 for αλλα το if που έχει ? Εξηγησε λιγο παραπανω γιατι έχει επελθει σύγχυση.