Δημοσιεύτηκε: 15 Οκτ 2011, 16:44
Μία παρατήρηση για το παράδειγμα της τετραγωνικής πολυπλοκότητας.
Η πολυπλοκότητα για την εκχώρηση στοιχείων σε έναν διδιάστατο πίνακα μπορεί μεν να χρησιμοποιεί 2 for για να επιτευχθεί αλλά αυτό δεν το κάνει να έχει τετραγωνική πολυπλοκότητα. Η πολυπλοκότητα είναι σταθερή ως προς το μέγεθος της εισόδου, αφού ως είσοδος θα υπάρχουν ΝχΝ στοιχεία, και όχι Ν.
Μπορείς να αλλάξεις το παράδειγμα με τον αλγόριθμο bubblesort για ταξινόμηση που είναι Ο(n²).
Η πολυπλοκότητα για την εκχώρηση στοιχείων σε έναν διδιάστατο πίνακα μπορεί μεν να χρησιμοποιεί 2 for για να επιτευχθεί αλλά αυτό δεν το κάνει να έχει τετραγωνική πολυπλοκότητα. Η πολυπλοκότητα είναι σταθερή ως προς το μέγεθος της εισόδου, αφού ως είσοδος θα υπάρχουν ΝχΝ στοιχεία, και όχι Ν.
Μπορείς να αλλάξεις το παράδειγμα με τον αλγόριθμο bubblesort για ταξινόμηση που είναι Ο(n²).