Οπτικός υπολογισμός πλήθους επαναλήψεων

Ξεκίνησε από gpapargi, 14 Δεκ 2015, 01:41:27 ΜΜ

« προηγούμενο - επόμενο »

gpapargi

Με αφορμή την είσοδο του κεφαλαίου της πολυπλοκότητας στην ύλη θα ήθελα να περιγράψω έναν οπτικό τρόπο (πέρα από τον αλγεβρικό) που σκέφτηκα προκειμένου να υπολογίζουμε το πλήθος των επαναλήψεων σε διπλούς βρόχους Για.

Μπορούμε να φανταστούμε  μόνο τους βρόχους (αγνοώντας τις εσωτερικές εντολές) να κάνουν προσπέλαση στα κελιά ενός πίνακα 2 διαστάσεων με το δείκτη του εξωτερικού βρόχου να συμβολίζει πχ γραμμές και το δείκτη του εσωτερικού βρόχου να συμβολίζει στήλες.  Βλέποντας από ποια κελιά περνάει, μπορούμε απλώς να μετρήσουμε το πλήθος αυτό των κελιών απευθείας από το σχήμα και να δούμε πόσες φορές επαναλήψεις έχουμε.
Για παράδειγμα στην τριγωνική σάρωση έχω τον κώδικα

Για ι από 2 μέχρι ν
  Για j από 1 μέχρι ι-1
     Γράψε α[ι,j]
  Τέλος_επανάληψης
Τέλος_επανάληψης

Περνάω από τα κελιά που είναι κάτω από την κύρια διαγώνιο. Για να μετρήσω σκέφτομαι ως εξής:
Όλα τα κελιά του πίνακα είναι ν^2. Αφαιρώ τα ν που είναι τα στοιχεία της διαγωνίου και μένουν τα ν^2-ν. Από αυτά κρατάω τα μισά που είναι κάτω από τη διαγώνιο και έχω (v^2-ν)/2.
Με αντίστοιχο τρόπο έβγαλα και το πλήθος των επαναλήψεων στη φυσαλίδα. Εκμεταλλεύεσαι βασικά τον εύκολο τρόπο που μετρώνται τα κελιά ενός πίνακα με απλό πολλαπλασιασμό. Δεν ξέρω αν είναι πιο εύκολο από την άλγεβρα που χρησιμοποιεί αριθμητικές προόδους.
Με διάφορα κόλπα μπορώ να το χρησιμοποιήσω και για τριπλούς βρόχους Για κάνοντας αναγωγή σε διπλό. Γενικά όμως δεν ξέρω τι είναι προτιμότερο μεταξύ αλγεβρικού και γεωμετρικού τρόπου.