Landau's Oh!

Jeronymo Simonstone · #1

Εάν για δυο ακολουθίες f(n), g(n)

με $g(n)\geq 2$ έχουμε f(n)=O(g(n))

,
τότε

.

Ισχύει το συμπέρασμα εάν g(n)<2

?

#2

Θεωρούμε βέβαια ότι και οι δυο ακολουθίες είναι ακολουθίες θετικών αριθμών για να ορίζονται και οι ακολουθίες των λογαρίθμων.

Από τα δεδομένα, υπάρχει C > 0

ώστε $f(n) \leqslant Cg(n)$ για κάθε $n \in \mathbb{N}$ . Αλλά τότε $\log(f(n)) \leqslant \log(g(n)) + \log{C}$ για κάθε

. Αν $C \leqslant 1$ τότε έχουμε $\log(f(n)) \leqslant \log(g(n))$ για κάθε

και άρα $\log(f(n)) = O\left( \log(g(n))\right)$ . Αν C > 1

, τότε $\log(g(n)) \geqslant \log{2} \geqslant \frac{\log{2}}{\log{C}} \log{C}$ και άρα $\displaystyle{ \log(f(n)) \leqslant \left(1 + \frac{\log{C}}{\log{2}} \right)\log(g(n))}$ για κάθε

άρα πάλι έχουμε το ζητούμενο.

Το συμπέρασμα δεν ισχύει αν g(n) < 2

. Για παράδειγμα αν f(n) = 100

και

τότε $f(n) = O(\(g(n))$ αλλά επειδή $\log(g(n)) \to 0$ δεν ισχύει ότι $\log((f(n)) = O(\log(g(n)))$ .

Jeronymo Simonstone · #3

ευχαριστώ Dem για την απάντηση

υγ. δεν βλέπω λόγο να μην ισχύει η προταση για g >c>1

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

#4

Jeronymo Simonstone έγραψε:ευχαριστώ Dem για την απάντηση

υγ. δεν βλέπω λόγο να μην ισχύει η προταση για g >c>1, με την ίδια απόδειξη.
υγ. άρα το πρόβλημα είναι να έχουμε το 1 ως σημείο συσσώρευσης... νομιζω.
τεσπα. ευχαριστω κ πάλι.

Έτσι ακριβώς.

Landau's Oh!

Landau's Oh!

Re: Landau's Oh!

Re: Landau's Oh!

Re: Landau's Oh!

Μέλη σε σύνδεση