forum.math.uoa.gr

Forum του Τμήματος Μαθηματικών
Ημερομηνία 21 Σεπ 2017, 12:43

Όλοι οι χρόνοι είναι UTC + 2 ώρες [ DST ]




Δημιουργία νέου θέματος Απάντηση στο θέμα  [ 3 δημοσιεύσεις ] 
Συγγραφέας Μήνυμα
 Θέμα δημοσίευσης: Άσκηση στο O Landau
ΔημοσίευσηΔημοσιεύτηκε: 07 Φεβ 2012, 16:44 
Χωρίς σύνδεση
Regular Forumer

Εγγραφη: 12 Μαρ 2006, 23:50
Δημοσ.: 442
Τοποθεσια: Άγιος Στέφανος
Δείξτε με χρήση του συμβολισμού O πως αν για δύο συναρτήσεις f(n) και g(n) με g(n) \geq 2 ισχύει f(n) = O(g(n)) τότε θα ισχύει ότι \ell og(f(n)) = O(\ell og(g(n)))

Ο περιορισμός g(n) \geq 2 εγγυάται πως \ell og(g(n)) \geq 1. Ισχύει το παραπάνω αν αφαιρέσουμε τον περιορισμό g(n) \geq 2; Εξηγήστε το συλλογισμό σας!

Στέλιος

_________________
Maths are so beautiful as a statue....


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Άσκηση στο O Landau
ΔημοσίευσηΔημοσιεύτηκε: 08 Φεβ 2012, 11:47 
Χωρίς σύνδεση
Regular Forumer

Εγγραφη: 11 Φεβ 2007, 21:13
Δημοσ.: 628
Μάς ζητάνε δλδ να αποδείξουμε ότι η λογαρίθμιση διατηρεί τα άνω φράγματα :

Γιά όλες τίς
f,g:\mathbb N \to \mathbb R^{+} με g(n)\geq 2, γιά κάθε n\geq n_{0} ισχύει :

f(n)\in O(g(n))\Rightarrow \log f(n)\in O(\log g(n))

Απόδειξη :

\frac{f(n)}{g(n)}\leq K\Rightarrow \frac{\ log f(n)}{\log g(n)}\leq \frac{\log K +\log g(n)}{\log g(n)}

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


Και μιά παρατήρηση : Η πρόταση δέν ισχύει για αυστηρά άνω φράγματα. Παράδειγμα : f(n)=\sqrt{n} και g(n)=n


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Άσκηση στο O Landau
ΔημοσίευσηΔημοσιεύτηκε: 08 Φεβ 2012, 12:09 
Χωρίς σύνδεση
Regular Forumer

Εγγραφη: 12 Μαρ 2006, 23:50
Δημοσ.: 442
Τοποθεσια: Άγιος Στέφανος
Σε ευχαριστώ πολύ Apokalyptikos!!

Στέλιος

_________________
Maths are so beautiful as a statue....


Κορυφή
 Προφίλ  
 
Τελευταίες δημοσιεύσεις:  Ταξινόμηση κατά  
Δημιουργία νέου θέματος Απάντηση στο θέμα  [ 3 δημοσιεύσεις ] 

Όλοι οι χρόνοι είναι UTC + 2 ώρες [ DST ]


Μελη σε συνδεση

Μέλη σε αυτή την Δ. Συζήτηση : Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης


Δεν μπορείτε να δημοσιεύετε νέα θέματα σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να απαντάτε σε θέματα σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να επεξεργάζεστε τις δημοσιεύσεις σας σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να διαγράφετε τις δημοσιεύσεις σας σε αυτή τη Δ. Συζήτηση

Αναζήτηση για:
Μετάβαση σε:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group