ممنون بابت جواب.
اثبات رو از کجا پیدا کردی؟
اون علامت تعجبی که جلوی "برسونی" نوشتی، فکر کنم برای خودت هم سواله که چرا؟ (چرا رادیکال ۲lgn )؟

(۰۳ آذر ۱۳۹۱ ۰۲:۵۲ ق.ظ)azad_ahmadi نوشته شده توسط:  ممنون بابت جواب.
اثبات رو از کجا پیدا کردی؟
اون علامت تعجبی که جلوی "برسونی" نوشتی، فکر کنم برای خودت هم سواله که چرا؟ (چرا رادیکال ۲lgn )؟

سلام مجدد
نه منظور خاصی نداشتم ، عادت دارم که علامت تعجب میزارم.
یکم فکر کردم به جواب رسیدم از جایی نیاوردم.

---

این نکته رو برای یادگاری میگم :

گزاره : اگر : [tex]f(n)\in O(g(n))[/tex] آنگاه : [tex]2^{f(n)}\notin O(2^{g(n)} )[/tex] غلط است چه اوی کوچیک باشه و چه اوی بزرگ.

اثبات اوی بزرگ ساده هست. ([tex]f(n)=2n ,g(n)=n[/tex]

اما اثبات اوی کوچیک : اگر فرض کنیم : [tex]f(n)=\frac{1}{n^2} ,g(n)=\frac{1}{n}[/tex] در این صورت میتوان گفت که :
[tex]f(n)\in o(g(n))[/tex] (اثبات از طریق حد : [tex]\lim_{n\rightarrow \infty }\frac{f(n)}{g(n)}=\lim_{n\rightarrow \infty } \frac{\frac{1}{n^2}}{\frac{1}{n}}=\lim_{n\rightarrow \infty } \frac{n}{n^2}=\lim_{n\rightarrow \infty } \frac{1}{n}=0\Rightarrow f(n)\in o(g(n))[/tex]
حال اگر داشته باشیم : [tex]2^{f(n)}\in o(2^{g(n)})=2^\frac{1}{n^2} \notin o(2^\frac{1}{n})[/tex]
زیرا : [tex]2^{f(n)}\in o(2^{g(n)})=2^\frac{1}{n^2} \in \theta (2^\frac{1}{n})[/tex]
(از حد استفاده کنید.)

کتاب پوران صفحه ۱۱، اون دو عبارتی که من نوشتم رو مساوی دونسته، و هردوی اونا رو کوچیکتر از n نوشته.
n >2^R2lgn = n^R2/lgn ، پس به عبارتی چون شما n^2 رو بدست اوردین، پاسخ شما اشتباهه.
اون اثبات با توجه به خواص لگاریتم حل می شه، اما تو یه قسمتیش نمی دونم باید چکار کنم.

(۰۳ آذر ۱۳۹۱ ۰۴:۰۶ ب.ظ)azad_ahmadi نوشته شده توسط:  کتاب پوران صفحه ۱۱، اون دو عبارتی که من نوشتم رو مساوی دونسته، و هردوی اونا رو کوچیکتر از n نوشته.
n >2^R2lgn = n^R2/lgn ، پس به عبارتی چون شما n^2 رو بدست اوردین، پاسخ شما اشتباهه.
اون اثبات با توجه به خواص لگاریتم حل می شه، اما تو یه قسمتیش نمی دونم باید چکار کنم.

سلام مجدد !
جسارته ولی چه ربطی داره ؟ مثلآ شما میخواهی ثابت کنی که : [tex]\sqrt{n}=n^{\frac{1}{2}}[/tex]
بعد دو طرف رو به توان دو برسونی : [tex](\sqrt{n})^2=(n^{\frac{1}{2}})^2[/tex]
و در نهایت برسی به این جمله که : [tex]n=n[/tex] که بدیهی است. (و اثبات کامل است.)
بعد از همه این ماجرا ها یکی بیاد و بگه غلطه ! و دلیلشم این باشه که [tex]\sqrt{n}\neq n[/tex] !!!
شما جای من ، آیا دیوانه نمیشدی ؟ (به حق چیزای ندیده ونشنیده ! )