Αλγοριθμος - γραφος

[maxegaleo]

Καλησπερα. Θα ηθελα να ζητησω βοηθεια με το project για τη σχολη μου. Το θεμα ειναι:

 

Να σχεδιαστούν και να υλοποιηθούν αλγόριθμοι που να αναγνωρίζουν αν ένας κατευθυνόμενος γράφος είναι: α) δακτύλιος, β) αστέρας στις περιπτώσεις που η αναπαράσταση του γράφου είναι με:

 

i) λίστες γειτνίασης,

ii) πίνακες γειτνίασης

 

Ποια η πολυπλοκότητα χειρότερης περίπτωσης για τους 4 αλγορίθμους που υλοποιήσατε;

 

Αν μπουρασατε να μου δωσετε λιγη βοηθεια με την υλοποιηση του.

[asbanoglou]

Παμε ρε Τει Λαμιας

[GKNSB]

Ας ξεκινήσουμε από κάτι βασικό. Για τι γλώσσα μιλάμε ?

Βοήθεια σε ποιο κομμάτι της υλοποίησης χρειάζεσαι?

[asbanoglou]

Ο αλγοριθμος πρεπει να ειναι γραμμενος στην C το μονο ζητημα της ασκησης το οποιο δεν μπορω να καταλαβω ειναι το ζητουμενο της πολυπλοκοτητας που ζηταει. "Ποια η πολυπλοκότητα χειρότερης περίπτωσης για τους 4 αλγορίθμους που υλοποιήσατε; "

[GKNSB]

Με την πολυπλοκότητα, μπορούμε να μετρήσουμε την απόδοση ενός αλγορίθμου και να τον συγκρίνουμε με άλλους που εκτελούν την ίδια λειτουργία με άλλο κώδικα. Απλούστερα, πολυπλοκότητα είναι ο αριθμός των στοιχειωδών πράξεων που εκτελεί ο αλγόριθμος σου δηλαδή στην προκειμένη κάθε μία από τις 4 υλοποιήσεις σου.

Δεν μπορώ να σου δώσω να καταλάβεις πολλά πράγματα δυστυχώς εδώ αλλά με μία αναζήτηση στο google σχετικά με πολυπλοκότητα αλγορίθμου θα βρεις πραματάκια.

Για παράδειγμα ένα πακετάκι που μπορείς να διαβάσεις και βρήκα με ένα πολύ πρόχειρο ψάξιμο http://www.cs.ucy.ac.cy/~mavronic/Classes/cs232/Notes/notes1.pdf

Επίσης ρίξε μια ματιά και εδώ, κι αυτό από την ίδια αναζήτηση προέκυψε http://www.adslgr.com/forum/showthread.php?t=464975