Pokazują, że $(\log n)^{\log n}\in\Omega (n)$
Nov 20 2020
Pokazują, że$(\log n)^{\log n}\in\Omega (n)$
Przechodząc do wspólnej własności logarytmicznej, otrzymujemy$$(\log n)^{\log n}=(n^{\log\log n})$$
Jak mam to wywnioskować?$$(n^{\log\log n})\in\Omega(n)$$
Jeśli tak powiem$n=b^{b}$gdzie$b$czy podstawa logarytmu może być prawdziwa, ale czy nie przekreśla celu bycia liniowym?
Tutaj,$\Omega,\Theta,\mathcal{O}$są dobrze znane asymptotyki, tj. dolna granica, górna granica i duże O .
Zostało to znalezione w MIT 6.006 wiosna 2020 , pytanie numer 6, chociaż przyjęto podstawę$2$logarytm.
Odpowiedzi
2 Adam Nov 20 2020 at 01:04
Kiedy$n$jest wystarczająco duży,$\log \log n \geq 1$. W związku z tym$n^{\log \log n} \geq n^1 = n$dla$n$wystarczająco duży.