تالار گفتمان مانشت

Log t(n)∈O(log⁡〖g(n))〗

توابع T ,G رو تعریف نکردید.

خیر . مطمئن هستید درست تایپ کردید؟ آخه این رابطه به بررسی دو تابع نامعلوم می پردازد .

فکر کنم منظورشون این سوال بوده.[attachment=3324]


خیر اگه [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]

جناب afagh1389 ممنون از پاسختون فکر می کنم همین باشه، استادمون t(n) و g(n) رو مشخص نکرد فقط گفت 24 تا رابطه هستند در کتاب CLRS که یکیش این سوال،
به هر حال فکر می کنم همین باشه ممنون از پاسختون

(26 اسفند 1390 09:52 ب.ظ)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] باشه دیگه رابطه بالا برقرار نیست.