زمان کنونی: ۲۱ فروردین ۱۴۰۰, ۰۴:۴۹ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

حل سوالات ساختمان داده و طراحی الگوریتم(۶۰۰ مساله،و تست های مهم)(۱)

۱۲
subtitle
ارسال:
  

Saman پرسیده:

حل سوالات ساختمان داده و طراحی الگوریتم(۶۰۰ مساله،و تست های مهم)(۱)

سلام.
درخواست از مدیران محترم سایت : خواهشا به هیچ وجه تیک درست سوالات را نزنید،پاسخ سوالات در همه جا موجود است،و اینجا نحوه ی پاسخگویی متفاوت و البته کامل تر است
درخواست از کاربران محترم : جدا از گذاشتن سپاس و تشکر خودداری کنید،طرح سوالات به عهده ی خودم هست و پاسخ های مختلف از خودم و سایر کاربران،اگر سوالی به نظرتون جالب اومد و در طول سلسله مراتب بود حتما برای من پیام خصوصی کنید به اسم شما طرح و پاسخ داده میشود
اینجا میخوام هر روز که بیام یه سری سوال ساختمان داده ها با حلشون رو بزارم.این کارو از دیر باز دوست داشتم انجام بدم.
شاید بعضی از سوالات تکراری باشن یا پاسخ هایی که من بهشون میدم درست و کامل نباشن.هیچ کس اینجا جز حل سوال خواهشان چیزی نذاره.
این اتفاق در تلگرامم افتاده بود که به هیچ وجه برای من قابل قبول نبود و کلا نمیتونستم باهاش ارتباط برقرار کنم و تصمیم گرفتم این جا برقرارش کنم.

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

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

هر سوال حداکثر پس از سه روز پاسخ داده میشه تا فرصت برای فکر کردن دوستان هم فراهم بشه.روند سوال ها از ساده به مشکل هست.

خواهشا یا پاسخ ها کامل باشد(تمام توضیحات در مورد یک پاسخ داده شود) با توجه به هدف اصلی این پست. یا در صورت عدم کامل بودن من از شما کاربران محترمِ پاسخگو درخواست حذف پاسخ رو میدم و شما با من همراهی کنید.باز هم سپاس.

با آرزوی موفقیت برای همه دوستان عزیز

سر فصل اول
(ادغام دنباله های مرتب) :

سوال اول از ۶۰۰ مساله {به مرتب بودن دقت شود)

m لیست پیوندی مرتب با مجموعه n عنصر داده شده است و تعداد عناصر هر دنباله مشخص نیست.کدام یک از گزینه های زیر مرتبه ی سریع ترین الگوریتم برای ادغام این دنباله هاست ؟

۱) n logm
۲) nm
۳) n+m
۴) n logn
نقل قول این ارسال در یک پاسخ

۵
ارسال:
  

Saman پاسخ داده:

RE: حل سوالات ساختمان داده (۶۰۰ مساله،و تست های مهم)

ارسال های بالا کمی بهم ریخته هست، به زودی به کمک تیم مدیریت درست میکنم
دلیل اصلی این بهم ریختگی این بود که من نت رو جز در گوشی نداشتم و نمیتونستم ادامه دهم و خواستم کلا موضوع رو ببندم.
الان شرایط مساعده خداروشکر،و البته دلیل مهم تر در نیمه تمام ماندن بحث بالا این هستش که سوالات اون بخش کاملا با بخش درخت و مرتب سازی ادغام شده که معمولا در انتهای کتاب ساختمان داده به اون پرداخته میشه

موضوع بحث را در اولین فرصت،با رابطه های بازگشتی ادامه میدهیم

سر فصل دوم(روابط بازگشتی)
سوال اول (از کتاب ۶۰۰ مساله)
کدام یک از گزینه های زیر بهترین پاسخ برای رابطه ی بازگشتی [tex]T(n)=T(\frac{n}{4})+T(\frac{3n}{4})+n^2\: ,\: T(1)=1[/tex]
است ؟
۱)[tex]\theta(nlogn)[/tex]
۲)[tex]\theta(n^2logn)[/tex]
۳)[tex]\theta(n^3)[/tex]
۴)[tex]\theta(n^2)[/tex]
نقل قول این ارسال در یک پاسخ

۵
ارسال:
  

Saman پاسخ داده:

RE: حل سوالات ساختمان داده (۶۰۰ مساله،و تست های مهم)

سوال سوم ۶۰۰ مساله (سراسری ۸۶)
رابطه های بازگشتی زیر برای اعداد صحیح [tex]n>2[/tex] تعریف شده اند و داریم [tex]T(0)=T(1)=1[/tex] کدام یک از این رابطه ها، پاسخ چند جمله ای ندارد؟
۱)[tex]T(n)=2T(n-2)+1[/tex]
۲)[tex]T(n)=T(\lfloor\frac{7n}{8}\rfloor)+\: 8n\: +1[/tex]
۳)[tex]T(n)=3T(\lfloor\frac{n}{2}\rfloor)+\: n^2[/tex]
۴)[tex]T(n)=T(n-1)\: +\: n^2[/tex]
نقل قول این ارسال در یک پاسخ

۴
ارسال:
  

Saman پاسخ داده:

RE: حل سوالات ساختمان داده (۶۰۰ مساله،و تست های مهم)

پاسخ سوال دوم(*)

با توجه به تشریح سوال داریم: تعداد لیست های موجود kتا است که هر کدام [tex]\frac{n}{k}[/tex] عنصر دارند. پس تعداد لیست های موجود برابر است با : [tex](\frac{n}{k})^k[/tex]

حال برای ادغام این لیست ها هر کدام از این لیست ها میتوانند با هم ترکیب شوند که داریم : [tex](\frac{n}{k})\: !\: ^k[/tex] در کل تعداد حالات برابر است با :

[tex]\frac{n!}{(\frac{n}{k})!^k}[/tex]

با توجه به ایده ی موجود در سوال قبلی برای پیمودن درختی(با توجه به مرتب بودن عناصر میشود با حذف بزرگترین عناصر هر لیست از آن ها یک هرم بیشینه ساخت و پس از آن پا پیمودن این درخت عناصر بعدی را اضافه نمود که با توجه به ارتفاع درخت مرتبه ای لگاریتمی داریم) با ساختار ذکر شده تعداد حالات موجود یا رسیدن به هر برگ هزینه ای برابر با ارتفاع آن درخت دارد که معادل است با :
[tex]\log(\frac{n!}{(\frac{n}{k})!^k})[/tex] و چون کران پایین خواسته شده. داریم :

[tex]\Omega(\log\frac{n!}{(\frac{n}{k})!^k})[/tex]

از تقریب استرلینگ که معادل است با : [tex]\log n!\approx n\: \log n[/tex] و ساده سازی روابط لگاریتمی داریم :
[tex]\Omega(nlogn-k(\frac{n}{k})\times\log(\frac{n}{k}))=(nlogn-nlogn+nlogk)=\Omega(nlogk)[/tex]

گزینه ی ۲ صحیح است
نکته (کتاب نارنجی پوران){برای کمک به حل سوال} : اگر تعداد راه های مختلف ادغام k لیست مرتب n/k ام عنصری و تولید یک لیست مرتب n عنصری خواسته شود داریم :
تعداد n عنصر دارای [tex]n![/tex] جایگشت ولی عناصر هر لیست n/k ام عنصری دارای [tex](\frac{n}{k})![/tex] جایگشت هستند که غیر مجاز است.یعنی نباید عناصر یک لیست جا به جا شوند.چرا؟؟؟ ( چون لیست ها هر کدام مرتب هستند و جابه جایی عناصر این ترتیب را به هم میریزد).و در نهایت چون k jh لیست مرتب وجود دارد. پس تعداد راه های ادغام برابر است با : [tex]\frac{n!}{((\frac{n}{k})!)^k}[/tex]


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

میخواهیم k لیست مرتب هر کدام با [tex]\frac{n}{k}[/tex] عنصر را در هم ادغام کنیم و یک لیست مرتب nتایی ایجاد نماییم.برای این کار ابتدا لیست ۱ را با لیست ۲ ادغام میکنیم،سپس لیست حاصل را با لیست ۳ و . . . در پایان لیست حاصل را با لیست kام ادغام میکنیم.زمان اجرای این الگوریتم در بدترین حالت بر حسب n و k چقدر است ؟
۱) [tex]O(n)[/tex]
۲) [tex]O(nk)[/tex]
۳) [tex]O(nlogk)[/tex]
۴) [tex]O(klogk)[/tex]
نقل قول این ارسال در یک پاسخ

۴
ارسال:
  

Pure Liveliness پاسخ داده:

RE: حل سوالات ساختمان داده (۶۰۰ مساله،و تست های مهم)

سوال۱ ۶۰۰مساله
من تا آخر تیر درگیر هستم و از اون به بعد میتونم فعال تر باشم.

راه حل های مختلف برای به دست آوردن مرتبه ی این روابط هست. اما فرمش شبیه قضیه ی اصلی یا معادله ی همگن و ناهمگن نیست، از تکرار و جایگزینی میتونیم استفاده کنیم و درخت بازگشت. در درخت بازگشت، [tex]t(n)[/tex] از جمع چند تا [tex]t(\frac{n}{a})[/tex] ساخته شده به علاوه ی هزینه ی [tex]t(n)[/tex]، همین طور اون [tex]t(\frac{n}{a})[/tex] هم از جمع توابعی به اون صورت ساخته شده، این شاخه ها رو رسم میکنیم و در هر سطح هزینه رو مینویسیم، هزینه به ازای [tex]t(n)[/tex] برابر با [tex]n^2[/tex] هست، پس به ازای [tex]t(\frac{n}{a})[/tex] میشه [tex](\frac{n}{a})^2[/tex]. معمولا دو تا اتفاق میفته، یا هزینه ی تمامی سطوح برابر با هم هستند و در نتیجه به تعداد سطوح(ارتفاع درخت) اون هزینه رو داریم و حاصل میشه ارتفاع*هزینه ی یک سطر. یا مثل این سوال هزینه ی سطوح یک دنباله ی هندسی رو تشکیل میدهند که جمع میکنیم با هم این هزینه ها رو.

نکته ی ۱: این سوال رو از اون راه حل [tex]\sum\frac{1}{ai}[/tex] نمیتونیم بریم. چون هزینه ی ریشه در درخت، یا در واقع هزینه ی تابع به ازای k=n برابر با n نیست در این جا..
نکته ی ۲: چون در هر سطح هزینه ی متفاوتی به دست میاد پس نباید از این راه بریم که هزینه ی یک سطر رو در ارتفاع ضرب کنیم، هزینه ی تمامی سطوح رو با هم جمع میکنیم.
نکته ی ۳: جمع این هزینه ها، باید تعدادش اندازه ی ارتفاع درخت باشه، یعنی حد بالای [tex]\sum[/tex] میشه همون ارتفاع درخت.
حل: هزینه های سطوح از ریشه تا برگ رو با هم جمع میکنیم:
[tex]n^2+n^2\times(\frac{10}{16})+n^2\times(\frac{10}{16})^2+....=n^2\times\sum(\frac​{10}{16})^i=n^2\times\frac{1}{1-\frac{10}{16}}=\theta(n^2)[/tex]
البته همونطور که گفتم i از ۰ شروع میشه تا ارتفاع درخت. (بزرگترین ارتفاع رو در نظر میگیریم، در این جا logn(در مبنای۳/۴) ارتفاع هست.)

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

۳
ارسال:
  

Saman پاسخ داده:

RE: حل سوالات ساختمان داده (۶۰۰ مساله،و تست های مهم)

پاسخ سوال سوم
====
بررسی مباحث به کار رفته در این سوال :
قانون جایگذاری در روابط بازگشتی : هر بار مقدار داخلی [tex]T(n)[/tex] را در رابطه قرار میدهیم تا به یک حالت کلی برسیم.
یا از نکته ی زیر استفاده کنیم :
نکته : اگر [tex]T(n)=a\: .\: T(n-b)+c\: [/tex] که a و b و c ثابت هستند آنگاه اگر [tex]a\: \ne\: 1[/tex] داریم :
[tex]T(n)\: =\theta(a^{\frac{n}{b}})[/tex]
و اگر [tex]a=1\: ,\: c\ne\: 0\: [/tex] آنگاه :
[tex]T(n)=\theta(n)\: [/tex]
با توجه به نکته ی بالا گزینه ی اول بررسی میشود.و میتوان گفت از مرتبه ی [tex]T(n)=\theta(n^{\frac{n}{2}})\: [/tex] می باشد پس مرتبه چند جمله ای ندارد
قضیه مستر : با فرض [tex]a\ge1\: ,\: b>1\: [/tex] با توجه به رابطه بازگشتی [tex]T(n)=a\: T(\frac{n}{b})+f(n)[/tex] که [tex]\frac{n}{b}[/tex] می تواند به شکل سقف یا کف یا [tex]\frac{n}{b}\pm C\: [/tex] باشد(دقت شود).برای یافتن [tex]T(n)[/tex] داریم :
۱) اگر [tex]f(n)=O(n^{Log\: \alpha-\epsilon})[/tex] که [tex]\epsilon>0\: [/tex] ثابت است ، آنگاه [tex]T(n)=\theta(n^{\log^a_b})[/tex]

۲) اگر [tex]f(n)=\theta(n^{\log_b^a})[/tex] آنگاه : [tex]T(n)=\theta(f(n)\: .\: \log n)=\theta(n^{\log_b^a}\: .\: \log\: n)[/tex]

۳) اگر [tex]f(n)=\Omega\: (n^{\log_b^{a+\epsilon}})[/tex] که [tex]\epsilon>0[/tex] ثابت است و اگر [tex]a\: f(\frac{n}{b})\le Cf(n)[/tex] برای ثابت [tex]C<1[/tex] و n های به اندازه ی کافی بزرگ آنگاه : [tex]T(n)=\theta(f(n))[/tex]

طبف نکات بیان شده گزینه های ۲ و ۳ به ترتیب از مرتبه های : [tex]\theta(n)[/tex] و [tex]\theta(n^2)[/tex] هستند.(در ادامه سوالاتی که با مستر قابل حل نخواهند بود و دلایل حل نشدن آنها شرح داده خواهد شد).
همچنین برای گزینه ی چهارم میشود بنا بر روش جایگذاری و تکرار با شرط اولیه ی [tex]T(1)=1[/tex] به [tex]\sum^n_{i=1}i^2[/tex] رسید.که از مرتبه ی [tex]\theta(n^3)[/tex] است.
نکته : در حالت کلی داریم : [tex]\sum^n_{i=1}i^k=\theta(n^{k+1})[/tex]
پاسخ گزینه ی ۱
نقل قول این ارسال در یک پاسخ

۳
ارسال:
  

Saman پاسخ داده:

RE: حل سوالات ساختمان داده (۶۰۰ مساله،و تست های مهم)

سوال چهارم (کتاب نارنجی پوران)
رفتار مجانبی تابع [tex]T(n)[/tex] با توجه به رابطه ی بازگشتی [tex]T(2)=2[/tex] , [tex]T(1)=1[/tex] و [tex]T(n)=T(\frac{n}{2})+T(\lfloor\sqrt{n}\rfloor)+n[/tex] کدام است ؟ می توانید n را توانی از ۲ فرض کنید ؟

۱)[tex]O(n.\log n)[/tex]
۲)[tex]O(n)[/tex]
۳)[tex]O(\log^2n)[/tex]
۴)[tex]O(n\sqrt{n})[/tex]
نقل قول این ارسال در یک پاسخ

۲
ارسال:
  

Saman پاسخ داده:

RE: حل سوالات ساختمان داده (۶۰۰ مساله،و تست های مهم)

پاسخ سوال چهارم(*)
اگر به جای [tex]T(\lfloor\sqrt{n}\rfloor)\: [/tex] قرار دهیم [tex]T(\frac{n}{2})\: [/tex] مرتبه ی این تابع طبق مستر [tex]T(n.\log n)\: [/tex] میشود.
اما چون [tex]\sqrt{n}[/tex] از [tex]\frac{n}{2}[/tex] برای [tex]n\ge2[/tex] بزرگتر نیست پس حتما از مرتبه ی [tex]T(n)=O(n.\log n)[/tex] هست ولی امکان دارد این مرتبه کمتر از این باشد!
با صرف نظر از [tex]T(\sqrt{n})[/tex] در مقابل [tex]T(\frac{n}{2})[/tex] پاسخ [tex]O(n)[/tex] است که با جایگذاری اثبات میکنیم.(دقت کنید که باید حدس ما اثبات شود چرا که یکی از گزینه ها میتواند مرتبه ای کمتر از [tex]O(n)[/tex] نیز داشته باشد به [tex]O(\log n)\: ,\: O(\log\log n)[/tex] در مقابل [tex]O(n)[/tex] فکر کنید)
در نهایت باید نشان دهیم:
[tex]T(n)\le Cn[/tex] حال داریم :
[tex]T(n)=T(\frac{n}{2})+T(\sqrt{n})+n\le C\frac{n}{2}+C\sqrt{n}+n[/tex]
که به ازای C=4 داریم :
[tex]4\frac{n}{2}+4\sqrt{n}+n=3n+4\sqrt{n}\le4n[/tex]
=======
با توجه به سوال بالا به سوال زیر فکر کنید و مرتبه ی زمانی آن را بیابید؟!
(MIT یا تمرینات CLRS)

[tex]T(n)=T(\frac{n}{2}+\sqrt{n})+\sqrt{6046}[/tex]

سوال پنجم (*){MIT سال ۲۰۰۵ و سوال ۱۷ پوران نارنجی}
با توجه به رابطه ی [tex]T(n)=T(\frac{n}{3})+T(\frac{n}{6})+\theta(n^{\sqrt{\log n}})[/tex] داریم :
۱) [tex]T(n)=\theta(\log n.n^{\sqrt{\log n}})[/tex]
۲) [tex]T(n)=\theta(n^{\sqrt{\log n}})[/tex]
۳) [tex]T(n)=\theta(n^{\log n})[/tex]
۴) [tex]T(n)=\theta(\sqrt{n}^{\log n})[/tex]
نقل قول این ارسال در یک پاسخ

ارسال:
  

sahabi2015 پاسخ داده:

RE: حل سوالات ساختمان داده و طراحی الگوریتم(۶۰۰ مساله،و تست های مهم)

پاسخ سوال ۴ )

این سوال با روش های مختلفی قابل حل است . اما روشی که شهود بیشتری میدهد روش درختی ست .

می دانیم برای n های بزرگتر از یک سرعت به مقدار ثابت رسیدن [tex]T(\sqrt{n})[/tex] در برابر [tex]T(\frac{n}{2})[/tex]
بسیار بیشتر میباشد .

مثلا برای n=1000 داریم :

[tex]T(\frac{n}{2})=T(\frac{1000}{2})=500,250,125,62.5,31.25,15.125,7.5,3.75,1.75[/tex]

[tex]T(\sqrt{n})=T(\sqrt{1000})=31.62,5.62,2.37,1.53[/tex]

در نتیجه ارتفاع درخت را [tex]T(\frac{n}{2})[/tex]
مشخص میکند که طول بیشتری دارد .

پس می توان در این رابطه از [tex]T(\sqrt{n})[/tex] صرف نظر کرد:
[tex]T(n)=T(\frac{n}{2})+n[/tex]

که با توجه به قضیه مستر مرتبه این رابطه [tex]\theta(n)[/tex] می باشد.[/align][/size]
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۲
ارسال: #۱۰
  

Saman پاسخ داده:

RE: حل سوالات ساختمان داده (۶۰۰ مساله،و تست های مهم)

پاسخ سوال پنجم(*)
نکته : دقت کنید که رشد تابعی که نمایی میشود(مثلا [tex]n[/tex] توان باشد) از رشد تمام چند جمله ای ها بیشتر است.
با حدس و استقرا و به ازای [tex]C=2[/tex] می توان ثابت کرد که روابط زیر برقرار هستند :
[tex]T(n)=T(\frac{n}{3})+T(\frac{n}{6})+\theta(n^{\sqrt{\log n}})\le2T(\frac{n}{3})+\theta(n^{\sqrt{\log n}})\: =\theta(n^{\sqrt{\log n}})[/tex]
و
[tex]T(n)=T(\frac{n}{3})+T(\frac{n}{6})+\theta(n^{\sqrt{\log n}})\ge2T(\frac{n}{6})+\theta(n^{\sqrt{\log n}})\: =\theta(n^{\sqrt{\log n}})[/tex]

با توجه به دو نامساوی فوق میتوان در یافت که مرتبه ی زمانی برابر است با [tex]T(n)\: =\theta(n^{\sqrt{\log n}})[/tex]، در واقع ما ثابت کردیم که این تابع هم از مرتبه ی [tex]T(n)\: =O(n^{\sqrt{\log n}})[/tex] و هم از مرتبه ی [tex]T(n)\: =\Omega(n^{\sqrt{\log n}})[/tex] است.

این پاسخ در حل المسائل انگلیسی هم موجود است!
پاسخ گزینه ی ۲
نقل قول این ارسال در یک پاسخ

۲
ارسال: #۱۱
  

Saman پاسخ داده:

RE: حل سوالات ساختمان داده (۶۰۰ مساله،و تست های مهم)

پاسخ فکر کنید:
دو روش برای پاسخ وجود دارد :
شرح روش کلی با استفاده از یک فرض در مثالی که به راحتی با قضیه مستر قاب حل است.
در رابطه ی [tex]T(n)=T(\frac{n}{2})+T(\frac{n}{2})\ +1\equiv T(n)=2T(\frac{n}{2})+1[/tex] ، این تابع همان طور که میدانید با مستر ثابت میشود که از مرتبه ی [tex]O(n)[/tex] است.
میدانیم که مقدار [tex]T(n)=T(\frac{n}{2})+T(\frac{n}{2})\ +1\equiv T(n)=2T(\frac{n}{2})+1[/tex] از مقدار [tex]T(n)=T(\frac{n}{2}+\sqrt{n})+\sqrt{6046}[/tex] بیشتر است . پس باید مقدار [tex]O(n)[/tex] را بهینه تر کنیم.
میتوان فرض کرد که مرتبه ی زمانی تابه ما [tex]O(\log n)[/tex] است، این فرض را با قرار دادن تابع اصلی در بین دو تابع دیگر میتوان به شکل زیر اثبات کرد، داریم :
[tex]T(\frac{n}{2})\le T(\frac{n}{2}+\sqrt{n})\le T(\frac{3n}{4})[/tex] ، با توجه به برقرار بودن این شرایط که در حالت اوی بزرگ به صورت مقابل است : [tex]O(\log_{\frac{4}{3}}n)[/tex] ، میتوان گفت که مرتبه ی این تابع [tex]O(\log n)[/tex] می باشد.
یک روش دیگر هم استفاده از این هم عرضی است که مقدار [tex]\sqrt{n}[/tex] را در مقابل [tex]T(\frac{n}{2})[/tex] نادیده بگیریم که به شکل زیر میشود :
[tex]T(n)=T(\frac{n}{2}+\sqrt{n})+\sqrt{6046} \simeq T(\frac{n}{2})+\theta(1) = \theta(\log n)[/tex]
دقت کنید مقدار [tex]\ sqrt{6046}[/tex] یک ثابت و از مرتبه ی تتا ۱ است.
بنابرین تابع مورد نظر از مرتبه ی [tex]\theta(\log n)[/tex] میباشد.
نقل قول این ارسال در یک پاسخ

۲
ارسال: #۱۲
  

Saman پاسخ داده:

RE: حل سوالات ساختمان داده (۶۰۰ مساله،و تست های مهم)

سوال ششم (*) {سوال ۱۳-۱ از ۶۰۰ سوال}
حل رابطه بازگشتی [tex]\: T(n)=\frac{1}{n}\sum_{i=1}^{n-1}T(i)+3n[/tex] و [tex]\: T(1)=1[/tex] برابر است با :

۱) [tex]O(\log n)[/tex]

۲)[tex]O(n)[/tex]

۳)[tex]O(n\: logn)[/tex]

۴)[tex]O(n^2)[/tex]
نقل قول این ارسال در یک پاسخ

۲
ارسال: #۱۳
  

Pure Liveliness پاسخ داده:

RE: حل سوالات ساختمان داده (۶۰۰ مساله،و تست های مهم)

سوال ششم (*) {سوال ۱۳-۱ از ۶۰۰ سوال}
سلام.
راه حل اول:
*روابط بازگشتی که تووش [tex]T(n)[/tex] به صورت جمع یک سری به علاوه ی یک هزینه ی اولیه به ازای n نوشته شده که در این جا هزینه به ازای [tex]T(K=n)[/tex] برابر با ۳n هست رو میایم معمولاََ اون رابطه رو به ازای [tex]T(K=n-۱)[/tex] مینویسیم تا به یه رابطه ای بین این دو تا یعنی [tex]T(n-۱)[/tex] و [tex]T(n)[/tex] برسیم و از شر اون سری خلاص بشیم.
توی این جا [tex]T(n)[/tex]:
[tex]T(n)=\frac{1}{n}\Sigma\: T(i)\: +\: 3n[/tex] که i از ۱ تا n-1 هست.
و [tex]T(n-1)[/tex]:
[tex]T(n-1)=\frac{1}{n-1}\Sigma\: T(i)\: +\: 3(n-1)[/tex] و i از ۱ تا n-2 هست.

خب واسه این که یه کم ساده تر بشه و بتونیم تفاوت این دو تا عبارت رو ببینیم به شکل بازتری مینویسیم:
[tex]T(n)=\frac{1}{n}(T(1)+T(2)+T(3)+...+T(n-3)+T(n-2)+T(n-1))\: +\: 3n[/tex]
[tex]T(n-1)=\frac{1}{n-1}(T(1)+T(2)+T(3)+...+T(n-3)+T(n-2))\: +\: 3n-3[/tex]

حالا چون که توی اینجا یه کمی اون n و n-1 اذیت میکنه پس [tex]T(n-1)[/tex] رو در [tex]\frac{(n-1)}{n}[/tex] ضرب میکنیم تا شبیه [tex]T(n)[/tex] بشه و حالا داریم:
[tex]\frac{(n-1)}{n}T(n-1)=\frac{1}{n}(T(1)+T(2)+T(3)+...+T(n-3)+T(n-2))\: +\frac{\: 3(n-1)^2}{n}[/tex]
الان از [tex]T(n)[/tex] میایم این [tex]\frac{(n-1)}{n}T(n-1)[/tex] رو کم میکنیم، پس:
[tex]T(n)-\: \frac{(n-1)}{n}T(n-1)=\frac{\: 1}{n}(T(1)+....T(n-2)+T(n-1))+3n\: -\frac{1}{n}(T(1)+...+T(n-2))-\frac{3(n-1)^2}{n\: }\: =\: [/tex]
[tex]T(n)-\: \frac{(n-1)}{n}T(n-1)=\frac{\: 1}{n}T(n-1)+3n-\frac{3(n-1)^2}{n\: }\: =[/tex]
[tex]T(n)=\: \frac{(n-1)}{n}T(n-1)+\frac{\: 1}{n}T(n-1)+3n-\frac{3(n-1)^2}{n\: }\: =[/tex]
[tex]T(n)=\: \frac{(n-1+1)}{n}T(n-1)+3n-\frac{3(n-1)^2}{n\: }\: =[/tex]
[tex]T(n)=\: T(n-1)+3n-\frac{3(n-1)^2}{n\: }\: =[/tex]
[tex]T(n)=\: T(n-1)+\frac{3n^2\: -\: 3(n-1)^2}{n\: }\: =[/tex]
[tex]T(n)=\: T(n-1)+\theta(1)[/tex]
که این رابطه [tex]\theta(n)[/tex] هست چون n بار فراخوانی داره.

راه حل دوم:
روش استقرا :
مبنای استقرا:[tex]T(1)[/tex] از an+b کوچکتر است.
فرض استقرا: برای n=k نیز همین را داریم و [tex]T(k)[/tex]نیز از an+b کوچکتر است.
مرحله ی استقرا: نشان می دهیم که این مساله برای k+1 نیز صحیح است، در نتیجه میتوان گفت برای n صحیح است.
چرا گفتیم از an+b کوچیکتر باشه؟ حدس میزنم چون که هزینه به ازای [tex]T(n)[/tex] برابر با ۳n هست، خب برای هر [tex]T(k)[/tex]ای هم قطعا از [tex]\theta(n)[/tex] بزرگتر نیست و در نتیجه : [tex]\forall\: k\: \: \: T(k)\le an+b[/tex]
(البته ما مراحل استقرا رو دنبال نکردیم ولی با سطر بالا اثبات شد.)
خب الان میتونیم این طوری بنویسیم:
[tex]T(n)\le\frac{\: 1}{n}\Sigma(an+b)+3n[/tex] که اون سری معادل هست با n-1 تا .an+b. چون به تعداد n-1 تاست از i=1 تا i=n-1
الان [tex]T(n)\le\frac{\: 1}{n}\Sigma(an+b)+3n=\frac{\: 1}{n}((n-1)(an+b))+3n[/tex]
[tex]T(n)\le\frac{\: 1}{n}\Sigma(an+b)+3n=\frac{\: 1}{n}((n-1)(an+b))+3n=\frac{1}{n}(an(n-1)+b(n-1))+3n[/tex]
[tex]T(n)\le\frac{\: 1}{n}\Sigma(an+b)+3n=\frac{\: 1}{n}((n-1)(an+b))+3n=\frac{1}{n}(an(n-1)+b(n-1))+3n=a(n-1)+\frac{b(n-1)}{n}+3n=\: (a+3)n\: +b\cdot teta(1)-a\: =\: a.n+b[/tex]
حالا چون [tex]T(n)[/tex] هم از an+b کوچیکتر شد پس از مرتبه ی [tex]\theta(n)[/tex] هست.
نقل قول این ارسال در یک پاسخ

۲
ارسال: #۱۴
  

Saman پاسخ داده:

RE: حل سوالات ساختمان داده و طراحی الگوریتم(۶۰۰ مساله،و تست های مهم)

پاسخ سوال دهم

برای شرط [tex]i^2\le\: N[/tex] میتوان گفت که چون i با سرعت بیشتری به N می رسد پس از مرتبه ی N نخواهد بود(در کتاب ۶۰۰ گزینه ها متفاوت از کتاب نارنجی هستند و مرتبه ی [tex]O(N)[/tex] نیز مطرح است ) یا میتوان گفت از طرفین رابطه [tex]i^2\le\: N[/tex] رادیکال میگیریم و البته با در نظر گرفتن این موضوع که i هر بار ۲ واحد اضافه میشود. که به دست می آید :
[tex]\frac{\sqrt{N}}{2}[/tex]
بنابراین مرتبه ی کد : [tex]O(\sqrt{N})[/tex] است.
نقل قول این ارسال در یک پاسخ

۲
ارسال: #۱۵
  

Saman پاسخ داده:

RE: حل سوالات ساختمان داده و طراحی الگوریتم(۶۰۰ مساله،و تست های مهم)

پاسخ سوال یازدهم

حلقه ی بیرونی [tex]\log n[/tex] بار تکرار میشود و حلقه ی درونی [tex]\log i[/tex] چون در حلقه ی درونی i را داخل j قرار میدهیم.

سوال سیزدهم(*) سوال ۷۸-۱ از ۶۰۰
چند تا از گزاره های زیر درست است؟[
۱) تفاوت زمان اجرای هر الگوریتم قطعی در بدترین حالت و حالت میانگین تنها در ضریب ثابتشان است

۲)تابع های [tex]f(n)[/tex] و [tex]g(n)[/tex] وجود دارند به طوری که [tex]f(n)=O(g(n))[/tex] و [tex]f(n)=\omega(g(n))[/tex]

۳) اگر [tex]f(n)=\sqrt{n}[/tex] و [tex]g(n)=n.(n\: \mod\: 100)[/tex] در آن صورت [tex]f(n)=O(g(n))[/tex]


۱)۰
۲)۱
۳)۲
۴)۳


سوال چهاردهم (سوال ۱۳ فصل اول کتاب نارنجی)

فرض کنید آرایه [tex]A[1...n]\: [/tex] یا همه ی عناصرش صفر است یا [tex]\frac{n}{2}[/tex] صفر و [tex]\frac{n}{2}[/tex] یک، اگر بخواهیم با احتمال حداقل [tex]\frac{3}{4}[/tex] مشخص کنیم آرایه A کدام نوع است . باید چند درایه از A بخوانیم و بررسی کنیم؟

۱)[tex]\frac{n}{2}+1[/tex]
۲)[tex]\frac{n}{4}+1[/tex]
۳)۲
۴)۴

سوال چهاردهم پایان مبحث فصل اول(روابط بازگشتی)

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

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

۱
ارسال: #۱۶
  

Saman پاسخ داده:

RE: حل سوالات ساختمان داده (۶۰۰ مساله،و تست های مهم)

سوال هفتم (*){سوال ۱۳ کتاب نارنجی} "بسیار مهم" [ این سوال مصداقی از سوالات ۶/۱ و ۱۸/۱ در ۶۰۰ مساله و چندین دوره از سوالات سراسری میباشد]

فرض کنید [tex]T(n)\: =\sum^k_{i=1}a_i.T(\frac{n}{b_i})+cn\: [/tex] که [tex]a_i[/tex] ها و [tex]b_i[/tex] ها ثابت هستند و [tex]1-\sum^k_{i=1}\frac{a_i}{b_i}>0[/tex] آنگاه :

۱) [tex]T(n)=O(n)[/tex]

۲)[tex]T(n)=O(n.\log n)[/tex]

۳)[tex]T(n)=O(\log n)[/tex]

۴)[tex]T(n)=O(n^2)[/tex]
نقل قول این ارسال در یک پاسخ

۱
ارسال: #۱۷
  

Pure Liveliness پاسخ داده:

RE: حل سوالات ساختمان داده و طراحی الگوریتم(۶۰۰ مساله،و تست های مهم)

سوال هفتم (*) {سوال ۱۳-۲ از نارنجی پوران}

راه حل اول:

توی صورت سوال نوشته شده که : [tex]1-\sum_{i=1}^k\frac{ai}{bi\: }>\: 0[/tex]
که یعنی: [tex]1>\: \sum^k_{i=1}\frac{ai}{bi}[/tex]
خب یه قضیه ای داشتیم که این بود:
برای رابطه ی : [tex]T(n)=\sum^k_{i=1}T(\frac{n}{ai})+\theta(n)[/tex]
اگر : [tex]\sum_{i=1}^{k\: }\frac{1}{ai}\: <1[/tex] آنگاه [tex]T(n)=O(n)[/tex]
اگر :[tex]\sum_{i=1}^{k\: }\frac{1}{ai}\: =1[/tex] آنگاه [tex]T(n)=O(nlogn)[/tex]
حالا این جا هم درست شبیه همون قضیه هست، b و a دو تا ثابت هستند، تابع [tex]T(n)[/tex] به صورت جمع تعدادی [tex]ai\: T(\frac{n}{bi})[/tex] هست که اینجا [tex]1>\: \sum^k_{i=1}\frac{ai}{bi}[/tex]
اگر تمامی ai ها برابر با ۱ باشه که درست میشه همون قضیه ی بالا و با توجه به این که [tex]\sum_{i=1}^k\frac{ai}{bi}=\sum^k_{i=1}\frac{1}{bi}<1[/tex] پس [tex]T(n)=\theta(n)[/tex]
در غیر اینطورت یعنی اگر ai ها برابر با ۱ نباشند چطور؟
فرض کنیم k=3 باشه مثلاََ.
خب حالا رابطه به این فرم میشه:
[tex]T(n)=\sum^3_{i=1}ai.\: T(\frac{n}{bi})+cn[/tex]
[tex]T(n)=a1.T(\frac{n}{b1})+a2.T(\frac{n}{b2})+a3.T(\frac{n}{b3})+cn[/tex]
خب اعدادی برای b1,b2,b3 و a1,a2,a3 بگذاریم که شرط [tex]1>\: \sum^k_{i=1}\frac{ai}{bi}[/tex] برقرار باشه، این رابطه رو به صورت درخت بازگشت حل کنیم حتما جمع هزینه ها ی هر سطر برابر میشه جمع جمله های یک سری هندسی با قدرنسبت کوچکتر از ۱، در نتیجه تابع از مرتبه ی [tex]O(n)[/tex] میشه.
پس تابع از مرتبه [tex]O(n)[/tex] هست.

راه حل دوم:
(تستی)
k که هر چیزی میتونه باشه، ۱ در نظر میگیریمش.
حالا داریم: [tex]T(n)=\: a1.T(\frac{n}{b1})+cn\: [/tex]
از طرفی طبق صورت سوال داریم :[tex]\sum_{i=1}^k\frac{ai}{bi}<1[/tex] و این یعنی [tex]\frac{a1}{b1}<1[/tex]
حالا مرتبه رو میخوایم با قضیه ی اصلی (master) به دست بیاریم. [tex]f(n)[/tex] رو با [tex]n^{\log^{a1}_{b1}}[/tex] مقایسه میکنیم. با توجه به این که[tex]\frac{a1}{b1}<1[/tex] ، پس : [tex]n^{\log^{a1}_{b1}}<\: n^1[/tex] و این یعنی [tex]T(n)=\theta(f(n))=\theta(n)[/tex]

راه حل سوم:
(تستی)
در نظر می گیریم که k یک نیست ولی [tex]b_i[/tex] بینهایت هست یا [tex]a_i[/tex] صفر هست (یا هر دو همزمان)، که این با توجه به شرایط صورت مساله یعنی[tex]\sum_{i=1}^k\frac{ai}{bi}<1[/tex]هم درست هست، حالا [tex]a_iT(\frac{n}{b_i})[/tex] برابر با صفر میشه و تنها چیزی که از [tex]^{ }T(n)=\sum^k_{i=1}a_i.T(\frac{n}{b_1})+cn[/tex] میمونه [tex]^{ }T(n)=cn[/tex] هست، در نتیجه [tex]^{ }T(n)=O(n)[/tex]
نقل قول این ارسال در یک پاسخ

۱
ارسال: #۱۸
  

Saman پاسخ داده:

RE: حل سوالات ساختمان داده و طراحی الگوریتم(۶۰۰ مساله،و تست های مهم)

ضمن سپاس از پاسخ کاربر Pure Liveliness :
=====
بنابر "بسیار مهم" بودن سوال هفتم و البته با توجه به این که در دوره های متوالی و در کتاب های متعددی این سوال و سوالات بسیار نزدیک با منطق این سوال مورد بررسی قرار گرفته پاسخ چهارمی با منطقِ آنچه که کاربر Pure Liveliness ارائه داد در این جا خدمت دوستان دنبال کننده میگذارم :
راه حل چهارم سوال هفتم

فرض میکنیم تمام [tex]a_i[/tex] ها برابر باشند داریم :
[tex]T(n)=T(\frac{n}{a})+T(\frac{n}{a})+.\: .\: .+T(\frac{n}{a})+\theta(n)[/tex] یعنی Kتا [tex]T(\frac{n}{a})[/tex] داشته باشیم که میشود :
[tex]T(n)=kT(\frac{n}{a})+\theta(n)[/tex] و این بیانی دیگر از سیگما هست. در صورتی که داشته باشیم :
[tex]T(n)=\sum^k_{i=1}T(\frac{n}{a_i})+\theta(n)[/tex] که کاملا منطبق هست با سوال ۱۸/۱ در ۶۰۰ مساله که پاسخ های کامل آن را میشود به صورت زیر ارائه داد.

با توجه به قضیه ی مستر حالات زیر برقرار است :

۱) [tex]T(n)=\theta(n)\: \: if\: \: k<a[/tex]

۲)[tex]T(n)=\theta(n.logn)\: \: if\: \: k=a[/tex]

۳)[tex]T(n)=\theta(n^{\log_a^k})\: \: if\: \: k>a[/tex]

حال آنچه که این سوال را از سوال ۱۸/۱ متمایز میکند شرط مقابل است [tex]1-\sum^k_{i=1}\frac{a_i}{b_i}>0[/tex]

همان گونه که مشاهده میشود علاوه بر ثابت [tex]a_i[/tex] ثابت [tex]b_i[/tex] نیز اضافه شده است. ما اگر مقدار ثابت [tex]a_i[/tex] را با مقادیر برابر ست کنیم، میشود مقادیر [tex]b_i[/tex] را متفاوت در نظر گرفت این تمایز باعث میشود شرط سوال متفاوت تر از سوالات پیشین به نظر برسد : (ضمن دقت در نکته ی زیر از پوران):

نکته : رابطه ی بازگشتی : [tex]T(n)=T(\alpha n)+T(\beta n)+n[/tex] که [tex]\alpha\: ,\: \beta[/tex] ثابت هستندمفروض است اگر [tex]\alpha+\beta=1[/tex] داریم [tex]T(n)=\theta(n.\log n)[/tex] و اگر [tex]\alpha+\beta<1[/tex] آنگاه [tex]T(n)=\theta(n)[/tex]

حال با دقت در شرط سوال و پاسخ کتاب نارنجی پوران و مثال ارائه شده در این کتاب میتوان پی برد که شرط مذکور در سوال بیانگر همان مقدار :
[tex]\alpha+\beta<1[/tex] می باشد یعنی داریم : [tex]\alpha+\beta<1\: \equiv\: \sum^k_{i=1}\frac{a_i}{b_i}<1[/tex]

حل مثال زیر با مقادیر [tex]k=2[/tex] و [tex]a_1=a_2=1\: [/tex] و [tex]b_1=5[/tex] و [tex]b_2=\frac{10}{7}[/tex] که رابطه ی بازگشتی زیر را میسازد [tex]T(n)=T(\frac{n}{5})+T(\frac{7n}{10})+cn[/tex] با درخت بازگشت اثباتی برای ادعای بالا است. که مرتبه ی سوال برابر است با :
[tex]T(n)=O(n)[/tex] و گزینه ی اول پاسخ صحیح است
نقل قول این ارسال در یک پاسخ

۱
ارسال: #۱۹
  

Saman پاسخ داده:

RE: حل سوالات ساختمان داده و طراحی الگوریتم(۶۰۰ مساله،و تست های مهم)

سوال هشتم (*) {ادغام چندین سوال از ۶۰۰ سوال و کتاب نارنجی) سوال ۳۰/۱ و سوال ۴۱/۱ و سوال ۵ و ۷ از نارنجی Smile

چه تعداد از عبارات زیر صحیح است ؟ {تشریح گزینه ها ضروریست}

۱)[tex]n\: !\: =\omega(2^n)[/tex]

۲)[tex]n\: !\: =o(n^n)[/tex]

۳)[tex]\log(n\: !)\: =\theta(n\: \log n)[/tex]

۴)[tex]n\: !=O(n^n)[/tex]

۵)[tex]3^{2^n}=\Omega(2^{3^n})[/tex]

۶)[tex]n^{2+\frac{1}{\sqrt{n}}}=O(n^2)[/tex]

۷)[tex]\sum^n_{i=1}i^k\log i=O(n^{k+1}\log^{k+1}n)[/tex]

۸)[tex]\sum^n_{i=1}\lceil\frac{1}{i}\rceil=O(n\: \log n)[/tex]


۱)۰
۲)۱
۳)۲
۴)۴


سوال نهم{سوال ۲۶ از کتاب نارنجی}

کدام عبارت صحیح است ؟
الف) [tex]\log^{\ast}(\log n)\in\omega(\log(\log^{\ast}n))[/tex]

ب ) اگر [tex]k.\ln k=\theta(n)[/tex] آن گاه [tex]k=\theta(\frac{n}{\ln n})[/tex]

پ ) [tex]\sqrt{n}\in\Omega(n^{\sin n})[/tex] یا [tex]\sqrt{n}\in O(n^{\sin n})[/tex]

۱)الف
۲)الف و پ
۳) الف و ب
۴)هر سه مورد


با ۶ تا ۱۰ سوال دیگر بخش اول به پایان میرسد، سوالات شامل ترتیب های رشد پیچیدگی تکه برنامه ها و مسائل استخراجی با ایده ی بازگشتی خواهد بودSmile
نقل قول این ارسال در یک پاسخ

۱
ارسال: #۲۰
  

Pure Liveliness پاسخ داده:

RE: حل سوالات ساختمان داده و طراحی الگوریتم(۶۰۰ مساله،و تست های مهم)

پاسخ سوال نهم (سوال ۱-۲۶ از کتاب نارنجی پوران)
در مورد گزینه ی الف:
یه فرمولی هست که [tex]\log^{\ast}(\log n)=\log^{\ast}n\: -\: 1[/tex]
این فرمول از کجا اومده؟ [tex]\log^{\ast}[/tex] هر چیزی یعنی انقدر ازش لگاریتم بگیریم که به عددی کوچکتر از یک یا یک برسه، تعدادش میشه [tex]\log^{\ast}n[/tex] که معمولا برای اعداد خیلییی بزرگ هم بیشتر از ۶ نمیشه. حالا فرض کنیم که لگاریتم یه عدد رو داریم یعنی log n تا این جا یه مرحله رو انجام دادیم، حالا میایم از این log n، [tex]\log^{\ast}[/tex]ش رو حساب میکنیم، یعنی یه دونه از مراحل [tex]\log^{\ast}n[/tex] کمتر، که میشه [tex]\log^{\ast}n\: -1[/tex]. مثال می زنم.
n=16
[tex]\log16=3[/tex] یعنی باید یه بار لگاریتم بگیریم از ۱۶ که بشه ۴، بار دوم از ۴ لگاریتم بگیریم که بشه ۲ و بار سوم از ۲ لگاریتم بگیریم در مبنای ۲ که بشه ۱، سه بار لگاریتم گرفتیم تا برسیم به ۱، این سه تا میشه [tex]\log^{\ast}۱۶[/tex]

[tex]\log^{\ast}\log16=\log^{\ast}4=2[/tex]
حالا [tex]\log^{\ast}16=3[/tex]
خب پس این فرمول قابل درک هست:[tex]\log^{\ast}(\log n)=\log^{\ast}n\: -\: 1[/tex]
توی صورت سوال داریم که [tex]\log^{\ast}(\log n)\: \in\omega(\log(\log^{\ast}n))[/tex] حالا از اونجایی که [tex]\log^{\ast}(\log n)=\log^{\ast}n\: -\: 1[/tex] و این که می دونیم رشد [tex]\log(\log^{\ast}n)[/tex] از رشد [tex]\log^{\ast}n[/tex] کمتر هست پس این گزینه کاملا درسته.

گزینه ی دو:
فرض میکنیم تالی درست باشه، یعنی واقعا [tex]k=\theta(\frac{n}{\ln n})[/tex] خب پس به جای k توی عبارت [tex]k.\ln k[/tex]، معادلش رو مینویسیم.
[tex]k.\ln k=\frac{\: n}{\ln n}.\ln(\frac{n}{\ln n})[/tex]
می دونیم که [tex]\ln(\frac{x}{y})=\ln x-\ln y[/tex] پس عبارت بالا به صورت زیر میشه:
[tex]\frac{n}{\ln n}.\ln(\frac{n}{\ln n})=\frac{n}{\ln n}.(\ln n\: -\: \ln\: \ln n)=\frac{n.\ln n}{\ln n}-\frac{\: n}{\ln n}.\ln\ln n=n-\frac{n}{\ln n}.\ln\ln n=n.(1-\frac{\ln\ln n}{\ln n})[/tex]
که می دونیم رشد [tex]\frac{\ln\ln n}{\ln n}[/tex] از ۱ کمتر هست پس عبارت بالا میشه:
[tex]\theta(n)[/tex] که خب درسته.
پس این گزینه هم درسته.

گزینه ی سوم:
کلا وقتی می تونیم مرتبه ی بزرگی دو تا تابع رو با هم مقایسه کنیم که هر کدوم یا صعودی یا نزولی باشه، یه سری از توابع هستند که تناوبی هستند و توی یه بازه هایی صعودی هستند و یه بازه هایی نزولی بعد ممکنه نشه با بعضی از توابع مقایسه بشن.
توی این مثال: خب [tex]-1\: <\: \sin\: n\: <\: 1[/tex]
وقتی [tex]-1\: <\: \sin\: n\: <\: 0[/tex] اونوقت [tex]n^{\sin n}[/tex] معادل میشه با [tex]n^k\: \: (-1<k<0)[/tex] که یعنی توان n از یک کمتر هست، پس یعنی توی این بازه ی مشخص شده [tex]\sqrt[]{n}=omega(n^{\sin n})[/tex]
اما وقتی[tex]0\: <\: \sin\: n\: <\: 1[/tex] اونوقت [tex]n^{\sin n}[/tex] معادل میشه با [tex]n^k\: \: (0<k<1)[/tex] که یعنی توان n از یک بیشتر هست، پس یعنی توی این بازه ی مشخص شده [tex]\sqrt[]{n}=O(n^{\sin n})[/tex]
اگر شکل این دو تابع رو هم بکشیم متوجه میشیم توی یه بازه ای اولی بالای دومی هست و توی بازه ی بعدی بالعکس، پس نمیشه این دو تا رو مقایسه کرد و غلط هست سوال به کل.
پس گزینه ی سه درسته یعنی الف و ب درست هستند.
نقل قول این ارسال در یک پاسخ

۱
ارسال: #۲۱
  

Saman پاسخ داده:

RE: حل سوالات ساختمان داده و طراحی الگوریتم(۶۰۰ مساله،و تست های مهم)

ضمن سپاس و در ادامه پاسخ کاربر Pure Liveliness :

۳)طبق قضیه ی استرلینگ داریم : [tex]\log(n!)\equiv n\: \log n[/tex] این هم ارزی در رشددرست بودن حالت سوم را نشان میدهد.

۴) تابع توضیحات عالی دوست عزیزمان این گزینه مانند حالت دوم قابل اثبات است

۵) باز هم به تبعیت از توضیحات کاربر Pure Liveliness :
میشود از طرفین رابطه لگاریتم گرفت : تا به حالت زیر برسیم :
[tex]2^n\log3\le3^n\log2[/tex] و نادرستی این گزینه نیز ثابت شود.

۶) میتوان گفت برای هر مقدار [tex]\epsilon[/tex] در توان افزایش قابل ملاحظه ای در پیچیدگی خواهیم داشت و در این مثال به ازای n0 که n>n0 باشد داریم : [tex]n^{2+\frac{1}{\sqrt{n}}}\ge n^2[/tex] که از مرتبه ی [tex]\Omega[/tex] خواهد بود.پس این گزینه نیز غلط است.

۷) در جستجوی پاسخ مناسب و ساده و کاربردی . . .(در حال تکمیل . . . )
نقل قول این ارسال در یک پاسخ

۱
ارسال: #۲۲
  

Pure Liveliness پاسخ داده:

RE: حل سوالات ساختمان داده و طراحی الگوریتم(۶۰۰ مساله،و تست های مهم)

پاسخ سوال هشتم (سوال ۱-۳۱ و ۱-۴۱ ۶۰۰ مساله ی دکتر قدسی و سوال ۵ و ۷ نارنجی پوران)
۱)[tex]n!=\omega(2^n)[/tex]
راه حل اول:
درست هست چون [tex]n!=n\times(n-1)\times(n-2)\times...\times3\times2\times1[/tex] که ضرب n عدد از ۱ تا n در هم هست.
[tex]2^n=\: 2\times2\times2\times....\times2[/tex] که ضرب n عدد ۲ در هم هست و مشخص هست که از ضرب ۱ تا n کمتر هست.
راه حل دوم:
لگاریتم میگیریم. [tex]\log_22^n=nlog_2^2=n[/tex] و [tex]\log_2n!=nlogn[/tex] که خب مشخص هست که nlogn از n بزرگتر هست.

۲)[tex]n!\: =\: O(n^n)[/tex]
درست هست چون طبق ۱ n! از ضرب ۱ تا n به دست میاد و [tex]n^n[/tex] از ضرب n تا n
با گرفتن log هم به همین نتیجه خواهیم رسید. گرچه همیشه این روش جواب نمیده. یعنی مثلا n با توان های مختلف رو اگه ازش log بگیریم، حاصل log هم مرتبه است ولی رشد به ازای توان های مختلف فرق داره.

۷)[tex]\sum^n_{i=1}i^k.\log k\: \in O(n^{k+1}.\log^{k+1}n)[/tex]
[tex]\sum_{i=1}^ni^k.\log i=1^k.\log1+2^k.\log2+3^k.\log3+....+n^k.\log n[/tex]
این سری تک تک جملاتش از [tex]n^k.\log n[/tex] کوچیکتر هست، از طرفی n تا جمله داریم از i=1 تا n
[tex]\sum^n_{i=1}i^k.\log k\: =1^k.\log1+....+n^k.\log n\: \le n.n^k.\log n\le n^{k+1}.\log^{k+1}n[/tex] که خب اثبات شد که [tex]\sum^n_{i=1}i^k.\log k\: \in O(n^{k+1}.\log^{k+1}n)[/tex]

۸)[tex]\sum^n_{i=1}floor(\frac{1}{i})=\theta(n)[/tex]
[tex]\sum^n_{i=1}ceil(\frac{1}{i})=ceil(\frac{1}{1})+ceil(\frac{1}{2})+ceil(\frac{1}{​3})+…+ceil(\frac{1}{n})=1+1+1+...+1=n=\theta(n)[/tex]
چون علامت سقف رو پیدا نکردم نوشتم ceil
نکته: اگر علامت براکت نبود اوضاع فرق داشت، همیشه نمیشه از براکت توی مرتبه زمانی ها چشم پوشی کرد. می دونیم: [tex]\sum^n_{i=1}\frac{1}{i}=\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n}=\ln n=\theta(\log n)[/tex]
نقل قول این ارسال در یک پاسخ

۱
ارسال: #۲۳
  

Saman پاسخ داده:

RE: حل سوالات ساختمان داده و طراحی الگوریتم(۶۰۰ مساله،و تست های مهم)

سوال دهم (۳۰ کتاب نارنجی و ۵۱/۱ از ۶۰۰ سوال)

زمان اجرای رویه ی زیر چقدر است(بهترین گزینه را انتخاب کنید) :
کد:
ISPRME(N)
I=3
IF(N==2 or  N==3)
then return true
if(n  mod  2 ==0)
then return false
while (i^2 <=N)
do if (N mod i==0)
then return false
else i = i+2
return true

۱) [tex]O(\log N)[/tex]

۲)[tex]\theta(\log N)[/tex]

۳)[tex]O(\sqrt{n})[/tex]

۴)[tex]\theta(\sqrt{n})[/tex]

سوال یازدهم (۵۹/۱از ۶۰۰ سوال و ارشد ۹۱)
هزینه ی زمانی تکه برنامه ی روبه رو کدام است؟ (دقت شود که مقادیر i/2 و j/3 به صورت کفِ مقادیر میباشند)

کد:
i=n
while i  > 1
do  i =i/2
i=j
while j>1 do j=j/3

۱)[tex]O(\log^2n)[/tex]

۲)[tex]O(\log n)[/tex]

۳)[tex]O(n)[/tex]

۴) [tex]O(n^2)[/tex]

سوال دوازدهم(*)(۶۳/۱ از ۶۰۰ سوال)
آرایه A به طول n داده شده است که تمام درایه های آن در ابتدا صفر هستند.عمل درج روبه رو را n بار با مقادیر دلخواه x انجام میدهیم هزینه ی سرشکن شده ی هر عمل درج کدام است؟بهترین گزینه را انتخاب کنید
کد:
INSERT (X)
n=n+1 , t=x
[for  i = 0 to [log n
do if A[i] <> 0
then t=t+A[i]
A[i] =0
else A[i] =t
return
نقل قول این ارسال در یک پاسخ

۰
ارسال: #۲۴
  

Saman پاسخ داده:

RE: حل سوالات ساختمان داده و طراحی الگوریتم(۶۰۰ مساله،و تست های مهم)(۱)

پاسخ سوال سیزدهم
گزاره ی اول نادرست است ، چون الگوریتم مرتب سازی سریع یک مثال نقض مناسب برای آن است.
زمان اجرای این الگوریتم در بدترین حالت [tex]O(n^2)[/tex] و در حالت میانگین [tex]O(nlogn)[/tex] است.

نکته : در مرتب سازی سریع اگر لیست از قبل مرتب باشد یا به صورت معکوس مرتب باشد داریم : [tex]\theta(n^2)[/tex] چرا که در این دو حالت در هر فراخوانی از روال partition یک زیر لیست با [tex]Q(n-1)[/tex] و دیگری با [tex]Q(0)[/tex] (یک لیست تهی) فراخوانی میشود که در کل مرتبه ی زمانی برابر است با :
[tex]Q(n)=Q(n-1)+Q(0)+n-1[/tex] دقت کنید که n-1 از نتیجه ی مقایسه عنصور محوری با کل عناصر است. مرتبه ی این حالت در کل : [tex]\theta(n^2)[/tex] است.

مرتب سازی سریع در حالت میانگین و بهترین حالت از مرتبه ی [tex]\theta(nlogn)[/tex] است که در نتیجه ی حالتی است که عنصر میانه را در وسط لیست بگیریم که رابطه ی بازگشتی تقریبی زیر با مرتبه ی ذکر شده به دست آید.
[tex]Q(n)\simeq Q(\frac{n}{2})+Q(\frac{n}{2})+n-1[/tex]

(در حال تکمیل . . .)
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  آزمون دکتری نرم افزار و الگوریتم ۱۴۰۰ Seyyedab ۴۰ ۷۳۳ ۱۸ اسفند ۱۳۹۹ ۰۸:۱۶ ب.ظ
آخرین ارسال: Seyyedab
  طراحی ui/ux kimiya1234 ۲ ۳۲۷ ۲۶ بهمن ۱۳۹۹ ۱۰:۴۲ ب.ظ
آخرین ارسال: farsamw
  پکیج آموزشی طراحی وب + فارسی سازی وردپرس + سئو Happiness.72 ۶ ۳,۲۱۵ ۱۸ بهمن ۱۳۹۹ ۰۱:۱۵ ب.ظ
آخرین ارسال: saqarmoshtaq
  طراحی یک سیستم نورانی هوشمند marvelous ۹ ۱,۸۳۰ ۱۶ بهمن ۱۳۹۹ ۰۱:۵۶ ب.ظ
آخرین ارسال: karnofa
  طراحی یک سیستم عامل (از صفر) sina4everafter ۱۲ ۱۰,۳۱۴ ۰۶ بهمن ۱۳۹۹ ۱۲:۵۳ ب.ظ
آخرین ارسال: nahalmomen2007@yahoo.com
  طراحی سایت ریسپانسیو wikidemy1 ۰ ۲۶۷ ۱۳ دى ۱۳۹۹ ۰۴:۰۱ ب.ظ
آخرین ارسال: wikidemy1
  تشریح تست همروندی - بررسی یکی از سوالات سال ۸۲ abji22 ۵ ۱,۶۱۷ ۰۲ دى ۱۳۹۹ ۱۱:۰۵ ق.ظ
آخرین ارسال: mohammadasadi1
  طراحی الگوریتم ها amir.m5560@gmail.com ۰ ۲۳۳ ۳۰ آذر ۱۳۹۹ ۰۸:۲۴ ب.ظ
آخرین ارسال: amir.m5560@gmail.com
  طراحی الگوریتم ها amir.m5560@gmail.com ۰ ۲۱۳ ۳۰ آذر ۱۳۹۹ ۰۸:۲۰ ب.ظ
آخرین ارسال: amir.m5560@gmail.com
  مجموعه تمارین و سوالات امتحانی درس طراحی الگوریتم دانشگاه MIT (سال ۲۰۰۰-۲۰۱۲) Farid_Feyzi ۵ ۴,۰۲۴ ۳۰ آبان ۱۳۹۹ ۱۰:۱۵ ب.ظ
آخرین ارسال: s-taheri

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close