آیا می تونیم (log(log(n رو بنویسیم( log^2(n (یا logn*logn) ؟ یا حالا اوردر این حالتا ؟
آیا میشه ؟
اول به این سوالم پاسخ بدید.
==
بعدش هم یه نظری به اینجا بندازید ببینید درست می گم یا نه ؟
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
رابطه بینشون از لحاظ مرتبه رشد به این شکله.
[tex]loglogn<logn<log^{2}n[/tex]
در مورد لینک هم بله آخرش حق با شماست یعنی [tex]nloglogn<nlogn<nlog^{2}n[/tex]
افراد دیگه هم لطفا نظرشونو بذارن همینجا
log^2(n)a یعنی همون log(n)*log(n)a یعنی یه حلقه داریم که log(n) بار اجرا میشه و داخل حلقه هم از مرتبه log(n)a هست.
log(log(n))a یعنی از عبارت log(n)a یکبار دیگه لگاریتم بگیر، یعنی عدد خیلی کوچیکی میشه.
مثال عددیش رو بزنی کاملا فرق رو متوجه میشی:
فرض کنید n=2^1024 که عدد خیلی بزرگی و برای مقایسه الگوریتم ها مناسبه :
حالت اول : log^2(2^1024)=log(2^1024)*log(2^1024)=1024*1024=2^20a
حالت دوم : log(log(2^24)=log(1024)=10a که در مقایسه با ۲۰^۲ عدد خیلی کوچیکیه.
پس کامل مشخصه که log(log(n)<log^2(n)a هستش و میتونیم بنویسیم log(log(n))=o(log^2(n))a یعنی log^2(n)a یه حدبالای نامساوی برای log(log(n))a هستش (o کوچیک) .