PDE - Η κοινότητα των εκπαιδευτικών

Συγνώμη παιδιά που θα σας "την σπάσω" για ακόμη μια φορά αλλά πάλι κάνετε λάθος. Καλά για τα παραδείγματα του βιβλίου που αναφέρονται δε θα μπω στη διαδικασία να τα περιγράψω γιατί όλοι καταλαβαίνουν ότι είναι άσχετα με τη συγκεκριμένη ερώτηση. Ας δώσω κάποια σχόλια για τη συγκεκριμένη ερώτηση.
Όταν δίνει το σύμβολο του αθροίσματος Σ και ζητάει να πούμε αν είναι Ο(n) ή Ο(n^2) φυσικά και δεν ζητάει συγκεκριμένο αλγόριθμο υλοποίησης απλά μας λέει να βασιστούμε στον ορισμό του αθροίσματος τον οποίο υποθέτει ότι όλοι μας τον ξέρουμε. Γιατί ο ορισμός του αθροίσματος αποτελεί από μόνος του αλγόριθμο υπολογισμού του αθροίσματος.
Το δ είναι ΛΑΘΟΣ γιατί το n(n-1)/2 στο οποίο βασίζονται όσοι επιλέγουν το Δ ΔΕΝ μας δίνει πολυπλοκότητα, μας δίνει το αποτέλεσμα (με τι ισούται δηλαδή το αριστερό μέρος της ισότητας). Δηλαδή αν π.χ. μας δίναν ότι το n=10 τότε ο παραπάνω τύπος θα μας έδινε: Σk για k=1 μέχρι 10 =45, OXI ME O(45). Αν δεν μπορείτε να το καταλάβετε αυτό με γεια σας με χαρά σας.

Είσαι πολύ λάθος και επιμένεις χωρίς λόγο. Μπορείς να μας δώσεις έναν αλγόριθμο σε οποιαδήποτε γλώσσα που να υπολογίζει το άθροισμα n όρων αριθμητικής προόδου, το οποίο είναι και ζητούμενο στην περιβόητη ερώτηση 17, με πολυπλοκότητα Ο(n); Εγώ προκαταβολικά θα σου πω ότι δεν υπάρχει για τον πολύ απλό λόγο ότι κάτι τέτοιο θα ίσχυε μόνο αν επρόκειτο για άθροισμα n ίδιων αριθμών (π.χ. c+c+...+c=c*n=O(n)). Εδώ όμως έχουμε διαφορετικούς αριθμούς και για να υπολογίσουμε το άθροισμά τους πρέπει να εφαρμόσουμε διπλή επανάληψη στον αλγόριθμο. Παραθέτω κι ένα παράδειγμα σε C που υπολογίζει το άθροισμα αυτό:

for (k=1; k <=n; k++) {
   for (j=1; j <= k; j++)
   sum=sum+j;
}

Η πολυπλοκότητά του είναι: n επαναλήψεις από το πρώτο for loop και n+1 προσθέσεις σε κάθε επανάληψη (n για τον υπολογισμό του όρου j που θα προστεθεί στο μερικό άθροισμα sum και 1 για τον υπολογισμό του νέου μερικού αθροίσματος. Οπότε συνολικά n*(n+1) πράξεις και άρα O(n²). Περιμένω τη δική σου υλοποίηση με πολυπλοκότητα O(n).