خب ببین یه راست بریم تا وقتی که مجموع رو حساب کنیم.مجموع به صورت یه کسره درسته؟وقتی مقدار هر سطح رو حساب کنیم صورت کسر همیشه [tex]n[/tex] میشه که تو این مشکل نیست خب ؟
حالا میمونه مخرج:توی سطح اول مخرج همه ی کسرها اینه:[tex]\log^{\frac{n}{2}}_2[/tex] حالا مقدار اینو چجوری محاسبه میکنیم؟
[tex]\log^{\frac{n}{2}}_2[/tex]: kjk[tex]\log^{\frac{n}{2}}_2=\log^n_2-\log^2_2=\log^n_2-1[/tex]

حالا توی سطح دوم مخرج همه کسر ها اینه:[tex]\log^{\frac{n}{4}}_2[/tex] حالا مقدار اینو چجوری محاسبه میکنیم؟
[tex]\log^{\frac{n}{4}}_2=\log^n_2-\log^4_2=\log^n_2-2[/tex]

و برای بقیه سطح ها هم ادامه داره و نهایتا مجموع:
[tex]n(\frac{1}{\lg n} \frac{1}{\lg n-1} \frac{1}{\lg n-2} ... 1)=\theta(n.\lg\lg n)[/tex]

(۲۹ مرداد ۱۳۹۳ ۰۸:۱۹ ب.ظ)miladcr7 نوشته شده توسط:  خب ببین یه راست بریم تا وقتی که مجموع رو حساب کنیم.مجموع به صورت یه کسره درسته؟وقتی مقدار هر سطح رو حساب کنیم صورت کسر همیشه [tex]n[/tex] میشه که تو این مشکل نیست خب ؟
حالا میمونه مخرج:توی سطح اول مخرج همه ی کسرها اینه:[tex]\log^{\frac{n}{2}}_2[/tex] حالا مقدار اینو چجوری محاسبه میکنیم؟
[tex]\log^{\frac{n}{2}}_2[/tex]: kjk[tex]\log^{\frac{n}{2}}_2=\log^n_2-\log^2_2=\log^n_2-1[/tex]

حالا توی سطح دوم مخرج همه کسر ها اینه:[tex]\log^{\frac{n}{4}}_2[/tex] حالا مقدار اینو چجوری محاسبه میکنیم؟
[tex]\log^{\frac{n}{4}}_2=\log^n_2-\log^4_2=\log^n_2-2[/tex]

و برای بقیه سطح ها هم ادامه داره و نهایتا مجموع:
[tex]n(\frac{1}{\lg n} \frac{1}{\lg n-1} \frac{1}{\lg n-2} ... 1)=\theta(n.\lg\lg n)[/tex]

جواب این طوری هست:

[tex]\frac{n}{logn}[/tex] <--- سطر اول درخت

[tex]\frac{\frac{n}{5}}{\log(\frac{n}{5})}[/tex] [tex]\frac{\frac{n}{5}}{\log(\frac{n}{5})}[/tex] <---سطر دوم درخت

[tex]\frac{\frac{n}{5^2}}{\log(\frac{n}{5^2})}[/tex] سطر دوم درخت که ۴ تا از اینا هست

حالا میرسیم به نوشتم فرمولهای هر سطر :

نکتش اینه که [tex]\frac{\frac{n}{5}}{\log(\frac{n}{5})}=\frac{n}{(\log n - \log5)}=\frac{n}{\log n-1}[/tex]

توجه کنید که لگاریتم در مبنای ۵ هست به خاطر همینه که لگاریتم ۵ برابر یک میشه

همونطور که میبینید دقیقا فرمولش با اون مثالی که توی کتاب حلش کرده برابره و جوابشون یکی میشه

(۲۹ مرداد ۱۳۹۳ ۰۹:۵۱ ب.ظ)shayesteb نوشته شده توسط:  

(29 مرداد ۱۳۹۳ ۰۸:۱۹ ب.ظ)miladcr7 نوشته شده توسط:  خب ببین یه راست بریم تا وقتی که مجموع رو حساب کنیم.مجموع به صورت یه کسره درسته؟وقتی مقدار هر سطح رو حساب کنیم صورت کسر همیشه [tex]n[/tex] میشه که تو این مشکل نیست خب ؟
حالا میمونه مخرج:توی سطح اول مخرج همه ی کسرها اینه:[tex]\log^{\frac{n}{2}}_2[/tex] حالا مقدار اینو چجوری محاسبه میکنیم؟
[tex]\log^{\frac{n}{2}}_2[/tex]: kjk[tex]\log^{\frac{n}{2}}_2=\log^n_2-\log^2_2=\log^n_2-1[/tex]

حالا توی سطح دوم مخرج همه کسر ها اینه:[tex]\log^{\frac{n}{4}}_2[/tex] حالا مقدار اینو چجوری محاسبه میکنیم؟
[tex]\log^{\frac{n}{4}}_2=\log^n_2-\log^4_2=\log^n_2-2[/tex]

و برای بقیه سطح ها هم ادامه داره و نهایتا مجموع:
[tex]n(\frac{1}{\lg n} \frac{1}{\lg n-1} \frac{1}{\lg n-2} ... 1)=\theta(n.\lg\lg n)[/tex]

جواب این طوری هست:

[tex]\frac{n}{logn}[/tex] <--- سطر اول درخت

[tex]\frac{\frac{n}{5}}{\log(\frac{n}{5})}[/tex] [tex]\frac{\frac{n}{5}}{\log(\frac{n}{5})}[/tex] <---سطر دوم درخت

[tex]\frac{\frac{n}{5^2}}{\log(\frac{n}{5^2})}[/tex] سطر دوم درخت که ۴ تا از اینا هست

حالا میرسیم به نوشتم فرمولهای هر سطر :

نکتش اینه که [tex]\frac{\frac{n}{5}}{\log(\frac{n}{5})}=\frac{n}{(\log n - \log5)}=\frac{n}{\log n-1}[/tex]

توجه کنید که لگاریتم در مبنای ۵ هست به خاطر همینه که لگاریتم ۵ برابر یک میشه

همونطور که میبینید دقیقا فرمولش با اون مثالی که توی کتاب حلش کرده برابره و جوابشون یکی میشه

نه اشتباه نکنید لگاریتم در مبنای ۲ نیست در مبنای ۵ هست. چرا؟

چونکه در صورت سوال داریم [tex]T(\frac{n}{5})[/tex] پس در هر سطر (همونطور که در بالا میبینید) توانی از ۵/n جایگزین n میشود.

به نظرتون کدامیک از روابط زیر درست است :

[tex]o(f(n))\: \subseteq\: O(f(n))\: -\: \ominus(f(n))[/tex]

[tex]o(f(n))\: !=\: O(f(n))\: -\ominus\: (f(n))[/tex]

(۱۷ تیر ۱۳۹۳ ۰۳:۰۵ ب.ظ)Pakniat نوشته شده توسط:  به نظرتون کدامیک از روابط زیر درست است :

[tex]o(f(n))\: \subseteq\: O(f(n))\: -\: \ominus(f(n))[/tex]

[tex]o(f(n))\: !=\: O(f(n))\: -\ominus\: (f(n))[/tex]

له نظره من دومی درسته.
چون براساس تعریف big O: از یک نقطه ای به بعد بزرگتر از تابع میشه در صورتیکه small o مطلاقا از تابع بزرگتره و نقطه اشتراک نداره.پس
big O زیر مجموعه small o حساب میشه.حالا شما اگه تتای تابع رو که از big O کوچکتره رو ازش کم کنید حتما از small o کمتر میشه.پس نتیجه میگیریم حاصل تفریق زیر مجموعه small o هستش نه برعکس.
که همین باعث میشه مورد دوم درست[/size] باشه

(۱۷ تیر ۱۳۹۳ ۰۵:۴۲ ب.ظ)mahdi200hell نوشته شده توسط:  له نظره من دومی درسته.
چون براساس تعریف big O: از یک نقطه ای به بعد بزرگتر از تابع میشه در صورتیکه small o مطلاقا از تابع بزرگتره و نقطه اشتراک نداره.پس
big O زیر مجموعه small o حساب میشه.حالا شما اگه تتای تابع رو که از big O کوچکتره رو ازش کم کنید حتما از small o کمتر میشه.پس نتیجه میگیریم حاصل تفریق زیر مجموعه small o هستش نه برعکس.
که همین باعث میشه مورد دوم درست[/size] باشه

اگر فرض بشه [tex]f(n)=n\: ;\: g(n)=n\: if\: n=2k\: ,\: 1\: if\: n=2k 1[/tex] در این حالت مورد دوم رو برای n های زوج چک کنید

If ( f(n) == sqrt(x) ) then

Y=x is O(f(n)) and

Y=(x^2)+2 is o(f(n)) and

Y=sqrt(x-2) is Ɵ(f(n))


مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
اینم لینک رسم نمودار این مثال نقض

میبینید که تساوی اول هیچ وقت واسه این مثال برقرار نمیشه
اینجور سوالارو فقط باید با تعریفش حل کرد

(۱۷ تیر ۱۳۹۳ ۰۷:۲۲ ب.ظ)mahdi200hell نوشته شده توسط:  If ( f(n) == sqrt(x) ) then

Y=x is O(f(n)) and

Y=(x^2)+2 is o(f(n)) and

Y=sqrt(x-2) is Ɵ(f(n))


مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
اینم لینک رسم نمودار این مثال نقض

میبینید که تساوی اول هیچ وقت واسه این مثال برقرار نمیشه
اینجور سوالارو فقط باید با تعریفش حل کرد

[tex]x^2 1\not\subseteq o(\sqrt{x})[/tex]
در ضمن Y شما تابع نیست ؛ به ازای هر x چند نگاشت مختلف در صفحه دارد

(۱۷ تیر ۱۳۹۳ ۰۵:۴۲ ب.ظ)mahdi200hell نوشته شده توسط:  

(17 تیر ۱۳۹۳ ۰۳:۰۵ ب.ظ)Pakniat نوشته شده توسط:  به نظرتون کدامیک از روابط زیر درست است :

[tex]o(f(n))\: \subseteq\: O(f(n))\: -\: \ominus(f(n))[/tex]

[tex]o(f(n))\: !=\: O(f(n))\: -\ominus\: (f(n))[/tex]

له نظره من دومی درسته.
چون براساس تعریف big O: از یک نقطه ای به بعد بزرگتر از تابع میشه در صورتیکه small o مطلاقا از تابع بزرگتره و نقطه اشتراک نداره.پس
big O زیر مجموعه small o حساب میشه.حالا شما اگه تتای تابع رو که از big O کوچکتره رو ازش کم کنید حتما از small o کمتر میشه.پس نتیجه میگیریم حاصل تفریق زیر مجموعه small o هستش نه برعکس.
که همین باعث میشه مورد دوم درست[/size] باشه

دارید برعکس میگیدا ! یعنی little O زیر مجموعه ی Big O میشه !! به عبارتی این رابطه بینشون برقراره !
[tex]o(n)\: \subset\: O(n)[/tex]
طبق تعریف litte o شامل مجموعه از توابع میشه که ازش کمتر باشن ( حد بالاشون little o باشه ) ولی تعریف Big o میشه کمتر یا مساوی مثلا O(x^2) رو و o(x^2) می بینید که تابع x^2+1 عضو little o نخواهد بود در صورتی که عضو big o هستش و همینطور عضو تتای x^2 !

بعضی وقتها توو یه سری نکات مسخره انقدر گیر میکنیم که....
[tex]\subseteqو\subset[/tex] الان من توو تفاوت این دوتا موندم
به این فرمول رسیدم [tex]o(f)\subseteq O(f)-Omega(f)[/tex] و گفته شده دلیلش اینه که توو سمت راستی توابعی هست که توو سمت چپی نیس. خب این که تعریفه این یکیه [tex]\subset[/tex]

(۲۶ تیر ۱۳۹۳ ۰۲:۰۳ ب.ظ)Ava.arshad94 نوشته شده توسط:  بعضی وقتها توو یه سری نکات مسخره انقدر گیر میکنیم که....
[tex]\subseteqو\subset[/tex] الان من توو تفاوت این دوتا موندم
به این فرمول رسیدم [tex]o(f)\subseteq O(f)-Omega(f)[/tex] و گفته شده دلیلش اینه که توو سمت راستی توابعی هست که توو سمت چپی نیس. خب این که تعریفه این یکیه [tex]\subset[/tex]

این چیزی ک شما میگید درستش اینه [tex]o(f)\subseteq O(f)-\theta(f)[/tex] و بعد هم فرق نماد [tex]\subseteq[/tex] و [tex]\subset[/tex] در این هست ک در مورد اولی ممکنه یک جاهایی هم دو طرف برابر بشن (تابعی ک انتخاب میکنید) ولی در مورد دومی میدانیم ک هیچ وقت مساوی نیستند صرفا زیرمجموعشه امکان مساوی بودن نداره.

(۲۶ تیر ۱۳۹۳ ۰۶:۲۲ ب.ظ)mahnaz.p نوشته شده توسط:  

(26 تیر ۱۳۹۳ ۰۲:۰۳ ب.ظ)Ava.arshad94 نوشته شده توسط:  بعضی وقتها توو یه سری نکات مسخره انقدر گیر میکنیم که....
[tex]\subseteqو\subset[/tex] الان من توو تفاوت این دوتا موندم
به این فرمول رسیدم [tex]o(f)\subseteq O(f)-Omega(f)[/tex] و گفته شده دلیلش اینه که توو سمت راستی توابعی هست که توو سمت چپی نیس. خب این که تعریفه این یکیه [tex]\subset[/tex]

این چیزی ک شما میگید درستش اینه [tex]o(f)\subseteq O(f)-\theta(f)[/tex] و بعد هم فرق نماد [tex]\subseteq[/tex] و [tex]\subset[/tex] در این هست ک در مورد اولی ممکنه یک جاهایی هم دو طرف برابر بشن (تابعی ک انتخاب میکنید) ولی در مورد دومی میدانیم ک هیچ وقت مساوی نیستند صرفا زیرمجموعشه امکان مساوی بودن نداره.

مرسی دوست عزیز
فرموله شما درست اما چیزی که من نوشتم یه فرمول دیگه ست و سوالم اینه که نباید اون علامت زیر مجموعه تغییر کنه؟ چون یه فرموله دیگه میگه این دو عبارتی که نوشتم برابرنیستن.پس وقتی برابر نیستن زیر مجموعه باید محض باشه و بدون اون خط کوفتیه زیرش
همین نکات ریز ممکنه بعضی وقتا از زیر دستمون در برن...

(۲۶ تیر ۱۳۹۳ ۰۶:۳۱ ب.ظ)Ava.arshad94 نوشته شده توسط:  

(26 تیر ۱۳۹۳ ۰۶:۲۲ ب.ظ)mahnaz.p نوشته شده توسط:  

(26 تیر ۱۳۹۳ ۰۲:۰۳ ب.ظ)Ava.arshad94 نوشته شده توسط:  بعضی وقتها توو یه سری نکات مسخره انقدر گیر میکنیم که....
[tex]\subseteqو\subset[/tex] الان من توو تفاوت این دوتا موندم
به این فرمول رسیدم [tex]o(f)\subseteq O(f)-Omega(f)[/tex] و گفته شده دلیلش اینه که توو سمت راستی توابعی هست که توو سمت چپی نیس. خب این که تعریفه این یکیه [tex]\subset[/tex]

این چیزی ک شما میگید درستش اینه [tex]o(f)\subseteq O(f)-\theta(f)[/tex] و بعد هم فرق نماد [tex]\subseteq[/tex] و [tex]\subset[/tex] در این هست ک در مورد اولی ممکنه یک جاهایی هم دو طرف برابر بشن (تابعی ک انتخاب میکنید) ولی در مورد دومی میدانیم ک هیچ وقت مساوی نیستند صرفا زیرمجموعشه امکان مساوی بودن نداره.

مرسی دوست عزیز
فرموله شما درست اما چیزی که من نوشتم یه فرمول دیگه ست و سوالم اینه که نباید اون علامت زیر مجموعه تغییر کنه؟ چون یه فرموله دیگه میگه این دو عبارتی که نوشتم برابرنیستن.پس وقتی برابر نیستن زیر مجموعه باید محض باشه و بدون اون خط کوفتیه زیرش
همین نکات ریز ممکنه بعضی وقتا از زیر دستمون در برن...

آها ببخشید حواسم نبود این فرمولیم ک شما نوشتید درسته و علامت زیر مجموعه مساوی باید باشه چون وقتی امگا رو از O کم میکنیم در واقه همون هم مرتبه ها یعنی همون تتا رو ازش کم میکنه(مرتبه های بالا ک اصلا تو O نیستند !) حالت مساوی هم پیش میاد مثلن f=n بگیرید

(۲۶ تیر ۱۳۹۳ ۰۶:۳۹ ب.ظ)mahnaz.p نوشته شده توسط:  

(26 تیر ۱۳۹۳ ۰۶:۳۱ ب.ظ)Ava.arshad94 نوشته شده توسط:  

(26 تیر ۱۳۹۳ ۰۶:۲۲ ب.ظ)mahnaz.p نوشته شده توسط:  

(26 تیر ۱۳۹۳ ۰۲:۰۳ ب.ظ)Ava.arshad94 نوشته شده توسط:  بعضی وقتها توو یه سری نکات مسخره انقدر گیر میکنیم که....
[tex]\subseteqو\subset[/tex] الان من توو تفاوت این دوتا موندم
به این فرمول رسیدم [tex]o(f)\subseteq O(f)-Omega(f)[/tex] و گفته شده دلیلش اینه که توو سمت راستی توابعی هست که توو سمت چپی نیس. خب این که تعریفه این یکیه [tex]\subset[/tex]

این چیزی ک شما میگید درستش اینه [tex]o(f)\subseteq O(f)-\theta(f)[/tex] و بعد هم فرق نماد [tex]\subseteq[/tex] و [tex]\subset[/tex] در این هست ک در مورد اولی ممکنه یک جاهایی هم دو طرف برابر بشن (تابعی ک انتخاب میکنید) ولی در مورد دومی میدانیم ک هیچ وقت مساوی نیستند صرفا زیرمجموعشه امکان مساوی بودن نداره.

مرسی دوست عزیز
فرموله شما درست اما چیزی که من نوشتم یه فرمول دیگه ست و سوالم اینه که نباید اون علامت زیر مجموعه تغییر کنه؟ چون یه فرموله دیگه میگه این دو عبارتی که نوشتم برابرنیستن.پس وقتی برابر نیستن زیر مجموعه باید محض باشه و بدون اون خط کوفتیه زیرش
همین نکات ریز ممکنه بعضی وقتا از زیر دستمون در برن...

آها ببخشید حواسم نبود این فرمولیم ک شما نوشتید درسته و علامت زیر مجموعه مساوی باید باشه چون وقتی امگا رو از O کم میکنیم در واقه همون هم مرتبه ها یعنی همون تتا رو ازش کم میکنه(مرتبه های بالا ک اصلا تو O نیستند !) حالت مساوی هم پیش میاد مثلن f=n بگیرید

نه.این مثال نقضشه
تابع دو ضابطه ای که برای nهای زوج مقدار n داشته باشه و برای n های فرد مقدار ۱
اینطوری میشه [tex]f\notin o(n)[/tex] چون یه جاهای مساوی n هست و طبق تعریف little o نباید مساوی باشه
اما بااین حال [tex]f\in O(n)-Omega(f)[/tex] درسته
با این مثال نقض باید زیر مجموعه ی محض باشه

---

این مثال نقض ماله جزوه ی استاد یوسفی هست مال منم نیست

(۲۶ تیر ۱۳۹۳ ۰۶:۴۶ ب.ظ)Ava.arshad94 نوشته شده توسط:  

(26 تیر ۱۳۹۳ ۰۶:۳۹ ب.ظ)mahnaz.p نوشته شده توسط:  

(26 تیر ۱۳۹۳ ۰۶:۳۱ ب.ظ)Ava.arshad94 نوشته شده توسط:  

(26 تیر ۱۳۹۳ ۰۶:۲۲ ب.ظ)mahnaz.p نوشته شده توسط:  

(26 تیر ۱۳۹۳ ۰۲:۰۳ ب.ظ)Ava.arshad94 نوشته شده توسط:  بعضی وقتها توو یه سری نکات مسخره انقدر گیر میکنیم که....
[tex]\subseteqو\subset[/tex] الان من توو تفاوت این دوتا موندم
به این فرمول رسیدم [tex]o(f)\subseteq O(f)-Omega(f)[/tex] و گفته شده دلیلش اینه که توو سمت راستی توابعی هست که توو سمت چپی نیس. خب این که تعریفه این یکیه [tex]\subset[/tex]

این چیزی ک شما میگید درستش اینه [tex]o(f)\subseteq O(f)-\theta(f)[/tex] و بعد هم فرق نماد [tex]\subseteq[/tex] و [tex]\subset[/tex] در این هست ک در مورد اولی ممکنه یک جاهایی هم دو طرف برابر بشن (تابعی ک انتخاب میکنید) ولی در مورد دومی میدانیم ک هیچ وقت مساوی نیستند صرفا زیرمجموعشه امکان مساوی بودن نداره.

مرسی دوست عزیز
فرموله شما درست اما چیزی که من نوشتم یه فرمول دیگه ست و سوالم اینه که نباید اون علامت زیر مجموعه تغییر کنه؟ چون یه فرموله دیگه میگه این دو عبارتی که نوشتم برابرنیستن.پس وقتی برابر نیستن زیر مجموعه باید محض باشه و بدون اون خط کوفتیه زیرش
همین نکات ریز ممکنه بعضی وقتا از زیر دستمون در برن...

آها ببخشید حواسم نبود این فرمولیم ک شما نوشتید درسته و علامت زیر مجموعه مساوی باید باشه چون وقتی امگا رو از O کم میکنیم در واقه همون هم مرتبه ها یعنی همون تتا رو ازش کم میکنه(مرتبه های بالا ک اصلا تو O نیستند !) حالت مساوی هم پیش میاد مثلن f=n بگیرید

نه.این مثال نقضشه
تابع دو ضابطه ای که برای nهای زوج مقدار n داشته باشه و برای n های فرد مقدار ۱
اینطوری میشه [tex]f\notin o(n)[/tex] چون یه جاهای مساوی n هست و طبق تعریف little o نباید مساوی باشه
اما بااین حال [tex]f\in O(n)-Omega(f)[/tex] درسته
با این مثال نقض باید زیر مجموعه ی محض باشه

---

این مثال نقض ماله جزوه ی استاد یوسفی هست مال منم نیست

درسته این مثال نقضشه منم نگفتم همه جا صادقه واسه همینم نماد زیرمجموعه مساوی میزاریم نه نماد مساوی خالی!یعنی بسته به تابعی ک داریم ممکنه مساوی شه یا زیر مجموعش باشه و نه مساوی

(۲۶ تیر ۱۳۹۳ ۰۷:۱۶ ب.ظ)mahnaz.p نوشته شده توسط:  

(26 تیر ۱۳۹۳ ۰۶:۴۶ ب.ظ)Ava.arshad94 نوشته شده توسط:  

(26 تیر ۱۳۹۳ ۰۶:۳۹ ب.ظ)mahnaz.p نوشته شده توسط:  

(26 تیر ۱۳۹۳ ۰۶:۳۱ ب.ظ)Ava.arshad94 نوشته شده توسط:  

(26 تیر ۱۳۹۳ ۰۶:۲۲ ب.ظ)mahnaz.p نوشته شده توسط:  این چیزی ک شما میگید درستش اینه [tex]o(f)\subseteq O(f)-\theta(f)[/tex] و بعد هم فرق نماد [tex]\subseteq[/tex] و [tex]\subset[/tex] در این هست ک در مورد اولی ممکنه یک جاهایی هم دو طرف برابر بشن (تابعی ک انتخاب میکنید) ولی در مورد دومی میدانیم ک هیچ وقت مساوی نیستند صرفا زیرمجموعشه امکان مساوی بودن نداره.

مرسی دوست عزیز
فرموله شما درست اما چیزی که من نوشتم یه فرمول دیگه ست و سوالم اینه که نباید اون علامت زیر مجموعه تغییر کنه؟ چون یه فرموله دیگه میگه این دو عبارتی که نوشتم برابرنیستن.پس وقتی برابر نیستن زیر مجموعه باید محض باشه و بدون اون خط کوفتیه زیرش
همین نکات ریز ممکنه بعضی وقتا از زیر دستمون در برن...

آها ببخشید حواسم نبود این فرمولیم ک شما نوشتید درسته و علامت زیر مجموعه مساوی باید باشه چون وقتی امگا رو از O کم میکنیم در واقه همون هم مرتبه ها یعنی همون تتا رو ازش کم میکنه(مرتبه های بالا ک اصلا تو O نیستند !) حالت مساوی هم پیش میاد مثلن f=n بگیرید

نه.این مثال نقضشه
تابع دو ضابطه ای که برای nهای زوج مقدار n داشته باشه و برای n های فرد مقدار ۱
اینطوری میشه [tex]f\notin o(n)[/tex] چون یه جاهای مساوی n هست و طبق تعریف little o نباید مساوی باشه
اما بااین حال [tex]f\in O(n)-Omega(f)[/tex] درسته
با این مثال نقض باید زیر مجموعه ی محض باشه

---

این مثال نقض ماله جزوه ی استاد یوسفی هست مال منم نیست

درسته این مثال نقضشه منم نگفتم همه جا صادقه واسه همینم نماد زیرمجموعه مساوی میزاریم نه نماد مساوی خالی!یعنی بسته به تابعی ک داریم ممکنه مساوی شه یا زیر مجموعش باشه و نه مساوی

آخ آخ آخ فکنم اشتباهمو فهمیدم. داشتم برعکس به قضیه میفکریدم بخاظر مثال نقضه
مرسی دوستم کامل افتاد

(۲۶ تیر ۱۳۹۳ ۰۷:۳۸ ب.ظ)Ava.arshad94 نوشته شده توسط:  

(26 تیر ۱۳۹۳ ۰۷:۱۶ ب.ظ)mahnaz.p نوشته شده توسط:  

(26 تیر ۱۳۹۳ ۰۶:۴۶ ب.ظ)Ava.arshad94 نوشته شده توسط:  

(26 تیر ۱۳۹۳ ۰۶:۳۹ ب.ظ)mahnaz.p نوشته شده توسط:  

(26 تیر ۱۳۹۳ ۰۶:۳۱ ب.ظ)Ava.arshad94 نوشته شده توسط:  مرسی دوست عزیز
فرموله شما درست اما چیزی که من نوشتم یه فرمول دیگه ست و سوالم اینه که نباید اون علامت زیر مجموعه تغییر کنه؟ چون یه فرموله دیگه میگه این دو عبارتی که نوشتم برابرنیستن.پس وقتی برابر نیستن زیر مجموعه باید محض باشه و بدون اون خط کوفتیه زیرش
همین نکات ریز ممکنه بعضی وقتا از زیر دستمون در برن...

آها ببخشید حواسم نبود این فرمولیم ک شما نوشتید درسته و علامت زیر مجموعه مساوی باید باشه چون وقتی امگا رو از O کم میکنیم در واقه همون هم مرتبه ها یعنی همون تتا رو ازش کم میکنه(مرتبه های بالا ک اصلا تو O نیستند !) حالت مساوی هم پیش میاد مثلن f=n بگیرید

نه.این مثال نقضشه
تابع دو ضابطه ای که برای nهای زوج مقدار n داشته باشه و برای n های فرد مقدار ۱
اینطوری میشه [tex]f\notin o(n)[/tex] چون یه جاهای مساوی n هست و طبق تعریف little o نباید مساوی باشه
اما بااین حال [tex]f\in O(n)-Omega(f)[/tex] درسته
با این مثال نقض باید زیر مجموعه ی محض باشه

---

این مثال نقض ماله جزوه ی استاد یوسفی هست مال منم نیست

درسته این مثال نقضشه منم نگفتم همه جا صادقه واسه همینم نماد زیرمجموعه مساوی میزاریم نه نماد مساوی خالی!یعنی بسته به تابعی ک داریم ممکنه مساوی شه یا زیر مجموعش باشه و نه مساوی

آخ آخ آخ فکنم اشتباهمو فهمیدم. داشتم برعکس به قضیه میفکریدم بخاظر مثال نقضه
مرسی دوستم کامل افتاد

خواهش میکنم

(۲۶ تیر ۱۳۹۳ ۰۲:۰۳ ب.ظ)Ava.arshad94 نوشته شده توسط:  الان من توو تفاوت این دوتا موندم
به این فرمول رسیدم [tex]o(f)\subseteq O(f)-Omega(f)[/tex] و گفته شده دلیلش اینه که توو سمت راستی توابعی هست که توو سمت چپی نیس. خب این که تعریفه این یکیه [tex]\subset[/tex]

سلام.
این درسته :


[tex]o(f)\subset O(f)-Omega(f)[/tex]

سلام دوستان
میگم برای فهمیدن مرتبه اجرایی حلقه های تودرتو وابسته در سر جلسه کنکور چه راهی بهتر از trace کردن چند مرحله از الگوریتم است که سریع به جواب برسیم
مثلا
for(i=1;i<=n;i*2)
for(j=1;j<=i;j*2
{
x++;
{

(۱۰ مرداد ۱۳۹۳ ۱۲:۲۶ ق.ظ)bernova نوشته شده توسط:  سلام دوستان
میگم برای فهمیدن مرتبه اجرایی حلقه های تودرتو وابسته در سر جلسه کنکور چه راهی بهتر از trace کردن چند مرحله از الگوریتم است که سریع به جواب برسیم
مثلا
for(i=1;i<=n;i*2)
for(j=1;j<=i;j*2
{
x++;
{

نه فکر نمی کنم روش دیگه ای وجود داشته باشه خود این روش trace کردن هم به نظرم مشکل نیست اگه چند نمونه از این مساله ها حل کنید زود راه می افتید. برای مساله بالا هم با trace کردن به جواب (O(logn می رسیم.

سلام دوست عزیز
منمنون از توجه تون
لطفا به حلقه تودرتو زیر نیز یه نگاه بنداز تو جزوه امیرکبیر یه جواب داده ، پارسه هم یه جواب
مرتبه اجراییی الگوریتم زیر چقدر است
for(i=0;i<n;i++[/align]

(۱۱ مرداد ۱۳۹۳ ۱۰:۳۸ ب.ظ)bernova نوشته شده توسط:  سلام دوست عزیز
منمنون از توجه تون
لطفا به حلقه تودرتو زیر نیز یه نگاه بنداز تو جزوه امیرکبیر یه جواب داده ، پارسه هم یه جواب
مرتبه اجراییی الگوریتم زیر چقدر است
for(i=0;i<n;i++[/align]

برای حلقه ی for خالی که مرتبه تعیین نمی کنن. از روی این حلقه ای که شما نوشتید فقط تعداد دفعات تکرار خود for به اضافه ی تعداد تکرار داخل حلقه ی for مشخص می شه.اگه هدف ما تعیین مرتبه باشه بایستی دنبال دستور اصلی باشیم.

اقا شرمنده من نمیدونم چرا حلقه for اینطوری پست شد اینجا منظورم مرتبه اجرایی حلقه زیر است
for(I=1;I<n;I++)1
for(j=1;j<n;J++)1
{
x++
n++
}
بازم ببخشید

(۱۲ مرداد ۱۳۹۳ ۰۴:۳۵ ب.ظ)bernova نوشته شده توسط:  اقا شرمنده من نمیدونم چرا حلقه for اینطوری پست شد اینجا منظورم مرتبه اجرایی حلقه زیر است
for(I=1;I<n;I++)1
for(j=1;j<n;J++)1
}
x++
n--
{
{
بازم ببخشید

مراحل trace:
i=1---------------> بار n/2
i=2---------------> بار n/4
i=3---------------> بار n/8
i=4--------------> بار n/16
.....................................
i=log n---> بار n/2^ log n
جمع تعداد دفعات تکرار: (n/2+n/4+n/8+n/16+...+n/n=n(1/2+1/4+1/8+...+1/n)=n(1-1/n)=n-1=O(n

(۱۲ مرداد ۱۳۹۳ ۰۴:۳۵ ب.ظ)bernova نوشته شده توسط:  اقا شرمنده من نمیدونم چرا حلقه for اینطوری پست شد اینجا منظورم مرتبه اجرایی حلقه زیر است
for(I=1;I<n;I++)1
for(j=1;j<n;J++)1
{
x++
n++
}
بازم ببخشید

مطمعنین اون n++ هست و n-- نیست؟

ببینم فکر کنم --n باشه نه ++n؟

اره n-- ,است . یکی از مثال های پارسه است
منظورم اینه که تو پارسه میگه O(n و جزوه امیرکبیر میگه O(nlogn به نظر من دومی است

(۱۲ مرداد ۱۳۹۳ ۱۰:۳۹ ب.ظ)bernova نوشته شده توسط:  اره n-- ,است . یکی از مثال های پارسه است
منظورم اینه که تو پارسه میگه O(n و جزوه امیرکبیر میگه O(nlogn به نظر من دومی است

دوستان منم فکر می کنم n log n درست باشه، چون شمارنده حلقه ها به هم وابسته نیستند تعداد تکرار حلقه ها در هم ضرب میشن.
در حلقه داخلی هر بار ۲واحد کاهش داریم چون یک بار j را می بریم جلو و یکبار از n کم می کنیم، پس حقه داخلی هربار n/2 بار اجرا میشه که مرتبه اجراییش میشه n، حالا وقتی از حلقه داخلی خارج میشم n شده n/2 یعنی بازه حلقه بیرونی شده از یک تا n/2 پس مثل اینه که گام کاهش حلقه بیرونی تقسیم بر ۲ هست که مرتبه اجراییش میشه log n ، پس مرتبه اجرایی دو حلقه میشه n log n

کسی فهمید من چی گفتم؟

---

اولین بار به ازای [tex]i=1[/tex] تعداد تکرار [tex]\frac{n}{2}[/tex] هستش و به ازای [tex]i=2[/tex] تعداد تکرار [tex]\frac{n}{4}[/tex] هستش و به همین ترتیب.j در هر بار به اندازه [tex]\frac{n}{2}[/tex]، ([tex]n[/tex]) تکرار میشه که برای بار دوم همون[tex]\frac{n}{4}[/tex] هستش .اخرش هم مرتبه اجرا همون n میشه.,وقتی لگاریتم درسته که رشد حلقمون لگاریتمی باشه(یعنی شرط حلقه).در صورتی که اینجا اینطور نیستش

نظرتون در مورد این حلقه چیه؟
for(int i=0; i<=n; i/=2)
cout<<"*";
غیر از اینه که چون هر بار بازه داره نصف میشه مرتبه اجراییش میشه log n
الان دقیقا همین اتفاق داره واسه حلقه بیرونی می افته

ببینید تو مثال شما درسته شمارنده هر بار داره نصف میشه پس زمان اجرا [tex]\lg(n)[/tex].ولی تو مثال قبلی شمارنده داره یه واحد هر بار اضافه میشه.یعنی همیشه داریم [tex]i=1[/tex] ،بعدش [tex]i=2[/tex] بعد [tex]i=3[/tex] و همینطور تا زمانی که [tex]i\le n[/tex].درسته؟
حالا ما باید مجموع اجرای [tex]i[/tex] ها رو به دست بیاریم اکی؟
قبول دارید به ازای [tex]i=1[/tex] جمله اصلی به اندازه [tex]\frac{n}{2}[/tex] اجرا میشه؟
و به ازای [tex]i=2[/tex] جمله اصلی به اندازه [tex]\frac{n}{4}[/tex] اجرا میشه؟
و به ازای [tex]i=3[/tex] جمله اصلی به اندازه [tex]\frac{n}{8}[/tex] اجرا میشه؟
و همینطوری تا اخر ادامه پیدا میکنه.

حالا میخوایم مجموع اجرای [tex]i[/tex] ها رو حساب کنیم:

[tex]\frac{n}{2} \frac{n}{4} \frac{n}{8} ...=n(\frac{1}{2} \frac{1}{4} \frac{1}{8} ...)=n\cdot\frac{\frac{1}{2}}{1-\frac{1}{2}}=n\cdot\frac{\frac{1}{2}}{\frac{1}{2}}=n=\theta(n)[/tex]

اکی؟توی مثال شما ما مطمئنیم که به ازای هر [tex]n[/tex] اون [tex]n[/tex] به اندازه [tex]\lg(n)[/tex] بار اجرا میشه چون فقط کافیه تعداد باری که شمارنده داره اضافه میشه رو بشماریم و چون شمارنده هم داره لگاریتمی اضافه میشه پس زمان اجرا [tex]\lg(n)[/tex] میشه ولی تو این مثال به ازای هر [tex]i[/tex] رابطه بالا برقراره.
امیدوارم براتون خوب توضیح داده باشم

در ضمن فکر کنم شرط حلقتون باید *(ضرب) باشه نه /(تقسیم).

(۱۹ مرداد ۱۳۹۳ ۰۹:۱۵ ق.ظ)miladcr7 نوشته شده توسط:  در ضمن فکر کنم شرط حلقتون باید *(ضرب) باشه نه /(تقسیم).

خیلی ممنون توضیحت کامل بود بله شرط حلقه ضربه، حالا اگه حلقمون تودرتو نباشه و به صورت زیر باشه چی میشه؟
for(int i= 1; i<=n; i++) 1
n/=2; 1

یکهای آخر خط را فقط برای این زدم که فونتش به هم نخوره
مرسیییییییییییی

فکر کنم باید از همون مرتبه [tex]\lg(n)[/tex] باشه البته اگه همین یه حلقه منظورته

(۱۹ مرداد ۱۳۹۳ ۰۶:۰۸ ب.ظ)miladcr7 نوشته شده توسط:  فکر کنم باید از همون مرتبه [tex]\lg(n)[/tex] باشه البته اگه همین یه حلقه منظورته

آره منظورم همون یه حلقه اس،
حالا می دونید چی گیجم میکنه؟ اینکه توی مثال اول حلقه داخلی داره کار نصف کردن n را انجام میده پس حلقه بیرونی مثل این حلقه تکیه میشه که مرتبش لگاریتمیه

ببین بذار اینطور بگیم.از مثال دوم شروع میکنیم خب:

[tex]for(int\: i=1\: ;\: i<n\: ;\: i )[/tex]
}
[tex]x ;[/tex]

[tex]n=\frac{n}{2}[/tex]
{

اینجا کار ما راحته ببین ما بازم برای زمان اجرا ،میخوایم تعداد باری که [tex]x[/tex] اجرا میشه رو به دست بیاریم خب؟
حالا قبول داری به ازای [tex]i=1[/tex] جمله اصلی( که همون [tex]x 1[/tex] هستش ) ۱ بار اجرا میشه؟
و به ازای [tex]i=2[/tex] جمله اصلی( که همون [tex]x 1[/tex] هستش ) بازم ۱ بار اجرا میشه؟
تا وقتی که [tex]i>n[/tex] برقرار شه و شرط حلقه رو نقض کنه.اکی؟
حالا برای به دست اوردن زمان اجرا ما باید تعداد این دفعات رو بشماریم خب یا مجموع این [tex][tex]i[/tex][/tex] ها رو به دست بیاریم.حالا دقت کن این بار دیگه اینطور نیست که بگیم مثلا به ازای [tex]i=1[/tex] جمله اصلی [tex]\frac{n}{2}[/tex] تکرار میشه و...
چون گفتیم به ازای هر [tex][tex]i[/tex][/tex] جمله اصلی ۱ بار فقط اجرا میشه حالا ما میخوایم تعداد این [tex][tex]i[/tex][/tex] رو به دست بیاریم
اگه برای چند عدد تست کنی میبینی که برای هر عدد [tex]n[/tex] تعداد [tex][tex]i[/tex][/tex] برابر [tex]Lg(n)[/tex] میشه پس زمان اجرا هم [tex]Lg(n)[/tex] میشه.هر چند با یه خرده دقت میتونستی بفهمی تقسیم شدن عدد [tex]n[/tex] تو این مثال مثل ضرب یا تقسیم شدن شمارندست البته چون یه حلقه داریم ها.

حالا مثال اول. توی مثال اول ما بازم میخوایم مجموع تعداد دفعات اجرای جمله اصلی به ازای هر [tex][tex]i[/tex][/tex] رو به دست بیاریم.دقت کن چون
حلقه تو در تو داریم پس دیگه نمیتونیم بگیم به ازای هر [tex][tex]i[/tex][/tex] جمله اصلی یه بار اجرا میشه و چون هر بار یه واحد از مقدار [tex]n[/tex] هم با اجرای جمله اصلی کم میشه پس نمیشه گفت به ازای هر [tex][tex]i[/tex][/tex] جمله اصلی [tex]n[/tex] بار تکرار میشه.حالا ما این مجموع رو حساب میکنیم اگه مجموع تعداد دفعات اجرای جمله اصلی [tex]Lg(n)[/tex] شد خب حرف شما قابل قبول.پس ما همیشه برای زمان اجرا مجموع تعداد اجرای جمله اصلی رو حساب میکنیم.

حالا ما باید مجموع اجرای [tex][tex]i[/tex][/tex] ها رو به دست بیاریم اکی؟
قبول دارید به ازای [tex]i=1[/tex] جمله اصلی به اندازه [tex]\frac{n}{2}[/tex] اجرا میشه؟
و به ازای [tex]i=2[/tex] جمله اصلی به اندازه [tex]\frac{n}{4}[/tex] اجرا میشه؟
و به ازای [tex]i=3[/tex] جمله اصلی به اندازه [tex]\frac{n}{8}[/tex] اجرا میشه؟
و همینطوری تا اخر ادامه پیدا میکنه.

حالا میخوایم مجموع اجرای [tex][tex]i[/tex][/tex] ها رو حساب کنیم:

[tex]\frac{n}{2} \frac{n}{4} \frac{n}{8} ...=n(\frac{1}{2} \frac{1}{4} \frac{1}{8} ...)=n\cdot\frac{\frac{1}{2}}{1-\frac{1}{2}}=n\cdot\frac{\frac{1}{2}}{\frac{1}{2}}=n=\theta(n)[/tex]

پس زمان اجرا همون [tex]\theta(\: n)[/tex] میشه.


دقت کن که جمله [tex]n--[/tex] باعث شده دیگه نتونیم بگیم مثلا حلقه اول دقیقا این قدر اجرا میشه و حلقه دوم هم به همچنین.اگه
[tex]n--[/tex] نبودش زمان اجرای حلقه رو میتونستیم به دست بیاریم ولی با این شرایط به ازای [tex]i=1[/tex] حلقه دوم یه تعداد بار اجرا میشه و به ازای [tex]i=2[/tex] یه تعداد بار دیگه.پس ما مجبوریم که مجموع این تعداد بارها رو به دست بیاریم

(۲۰ مرداد ۱۳۹۳ ۱۲:۰۳ ب.ظ)miladcr7 نوشته شده توسط:  ببین بذار اینطور بگیم.از مثال دوم شروع میکنیم خب:

[tex]for(int\: i=1\: ;\: i<n\: ;\: i )[/tex]
}
[tex]x ;[/tex]

[tex]n=\frac{n}{2}[/tex]
{

اینجا کار ما راحته ببین ما بازم برای زمان اجرا ،میخوایم تعداد باری که [tex]x[/tex] اجرا میشه رو به دست بیاریم خب؟
حالا قبول داری به ازای [tex]i=1[/tex] جمله اصلی( که همون [tex]x 1[/tex] هستش ) ۱ بار اجرا میشه؟
و به ازای [tex]i=2[/tex] جمله اصلی( که همون [tex]x 1[/tex] هستش ) بازم ۱ بار اجرا میشه؟
تا وقتی که [tex]i>n[/tex] برقرار شه و شرط حلقه رو نقض کنه.اکی؟
حالا برای به دست اوردن زمان اجرا ما باید تعداد این دفعات رو بشماریم خب یا مجموع این [tex][tex]i[/tex][/tex] ها رو به دست بیاریم.حالا دقت کن این بار دیگه اینطور نیست که بگیم مثلا به ازای [tex]i=1[/tex] جمله اصلی [tex]\frac{n}{2}[/tex] تکرار میشه و...
چون گفتیم به ازای هر [tex][tex]i[/tex][/tex] جمله اصلی ۱ بار فقط اجرا میشه حالا ما میخوایم تعداد این [tex][tex]i[/tex][/tex] رو به دست بیاریم
اگه برای چند عدد تست کنی میبینی که برای هر عدد [tex]n[/tex] تعداد [tex][tex]i[/tex][/tex] برابر [tex]Lg(n)[/tex] میشه پس زمان اجرا هم [tex]Lg(n)[/tex] میشه.هر چند با یه خرده دقت میتونستی بفهمی تقسیم شدن عدد [tex]n[/tex] تو این مثال مثل ضرب یا تقسیم شدن شمارندست البته چون یه حلقه داریم ها.

حالا مثال اول. توی مثال اول ما بازم میخوایم مجموع تعداد دفعات اجرای جمله اصلی به ازای هر [tex][tex]i[/tex][/tex] رو به دست بیاریم.دقت کن چون
حلقه تو در تو داریم پس دیگه نمیتونیم بگیم به ازای هر [tex][tex]i[/tex][/tex] جمله اصلی یه بار اجرا میشه و چون هر بار یه واحد از مقدار [tex]n[/tex] هم با اجرای جمله اصلی کم میشه پس نمیشه گفت به ازای هر [tex][tex]i[/tex][/tex] جمله اصلی [tex]n[/tex] بار تکرار میشه.حالا ما این مجموع رو حساب میکنیم اگه مجموع تعداد دفعات اجرای جمله اصلی [tex]Lg(n)[/tex] شد خب حرف شما قابل قبول.پس ما همیشه برای زمان اجرا مجموع تعداد اجرای جمله اصلی رو حساب میکنیم.

حالا ما باید مجموع اجرای [tex][tex]i[/tex][/tex] ها رو به دست بیاریم اکی؟
قبول دارید به ازای [tex]i=1[/tex] جمله اصلی به اندازه [tex]\frac{n}{2}[/tex] اجرا میشه؟
و به ازای [tex]i=2[/tex] جمله اصلی به اندازه [tex]\frac{n}{4}[/tex] اجرا میشه؟
و به ازای [tex]i=3[/tex] جمله اصلی به اندازه [tex]\frac{n}{8}[/tex] اجرا میشه؟
و همینطوری تا اخر ادامه پیدا میکنه.

حالا میخوایم مجموع اجرای [tex][tex]i[/tex][/tex] ها رو حساب کنیم:

[tex]\frac{n}{2} \frac{n}{4} \frac{n}{8} ...=n(\frac{1}{2} \frac{1}{4} \frac{1}{8} ...)=n\cdot\frac{\frac{1}{2}}{1-\frac{1}{2}}=n\cdot\frac{\frac{1}{2}}{\frac{1}{2}}=n=\theta(n)[/tex]

پس زمان اجرا همون [tex]\theta(\: n)[/tex] میشه.


دقت کن که جمله [tex]n--[/tex] باعث شده دیگه نتونیم بگیم مثلا حلقه اول دقیقا این قدر اجرا میشه و حلقه دوم هم به همچنین.اگه
[tex]n--[/tex] نبودش زمان اجرای حلقه رو میتونستیم به دست بیاریم ولی با این شرایط به ازای [tex]i=1[/tex] حلقه دوم یه تعداد بار اجرا میشه و به ازای [tex]i=2[/tex] یه تعداد بار دیگه.پس ما مجبوریم که مجموع این تعداد بارها رو به دست بیاریم

آره کاملا توجیح شدم، گرچه هنوز نفهمیدم اشتباه کارم جاست ولی منطق استدلال شما را کاملا متوجه میشوم، (البته فکر کنم من وابستگی حلقه ها را لحاظ نمی کنم) به هر حال ممنونم ازت بابت وقتی که گذاشتی

فکر کنم بدونم برای چی قاطی کردی.یه چند تا مثال میزنم امیدوارم باعث نشم بیشتر قاطی کنی.

این حلقه رو در نظر بگیر:

[tex]for\: (int\: i=0\: ;\: i<n\: ;\: i )[/tex]
}
[tex]x ;[/tex]
{

حالا زمان اجرا:قبول داری حلقه [tex][tex]n[/tex][/tex] بار دستور اصلی ( که همون [tex]x ;[/tex] هستش ) رو اجرا میکنه که این [tex][tex]n[/tex][/tex] بار همون تعداد اجرای شمارنده حلقه( [tex][tex]i[/tex][/tex] ) هم هست درسته؟پس زمان اجرا میشه:[tex]\theta(n)[/tex]

________________________________________________________________________________​______________________-

حالا این حلقه رو در نظر بگیر:

[tex]for\: (int\: i=0\: ;\: i<n\: ;\: i )[/tex]

}
[tex]for\: (int\: j=0\: ;\: j<n\: ;\: j )[/tex]
}
[tex]x ;[/tex]
{
{

حالا زمان اجرا:قبول داری به ازای هر [tex][tex]i[/tex][/tex] حلقه دومی به اندازه [tex][tex]n[/tex][/tex] بار اجرا میشه و متعاقبا جمله اصلی هم [tex][tex]n[/tex][/tex] بار
تکرار میشه؟
ولی یه مسئله ای که باید بهش دقت کنی اینه که به ازای هر [tex][tex]i[/tex][/tex] از حلقه اول، حلقه دومی داره به اندازه ثابتی اجرا میشه درسته؟
پس برای همین ما میتونیم بگیم که طبق اصل شمارش تعداد اجرای دستور اصلی میشه:
به ازای هر [tex][tex]i[/tex][/tex] ،جمله اصلی [tex][tex]n[/tex][/tex] بار تکرار میشه پس به ازای [tex][tex]n[/tex][/tex] بار میشه :[tex]n\ast n[/tex] که
زمان اجرا میشه :[tex]\theta(n^2)[/tex]

ببین حالا نکته اینجاست:وقتی مثلا دو حلقه تو در تو داریم زمانی میتونی تعداد اجرای حلقه بیرونی رو مستقل از حلقه دوم بگی( مثلا بگی حلقه بیرونی [tex][tex]n[/tex][/tex] بار اجرا میشه و حلقه تویی [tex]\lg(n)[/tex] بار) که به ازای هر [tex][tex]i[/tex][/tex] توی حلقه اول، حلقه دوم به تعداد [tex]\lg(n)[/tex] بار اجرا بشه که نیازی نباشه مجموع بگیری ولی اگه به ازای هر [tex][tex]i[/tex][/tex] از حلقه اولی ،حلقه دوم به تعداد متغیری اجرا شد دیگه نمیتونی زمان اجرای حلقه اول رو همینطوری مستقل بگی میدونی چرا؟مثال زیر رو داشته باش


[tex]for\: (int\: i=0\: ;\: i<n\: ;\: i )[/tex]

}
[tex]for\: (int\: j=0\: ;\: j<i\: ;\: j )[/tex]
}
[tex]x ;[/tex]
{
{


خب حالا سوال من اینه : حلقه اول [tex][tex]n[/tex][/tex] بار اجرا میشه درسته؟ ولی ایا میتونی برای محاسبه تعداد دفعات اجرای جمله اصلی بیای
از این روش بری که بگی حلقه اول [tex][tex]n[/tex][/tex] بار تکرار میشه ؟نه نمیتونی چون به ازای هر [tex][tex]i[/tex][/tex] توی حلقه اول ،حلقه دوم داره به یه مقدار متغیر اجرا میشه مثلا به ازای [tex]i=1[/tex] حلقه دوم ۱ بار و به ازای [tex]i=2[/tex] حلقه دوم ۲ بار و همینجوری.خب الان اگه برای به دست اوردن تعداد دفعه اجرای جمله اصلی بیایم بگیم حلقه اول [tex][tex]n[/tex][/tex] بار اجرا میشه اون وقت برای حلقه دوم چی بگیم؟مگه نباید توی این روش تعداد دفعه اجرای حلقه دوم رو توی تعداددفعه اجرای حلقه اول ضرب کنیم؟ولی میبینی نمیتونیم این کار رو انجام بدیم چون تعداد دفعه اجرای حلقه دوم به ازای هر بار اجرای حلقه اول متغیره اکی؟
پس مجبوریم مجموع تعداد دفعات اجرای حلقه دوم رو به ازای هر بار اجرای حلقه اول محاسبه کنیم که تو این مثال داریم:

به ازای هر [tex][tex]i[/tex][/tex] حلقه دوم از ۱ تا [tex]j[/tex] متغیره و [tex][tex]i[/tex][/tex] بار تکرار میشه.
یعنی به ازای [tex]i=1[/tex] حلقه دوم ۱ بار و به ازای [tex]i=2[/tex] حلقه دوم ۲ بار و همینجوری پس زمان اجرا:

[tex]1 2 3 ... n=\frac{n\ast(n 1)}{2}=\theta(n^2)[/tex]


________________________________________________________________________________​________________

حالا توی مثال خودمون اگه بگی حلقه اول [tex]\lg(n)[/tex] بار داره تکرار میشه برای حلقه دوم چی میگی؟
در ضمن برای حلقه دوم هم دقت کن نمیتونیم بگیم زمان اجراش [tex]\theta(n)[/tex] چون هر بار [tex][tex]n[/tex][/tex] داره عوض میشه پس باید بیایم مجموع این تعداد اجراها رو به دست بیاریم یعنی به ازای [tex]i=1[/tex] حلقه دوم چند بار اجرا میشه و به ازای [tex]i=2[/tex] حلقه دوم چند بار تکرار میشه.ما از این روش استفاده کردیم چون به ازای هر [tex][tex]i[/tex][/tex] تو حلقه اول ،حلقه دوم به مقدار متغیری داره اجرا میشه پس باید مجموع این اجراها رو به دست بیاریم.ولی اگه بگیم حلقه اول [tex]\lg(n)[/tex] بار داره تکرار میشه اون وقت تعداد اجرای حلقه دوم رو نداریم یه بار [tex]\frac{n}{2}[/tex] بار اجرا میشه و یه بار [tex]\frac{n}{4}[/tex] و ....
وقتی هم داریم مجموع این تعداد اجراها رو به دست بیاریم در واقع زمان اجرای کل رو داریم به دست میاریم

________________________________________________________________________________​________________________

اوه اوه چه زیاد شد ببخشید دیگه.امیدوارم خوب توضیح داده باشم.اگه بازم مشکلی بود بگو تا اگه تونستیم حلش میکنیم و اگه هم نتونستیم از بقیه دوستان کمک میگیریم

به نظر من همون مرتبه n درسته

براساس تریس که کردین شد n

دوستان این روابط بازگشتی و این چیزارو با کدوم کتاب خوب یاد میگیرم.
هیچ جوره من یادش نمیگیرم

اره یه تریس کنید معلوم میشه

(۲۱ مرداد ۱۳۹۳ ۰۹:۱۸ ق.ظ)miladcr7 نوشته شده توسط:  خواهش میکنم.چه اشتباهی رو متوجه نشدی بگو شاید تونستم کمکت کنم؟

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

سلام خسته نباشید.اره دیگه ازت یاد گرفتم

سلام دوستان
لطفا اگه کسی میتونه به این سوالم جواب بده. مرسی

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

بله همون الگوریتم جایگشت هستش

(۲۹ مرداد ۱۳۹۳ ۰۶:۴۵ ب.ظ)miladcr7 نوشته شده توسط:  بله همون الگوریتم جایگشت هستش

توو تاپیکه خودش یکم توضیح میدی؟ منم گیج شدم


Sent from my iPad using
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

چیشو توضیح بدم؟

خب صورت اصلی که اینه:[tex]T(n)=5T(\frac{n}{5}) \frac{n}{\lg n}[/tex]

خب پایه لگاریتم دو هستش و ما هر بار داریم به جای n مقدار میذاریم ،پایه که تغییر نمیکنه.توی مثال صفحه ۴۲ هم اینطور بود بازم همون پایه لگاریتم ۲ بود.
ولی فرقش این بود که هر بار [tex]\frac{n}{2}[/tex] یا [tex]\frac{n}{4}[/tex] یا .... میشد که اینا توان دو هستن

مثلا:
[tex]\lg^{\frac{n}{8}}_2=\lg^n_2-\lg^8_2=\lg^n_2-3[/tex]

حالا این مثال هم اینطوره دیگه:
مثلا توی سطح دوم داریم:
[tex]\lg^{\frac{n}{25}}_2=\lg^n_2-\lg^{25}_2=\lg^n_2-2\lg^5_2[/tex]

اشتباه میگم؟

سلام. بچه ها تو کتاب مقسمی یه چیزی بیان شده که برا من عجیبه! به این صورت که اگر k=0 باشه، جواب این عبارت صفر میشه:
a[i] = k++
ینی:
a[i] = 0
و این برخلاف چیزیه که من تا حالا میدونستم. آیا من درست متوجه موضوع نشدم یا توضیح مقسمی مشکل داره؟ در ضمن این مربوط به سوال ۱۵ صفحه ۲۸ کتابشه.

(۰۲ مهر ۱۳۹۳ ۰۸:۰۷ ب.ظ)ldns0098 نوشته شده توسط:  سلام. بچه ها تو کتاب مقسمی یه چیزی بیان شده که برا من عجیبه! به این صورت که اگر k=0 باشه، جواب این عبارت صفر میشه:
a[i] = k++
ینی:
a[i] = 0
و این برخلاف چیزیه که من تا حالا میدونستم. آیا من درست متوجه موضوع نشدم یا توضیح مقسمی مشکل داره؟ در ضمن این مربوط به سوال ۱۵ صفحه ۲۸ کتابشه.

سلام، ببینید عبارات ++k و k++ با هم فرق دارن، در عبارتی که شما گفتید چون شکل اولی رو گذاشته یعنی اول محتوای k رو بریز تو a ،بعد یکی به k اضافه کن. اما اگه شکل دوم یعنی k++ به کار رفته بود ،یعنی اول یکی به k اضافه کن بعد بریزش تو a .

سلام خواستم بدونم سوالات مربوط به لیستای پیوندی چطور حل میشن
مثل این سوال