Υπολογισμός πολυπλοκότητας βρόχου από γνωστή πολυπλοκότητα κάθε επανάληψης

Question

Το πρόβλημα έχει μέγεθος Ν. Ο αλγόριθμος τρέχει έναν βρόχο με μεταβλητή έλεγχου i από Ν ως 1. Κάθε επανάληψη του βρόχου κοστίζει logi χρόνο.

Άρα ο αλγόριθμος θα χρειαστεί logN+log(N-1)+log(N-2)+...+log1 χρόνο. Αυτή η ποσότητα φαντάζομαι είναι "ίση" με κάποια από τις γνωστές πολυπλοκότητες. Θεωρώ πως βρίσκεται κάπου μεταξύ logN και N*logN. Όμως δεν μπορώ να το προσδιορίσω ακριβώς.

Μήπως θα μπορούσατε να εξηγήσετε αν "ισούται" με κάποια γνωστή πολυπλοκότητα;

Answer 1

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

Το bottom line είναι ότι σε ενδιαφέρει να βρεις μια συνάντηση που είναι ασυμπτωτικα μεγαλύτερη από την πολυπλοκότητα που θέλεις να φτιάξεις.

Στην περίπτωση σου ισχύει $f(n) = \log n + \log (n-1) + ... + \log 1 \leq n\log n = g(n)$, άρα μπορείς να πεις ότι $f(n) = O(g(n))$, το οποίο για τις περισσότερες χρήσεις που θα έχεις είναι ένα good enough όριο, ώστε να μην χρειάζεται να βρεις καλύτερο.