صفحهها: ۱ ۲
خب ببخشید چطوری با جاگذاریn=2^k میشه به تتای nlog رسید؟
کلا من میخوام بدونم چطوری و با چه محاسباتی میشه به تتای nlogn رسید؟
خب چه محاسباتی روی اون معدله باید انجام بدم تا برسم به تتایnlogn ؟
(۲۹ مهر ۱۳۹۱ ۰۷:۳۶ ب.ظ)roofia نوشته شده توسط: خب ببخشید چطوری با جاگذاریn=2^k میشه به تتای nlog رسید؟
کلا من میخوام بدونم چطوری و با چه محاسباتی میشه به تتای nlogn رسید؟
خب چه محاسباتی روی اون معدله باید انجام بدم تا برسم به تتایnlogn ؟
ببینید، اون n=2^k رو برای راحتی کار فرض کرده، یعنی فرض کرده که طول آرایه ای که می خواد ادغام کنه طوری باشه که دقیقا نصف بشه. پس اگه اون n=2^k رو هم تو مفروضات نباشه مهم نیست.
قضیه اصلی یا master برای همچین حالاتی میتونه جواب رو بدست بیاره. شما یک بار اون قسمت رو بخون، حتما متوجه میشی.
چون ۲ به توان (لگاریتم a در مبنای b) برابر با n میشه، که a همون ۲ قبل از Tn و b همون ۲ که در مخرج وجود داره (n/2) هست، و مقدار زمان برای ادغام و مقایسه برابر با تتای n بوده، پس این Tn با این زمان ادغام و مقایسه برابر بوده و در صورت برابری این دوتا جواب میشه تتای nlogn . ( اذعان می کنم خیلی بد توضیح دادم، بهت حق میدم متوجه نشی، شما قضیه اصلی رو بخون متوجه خواهی شد)
موفق باشی.
راه حل تشریحی فرمول روابط بازگشتی مرتب سازی ادغامی رو میخوام!
در مرتب سازی ادغامی دوتا لیست دارن با هم ادغام میشن و مرتب میشن.این رو کاملا بلدم.
حالا چطوری میتونم همین روال رو برای سه تا لیست تعمیم بدم؟
میشه راهنماییم کنید؟
راهنمائـــــــــــــــــــــــــــــــــــــــــــــــــــــیم کنید خواهشا!!!!!
(۰۱ آبان ۱۳۹۱ ۰۸:۱۳ ب.ظ)razaghian نوشته شده توسط: در مرتب سازی ادغامی دوتا لیست دارن با هم ادغام میشن و مرتب میشن.این رو کاملا بلدم.
حالا چطوری میتونم همین روال رو برای سه تا لیست تعمیم بدم؟
میشه راهنماییم کنید؟
راهنمائـــــــــــــــــــــــــــــــــــــــــــــــــــــیم کنید خواهشا!!!!!
سلام
خوب سه تا اشارگر نیاز داری که به اول سه لیست اشاره کنه مثلآ i و j و k بعد باید با دو مقایسه ببینی کدامیک از این شه مقداری که این اشاره گر ها بهش اشاره میکنن کوچکتره ٰ و بعد اونو داخل آرایه نهایی بریزی و الی آخر ...
میخواهی برنامشو بنویسم برات ؟ به زبان سی پلاس پلاس بنویسم ؟
سلام!
الگوریتمشو میخوام.
واسه درس طراحی الگوریتم.
با آرایه!
اگ بنویسید که لطف بزرگی میکنید در حقم!
بله سی پلاس پلاس:-)
(۰۱ آبان ۱۳۹۱ ۰۹:۱۸ ب.ظ)razaghian نوشته شده توسط: سلام!
الگوریتمشو میخوام.
واسه درس طراحی الگوریتم.
با آرایه!
اگ بنویسید که لطف بزرگی میکنید در حقم!
بله سی پلاس پلاس:-)
اولش که برنامه رو شروع کردم به نوشتن ، گفتم آسونه ! بعدش دیدم ناجوره ! البته مشکل خاصی نبود ولی یکم ریزه کاری داشت و تا جایی که تونستم جوری نوشتم که خوانایی برنامه حفظ بشه ولی در کل برنامه روتینی نیست که با یک نگاه بشه ازش سر در آورد. (در ضمن شاید یه بنده خدایه دیگه بهتر از من بنویسه چون من هنگام دیدن برنامه مورد علاقم ("افسانه دونگی") داشتم کد مینوشتم ! زیاد بهینه نیست ولی صد در صد درسته) و اینم بگم که ایدش همون ادغام دو آرایه هست و چیزی نیست که از کره مریخ اومده باشه
خوش به حالتون.چقد بلدید.حالم از خودم به هم خورد.:-(
دستتون درد نکنه.خیلی لطف کردید واقعا!
("افسانه دونگی") هم فیلم جالبیه:-)