Θέμα: Επίδοση και Πολυπλοκότητα - Ερώτηση 1η

[gthal]

Έστω το παρακάτω πρόβλημα:
Να γραφεί αλγόριθμος που εμφανίζει όλα τα πολλαπλάσια του 5 που βρίσκονται στο διάστημα [0, 100]
και έχουμε 3 αλγορίθμους που το επιλύουν:

Αλγόριθμος λύση_1   Για κ από 0 μέχρι 100     Αν κ mod 5 = 0 τότε       Εμφάνισε κ     Τέλος_αν   Τέλος_επανάληψης Τέλος λύση_1

Αλγόριθμος λύση_2   Για κ από 0 μέχρι 100 με_βήμα 5     Εμφάνισε κ   Τέλος_επανάληψης Τέλος λύση_2

Αλγόριθμος λύση_3   Για κ από 0 μέχρι 20     Εμφάνισε κ*5   Τέλος_επανάληψης Τέλος λύση_3

Ας υπολογίσουμε τον αριθμό πράξεων για καθέναν από αυτούς

Λύση 1: αρχική τιμή κ: 1 πράξη βρόχος επανάληψης    έλεγχος κ<=100: 1 σύγκριση * 102 φορές = 102 πράξεις    έλεγχος κ mod 5 = 0: (1 πράξη + 1 σύγκριση)* 101 φορές = 202 πράξεις    Εμφάνισε κ: 1 πράξη * 21 φορές = 21 πράξεις    αύξηση του κ: (1 πράξη + 1 εκχώρηση)*101 φορές = 202 πράξεις                   (ή αν είναι 1 πράξη όλο μαζί = 101 πράξεις) Σύνολο: 527 πράξεις και γενικά, υπολογίζω 8+5n+(n div 5)  πράξεις

Λύση 2: αρχική τιμή κ: 1 πράξη βρόχος επανάληψης    έλεγχος κ<=100: 1 σύγκριση * 22 φορές = 22 πράξεις    Εμφάνισε κ: 1 πράξη * 21 φορές = 21 πράξεις    αύξηση του κ: (1 πράξη + 1 εκχώρηση)*21 φορές = 42 πράξεις                   (ή αν είναι 1 πράξη όλο μαζί = 21 πράξεις) Σύνολο: 86 πράξεις και γενικά,  υπολογίζω 6+4(n div 5) πράξεις

Λύση 3: αρχική τιμή κ: 1 πράξη βρόχος επανάληψης    έλεγχος κ<=20: 1 σύγκριση * 22 φορές = 22 πράξεις    Εμφάνισε κ*5: (1 πράξη + 1 εμφάνιση)* 21 φορές = 42 πράξεις    αύξηση του κ: (1 πράξη + 1 εκχώρηση)*21 φορές = 42 πράξεις                   (ή αν είναι 1 πράξη όλο μαζί = 21 πράξεις) Σύνολο: 107 πράξεις και γενικά,  υπολογίζω 7+5*(n div 5) πράξεις

Από αυτά είναι ολοφάνερο ότι ο 2ος κι ο 3ος αλγόριθμος απαιτούν σημαντικά λιγότερες πράξεις απ' ότι ο πρώτος.
Μάλιστα ο δεύτερος κάνει περίπου μόλις το 15% των πράξεων του 1ου για μεγάλα n (άρα και το 15% του χρόνου) ?
και σίγουρα, διαισθητικά, θα διάλεγα τον 2ο για να λύσω το πρόβλημα.

Ωστόσο και οι τρεις έχουν πολυπλοκότητα O(n), σωστά?
Τι σημαίνει αυτό για την πολυπλοκότητα? Δεν μπορεί να αποτελέσει μέτρο για την καταλληλότητα των αλγορίθμων σ' αυτή την περίπτωση?
Ευχαριστώ εκ των προτέρων όποιον ασχοληθεί.

[alkisg]

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

Καταρχάς, όταν μελετάμε συναρτήσεις στα μαθηματικά, τις μελετάμε ανάλογα με τον βαθμό τους... πρωτοβάθμια: ax+b, δευτεροβάθμια: ax²+bx+c κλπ. Ο βαθμός είναι το σημαντικό και όχι τόσο η τιμή του a. Αν το δούμε σαν γραφικές παραστάσεις, τότε οι πρωτοβάθμιες είναι ευθείες και οι δευτεροβάθμιες καμπύλες, εντελώς διαφορετικά πράγματα.

Το ίδιο είναι και στην πολυπλοκότητα. Όταν ένα πρόβλημα έχει είσοδο 1 δις στοιχεία, μας  ενδιαφέρει αν θα χρειαστούμε αριθμό επαναλήψεων της τάξης του n*1 δις στοιχείων (δηλαδή O(n)). Δεν είναι ιδιαίτερα σημαντικό το πόσο θα είναι το n, το σημαντικό είναι ότι η λύση του προβλήματος είναι γραμμική. Αντίθετα, αν θέλαμε n*n επαναλήψεις, τότε αλλάζει ριζικά η τάξη της λύσης, άλλο πράγμα να πεις "χρειάζομαι 5*δις επαναλήψεις" και άλλο "χρειάζομαι 1.000.000.000*δις επαναλήψεις".

Σίγουρα μια λύση που θέλει 0.5*n πράξεις είναι καλύτερη από μία που θέλει 10*n πράξεις αλλά δεν είναι και ιδιαίτερα σημαντική αυτή η διαφορά. Γι' αυτό και όλα αυτά τα λέμε O(n) χωρίς να μπαίνουμε σε λεπτομέρειες. Αν αυξάνεται η τάξη (δύναμη) της λύσης (π.χ. εμφωλευμένη επανάληψη) τότε είναι που η λύση είναι σημαντικά χειρότερη και αξίζει να επισημανθεί.

[bugman]

Εδώ έχει ένα πολύ ωραίο πίνακα με επεξηγήσεις! (Orders of common functions)
https://en.wikipedia.org/wiki/Big_O_notation

[dpa2006]

Καλές σημειώσεις έχει για απόδοση Αλγορίθμων συμβολισμό Ο (Big O notation) ο Δημήτρης Φωτάκης από ECE ntua στο μάθημα Αλγόριθμοι
Παραδείγματα για το πως μπορείς να υπολογίσεις τον χρόνο εκτέλεσης του αλγοριθμου  εδώ σελίδα 14.
Έχει πολλά παραδείγματα ρίξε τα μια ματιά και αν έχεις απορίες ρωτάς.

[apoldem]

gthal, σωστή η ανάλυσή σου. Δεν πρέπει όμως να προσθέτεις διαφορετικό είδος πράξεων για να βγάλεις συνολικό αριθμό σε κάθε αλγόριθμο. Οι πράξεις (ή τα βήματα) του κάθε αλγόριθμου δεν είναι το ίδιο σημαντικά.

Ο κάθε αλγόριθμος συγκρίνεται με τους άλλους με βάση τον ίδιο τύπο πράξης (ή βήματος). Πιο μεγάλο κόστος (με πολύ μεγάλη διαφορά)  έχουν οι αριθμητικές πράξεις, οπότε η σύγκριση ξεκινάει απ' εκεί:
-Ο πρώτος αλγόριθμος θα κάνει 101 διαιρέσεις (ισοδύναμο με πολλαπλασιασμό)
-Ο δεύτερος θα κάνει 21 προσθέσεις
-Ο τρίτος θα κάνει 21 πολλαπλασιασμούς

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

[alkisg]

Ο πολλαπλασιασμός δεν είναι αυτονόητα πιο υπολογιστικά ακριβός από την πρόσθεση.
Π.χ. http://stackoverflow.com/questions/21819682/is-integer-multiplication-really-same-speed-as-addition-on-modern-cpu
Δεν νομίζω ότι έχει νόημα να μπούμε σε τέτοιες λεπτομέρειες στα πλαίσια σχολικού μαθήματος...

[gthal]

Σας ευχαριστώ όλους για τη συμμετοχή σας!

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

Άλκη, το ανάλογο με τις συναρτήσεις βοήθησε αρκετά, ναι...

[stam12]

Καλά, τι ήθελαν και το έβαζαν μέσ' την ύλη αυτό το κεφάλαιο; Είναι μέσ' την ασάφεια! Ό,τι πιο ακατάλληλο για τις τις Πανελλαδικές Εξετάσεις. Καψόνια θέλουν να μας κάνουν μάλλον.

[gpapargi]

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

Γιώργο συμφωνώ με αυτά που έγραψε ο Άλκης.
Γράφω και εγώ κάποια σχετικά πράγματα. Η πολυπλοκότητα είναι το ακριβές πλήθος των βημάτων. Αλλά αυτό που έχει σημασία είναι η συμπεριφορά της συνάρτησης καθώς το πλήθος των βημάτων ανεβαίνει πάρα πολύ. Εκεί μετράει ο μεγιστοβάθμιος όρος και έτσι οδηγούμαστε στην τάξη του αλγορίθμου. Δηλαδή ποιος είναι ο όρος που κυριαρχεί όταν αυξάνεται πολύ το πλήθος. Κάτι ανάλογο βλέπεις και στα όρια ρητών συναρτήσεων (στα μαθηματικά) που παίρνεις το μεγιστοβάθμιο όρο από αριθμητή και παρονομαστή και βλέπεις τη συμπεριφορά. Αυτή είναι η βασική ιδέα. Τα Ο,ο Θ κλπ είναι διάφοροι τεχνικοί τρόποι για να περιγράψεις όλα αυτά. Η ουσία όμως είναι ότι ο μεγιστοβάθμιος όρος είναι αυτός που κυριαρχεί στις πολύ μεγάλες τιμές και εκεί πάνω καθορίζεται η τάξη του αλγορίθμου.