اولی اگر f>1 باشه درسته ولی برای f<1 غلطه .

برای سومی
[tex]f = 2n , g=n \rightarrow 2^{2n} = O(2^{n}) \rightarrow 4^n \neq O (2^n)[/tex]

واسه چهارمی هم
[tex]f = 4n \rightarrow 4^{n} = \theta (4^{n/2}) \rightarrow 4^n \neq \theta (2^n)[/tex]

سلام. گزینه ۱ که تابلو غلطه. مثلا F رو برابرn بدید.
گزینه ۲ درسته. چون تابع به علاوه کوچکترین حد بالاش عضو تتا است. مثلا n+ cn که c عدد ثابته.
گزینه ۳ اگه طرف دوم رو میگفت ۲ به توان f برابر ۲ به توان o)g( درست میشد. اما این مورد لزوما درست نیست.
گزینه ۴ هم اگه به جای تتا میگفت امگا درست میشد.
تنها گزینه ۲ درسته

Sent from my SM-T210R using Tapatalk

اقا هومن ۲ درست نیست
برای اینکه تابع f هیچ وقت با o کوچک برابر نیست چون o کوچیک مقدارش از f بیشتر و باهاش برابر نیست.برای همین غلطه.
ولی نمیدونم چرا کتابای مختلف هر کدوم یه حرفی میزننن به نظرم هیچ کدوم درست نیست. البته اگر گزینه ۲ o بزرگ باشه درسته.
آقا مسعود برای ۴ مثال درست زدید و درست حل نکردید فک کنم حواستون نبوده.
ممنون از شما.

موفق باشید.

(۰۲ بهمن ۱۳۹۲ ۱۰:۵۷ ب.ظ)tarane1992 نوشته شده توسط:  اقا هومن ۲ درست نیست
برای اینکه تابع f هیچ وقت با o کوچک برابر نیست چون o کوچیک مقدارش از f بیشتر و باهاش برابر نیست.برای همین غلطه.
ولی نمیدونم چرا کتابای مختلف هر کدوم یه حرفی میزننن به نظرم هیچ کدوم درست نیست. البته اگر گزینه ۲ o بزرگ باشه درسته.
آقا مسعود برای ۴ مثال درست زدید و درست حل نکردید فک کنم حواستون نبوده.
ممنون از شما.

موفق باشید.

برای گزینه ۲ حد بگیرید. مثلا
o(f(n)) = f(n) + c
lim (f(n) + f(n) + c)/(f(n) = 2
که عددی ثابته و اثباتش می کنه.

نمیدونم چرا همه o کوچیو یه طور تعریف میکنه آره میدونم o کوچیک هیچ وقت حالت مساوی نیست یعنی با تابع برابر نیست ولی باید توابع بزرگتر از اونو در نظر بگیریم.

بعدش یه سوالی چطوری تتاش شد دوباره خود تابع؟اصلا تتا مگه اشتراک دو جمله نیست پس چطوری بدست اوردی؟

تازه هیچ حالتی o کوچیک با خود تابع یکی نمیشه شما هم همینو میگید ولی تو جواب تتاش من نمیدونم چطوری خود تابع شده؟کمک کنید ممنون میشم.

(۰۳ بهمن ۱۳۹۲ ۱۱:۴۶ ق.ظ)tarane1992 نوشته شده توسط:  نمیدونم چرا همه o کوچیو یه طور تعریف میکنه آره میدونم o کوچیک هیچ وقت حالت مساوی نیست یعنی با تابع برابر نیست ولی باید توابع بزرگتر از اونو در نظر بگیریم.

بعدش یه سوالی چطوری تتاش شد دوباره خود تابع؟اصلا تتا مگه اشتراک دو جمله نیست پس چطوری بدست اوردی؟

تازه هیچ حالتی o کوچیک با خود تابع یکی نمیشه شما هم همینو میگید ولی تو جواب تتاش من نمیدونم چطوری خود تابع شده؟کمک کنید ممنون میشم.

منم همین اعتقاد را داشتم. o کوچیک یه مقدار ، میتونه هر چیزی کوچیکتر از اون باشه . به مثالهایی که زدم توجه کن.
مثلا میگن o کوچیک f= n چی میشه جواب : [tex]o(n^2) , o(n^3) , o(2^n)[/tex]


شما برعکسش تو ذهنته. وقتی یه تابع دادند و گفتند o کوچیکش چی میشه اونوقت میتونی هر تابعی بزرگتر از اون را حساب کنی
مثلا میگن [tex]o(n^3)[/tex] واسه چه تابع هایی میباشد : جواب : [tex]f = n^2 , logn, n , C , nlogn[/tex]

من خودم اشتباه شما رو داشتم ، ولی با مثالهایی که به این شکل تو کامنت قبلی زدم اگر روش کمی فکر کنید حتما متوجه میشید اشتباهتون کجاست

تتا اشتراک دو جمله نیست. تتا مساوی با بزرگترین مقدار جمله میشه.

مثال ۴ منظورم n به توان ۴ بوده
گزینه دو درسته
شاید شما هم اشتباه منو انجام دادید.
فرض کنید f=n^4

[tex]n^2 = o(f(n))[/tex]
[tex]n = o(f(n))[/tex]
[tex]n^3 = o(f(n))[/tex]
[tex]n^4 \not\equiv o(f(n))[/tex]
[tex]n^5 \not\equiv o(f(n))[/tex]

خب طبق تعریف رابطه برای مثال های صحیح بالا به این شکل میشه
[tex]f(n) o(f(n)) = n^4 n^2 = \Theta (n^4) = \Theta (f(n))[/tex]
[tex]f(n) o(f(n)) = n^4 n = \Theta (n^4) = \Theta (f(n))[/tex]
[tex]f(n) o(f(n)) = n^4 n^3 = \Theta (n^4) = \Theta (f(n))[/tex]