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

Ξεκίνησε από gthal, 12 Νοε 2015, 10:50:33 ΜΜ

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

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

#3
Καλές σημειώσεις έχει για απόδοση Αλγορίθμων συμβολισμό Ο (Big O notation) ο Δημήτρης Φωτάκης από ECE ntua στο μάθημα Αλγόριθμοι
Παραδείγματα για το πως μπορείς να υπολογίσεις τον χρόνο εκτέλεσης του αλγοριθμου  εδώ σελίδα 14.
Έχει πολλά παραδείγματα ρίξε τα μια ματιά και αν έχεις απορίες ρωτάς.
Computer science (abbreviated CS or CompSci) is the scientific and practical approach to computation and its applications. It is the systematic study of the feasibility, structure, expression, and mechanization of the methodical processes (or algorithms) that underlie the acquisition, representation, processing, storage, communication of, and access to information, whether such information is encoded in bits and bytes in a computer memory or transcribed engines and protein structures in a human cell.source:http://en.wikipedia.org/wiki/Computer_science

apoldem

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

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

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

alkisg

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

gthal

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

Παράθεση από: alkisg στις 13 Νοε 2015, 01:29:52 ΜΜ
Γιώργο δεν έχω διαβάσει το σχετικό κεφάλαιο του βιβλίου οπότε μόνο κάποιες γενικούρες θα πω, αν τυχόν βοηθήσουν...
Άλκη, το ανάλογο με τις συναρτήσεις βοήθησε αρκετά, ναι...
Φιλικά,
Γιώργος Θαλασσινός

stam12

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

gpapargi

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

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