Δημοσιεύτηκε: 15 Οκτ 2011, 17:49
Tasos09 έγραψε:Στη bubblesort έχεις Ν στοιχεία και χρησιμοποιείς τα 2 for για να τα ταξινομήσεις. Άρα έχεις Ν στοιχεία επί Ν φορές που προσπελαύνεις το καθένα. Άρα συνολικά Ν² πράξεις.
Στην εισαγωγή στο διδιάστατο πίνακα έχεις Ν*Ν στοιχεία σαν είσοδο και απλά κάνεις Ν*Ν εμφανίσεις πχ. Άρα αν θέσεις Ν*Ν = n ως είσοδο η πολυπλοκότητά σου θα είναι O(n).
Αχα! Καταλαβα τι εννοεις. Για παράδειγμα αν είχα εναν πίνακα 2 Χ 2 τότε θα είχα :
- Κώδικας: Επιλογή όλων
11 12
21 22
4 στοιχεία δεδομένη είσοδος δηλαδη και 4 στοιχεία δεδομένη έξοδος δεν υπάρχει ούτε άυξηση ούτε μείωση αρα σταθερή πολυπλοκότητα
πφφφ ακομη δεν μπορω να καταλαβω 100% παντως τον ακριβη ορισμο της πολυπλοκότητας , ισως βεβαια φταιει οτι δεν υπάρχουν κάποια στανταρ βήματα αλγορίθμου στο γέμισμα ενος δισδιάστατου πίνακα που επιχείρησα να κάνω πιο πάνω ετσι δεν ειναι?
Τωρα σχετικα με τον bubble sort θα τον βάλω αλλα δεν μπορω να καταλάβω το εξής.
ΑΝ εχω πχ την διάταξη 4 3 2 1 και θελω να την ταξινομήσω με χαρτι και μολύβι οι πράξεις που χρειάζονται μου βγήκαν 6!
Kαι κάθε φορα οι συνολικές πράξεις ηταν Ν-1 ... Ν-2 ...κτλπ
ΑΠλα με έχει μπερδέψει το γεγονός οτι έδωσα βάρος στις for για να κατανοήσω την πολυπλοκότητα :/
p.s Βασικα ουτε αυτο που έχω στην 1η περίπτωση ειναι γραμμική πολυπλοκότητα αλλα σταθερή νομιζω .. εφοσον εξαρχης προδικάζω οτι το n=3 αν εβαζα πχ ο χρηστης να επιλέγει ποσα θα είναι τα στοιχεία του πινακα που εχω ορισει εγω εξαρχης στο προγραμμα τοτε δεν θα ηταν γραμμικη ας πουμε???