Μια συνάρτηση που μεγαλώνει ταχύτερα από κάθε πολυώνυμο αλλά πιο αργά από κάθε εκθετική

Η απάντηση είναι: ναι, υπάρχει! Ακολουθεί ένα χαρακτηριστικό παράδειγμα τέτοιας συνάρτησης που αναπτύσσεται ταχύτερα από κάθε πολυώνυμο, αλλά πιο αργά από κάθε εκθετική:

$$f(n)=n^{\log n}$$

📈 Μια τέτοια συνάρτηση εμφανίζεται συχνά στην ανάλυση αλγορίθμων και στη θεωρία πολυπλοκότητας — είναι ενδεικτική της λεγόμενης υπερπολυωνυμικής αλλά υποεκθετικής συμπεριφοράς.

Θα μπορούσε να είναι το "μέσο έδαφος" μεταξύ του $n^k$ και του $2^n$; 🤔

📘

Έρχεται το πολλαπλό βιβλίο ΝΕΟ — βρες όλες τις επιλογές εδώ

PDF & Ψηφιακά Μαθησιακά Αντικείμενα — χωρίς εγγραφή • Portify

📚 437 βιβλία🎬 22.000+ Ψηφιακά Μαθησιακά Αντικείμενα

Δες τα βιβλία →