۰
subtitle
ارسال: #۱
آیا این رابطه برقرار است؟
Log t(n)∈O(log〖g(n))〗
۰
ارسال: #۲
RE: آیا این رابطه برقرار است؟
فکر کنم منظورشون این سوال بوده.
خیر اگه [tex]f(n)<1[/tex] یا [tex]log(f(n))<1[/tex] رابطه ای که گفتید برقرار نیست.
اما اگه [tex]f(n)>=1[/tex] و [tex](log g(n))>=1[/tex] اونوقت مساوی میشه. (طبق جواب یکی از تمرینهای clrs)
یه جواب واسه سوالی که ضمیمه کردم : [tex]f(n)=1/2^{n^2}[/tex] و [tex]g(n)=1/2^{n}[/tex]
البته با در نظر گرفتن قدرمطلق در تعریف O یعنی :
[tex]\left | f(n)) \right |<=c\left | g(n) \right | \rightarrow f(n)=O(g(n))[/tex]
خیر اگه [tex]f(n)<1[/tex] یا [tex]log(f(n))<1[/tex] رابطه ای که گفتید برقرار نیست.
اما اگه [tex]f(n)>=1[/tex] و [tex](log g(n))>=1[/tex] اونوقت مساوی میشه. (طبق جواب یکی از تمرینهای clrs)
یه جواب واسه سوالی که ضمیمه کردم : [tex]f(n)=1/2^{n^2}[/tex] و [tex]g(n)=1/2^{n}[/tex]
البته با در نظر گرفتن قدرمطلق در تعریف O یعنی :
[tex]\left | f(n)) \right |<=c\left | g(n) \right | \rightarrow f(n)=O(g(n))[/tex]
۰
۰
ارسال: #۴
RE: آیا این رابطه برقرار است؟
خیر . مطمئن هستید درست تایپ کردید؟ آخه این رابطه به بررسی دو تابع نامعلوم می پردازد .
۰
ارسال: #۵
آیا این رابطه برقرار است؟
جناب afagh1389 ممنون از پاسختون فکر می کنم همین باشه، استادمون t(n) و g(n) رو مشخص نکرد فقط گفت ۲۴ تا رابطه هستند در کتاب CLRS که یکیش این سوال،
به هر حال فکر می کنم همین باشه ممنون از پاسختون
به هر حال فکر می کنم همین باشه ممنون از پاسختون
ارسال: #۶
RE: آیا این رابطه برقرار است؟
(۲۶ اسفند ۱۳۹۰ ۰۹:۵۲ ب.ظ)fa_karoon نوشته شده توسط: جناب afagh1389 ممنون از پاسختون فکر می کنم همین باشه، استادمون t(n) و g(n) رو مشخص نکرد فقط گفت ۲۴ تا رابطه هستند در کتاب CLRS که یکیش این سوال،
به هر حال فکر می کنم همین باشه ممنون از پاسختون
۲۴ تا رو نمیدونم ولی یه تعدادی توی کتاب هست میتونید خودتون به تمرینهای کتاب clrs مراجعه کنید.
مثلا یه رابطه دیگه که توی کتاب هست [tex]f(n)=O(g(n))\overset{?}{\rightarrow}2^{f(n)}=2^{g(n)}[/tex]
که اگه [tex]f(n)=2n , g(n)=n[/tex] باشه دیگه رابطه بالا برقرار نیست.
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close