Ευκλείδειος Αλγόριθμος και η πολυπλοκότητα του

Θιελα, δεν αναφέρεται σε ζητήματα πολυπλοκότητας το βιβλίο που παραθέτεις


Ούτε και εγώ βασικά είμαι εξπέρ στο ζήτημα, μα σκέφτομαι τα εξής.

- Πραγματικοί. Τα υπόλοιπα θα είναι πραγματικοί αριθμοί επίσης, οπότε ο αλγόριθμος - εξόν από αριθμήσιμο σύνολο- δεν θα τερματίζει σε πεπερασμένο αριθμό βημάτων. Οπότε ο αλγόριθμος είναι έναν βαθμό παραπάνω πολύπλοκος απ' ότι στην περίπτωση των ακεραίων.

- Μιγαδικοί. Δεν πρόκειται παρά για ζεύγη πραγματικών αριθμών, οπότε ο αλγόριθμος της προηγούμενης περίπτωσης εφαρμόζεται παράλληλα σε κάθε συνιστώσα. Συνεπώς, δεν αυξάνεται η πολυπλοκότητα σε αυτή την περίπτωση.

- Πολυώνυμα. Εδώ πάλι το υπόλοιπο θα είναι πολυώνυμο, οπότε θα έχει βαθμό έναν φυσικό αριθμό (ή μηδέν). Οπότε
ο αλγόριθμος σε κάθε βήμα θα υπολογίζει ένα πολυώνυμο βαθμού μικρότερου (ή ίσου, λολ) από τον διαιρετέο. Δηλαδή,
αναγκαστικά θα τερματίζεται σε πεπερασμένο αριθμό βημάτων, και η πολυπλοκότητά του αλγορίθμου δεν διαφέρει από
την πολυπλοκότητα του αλγορίθμου για ακεραίους.


Υγ. τι τα θες αυτά ρε μαν;