۰
subtitle
ارسال: #۱
مرتب سازی ادغام با اندکی تغییر...
یا سلام.این سوال رو از فصل ۲کتاب آقای مقسمی آوردم.
اگه مرتب سازی ادغام رو به این ترتیب کمی تغییر بدیم که لیست به دوقسمت تقسیم شود که این قسمت‌ها با هم نسبت ۹ به ۱داشته باشند پیچیدگی زمانی الگوریتم در این حالت از چه مرتبه ایست؟
بنده این مسئله رو به این شکل حل کردم [tex]T(n)=T(n/10) 9T(n/10) cn[/tex] . و با استفاده از قضیه اصلی جواب بدست اومده شد [tex]O(n)[/tex]
اما جواب مسئله رو که دیدم رابطه بازگشتی رو به این شکل نوشته بود:
[tex]T(n)=T(n/10) T(9n/10) cn[/tex] و در ادامه آورده بود که اگه در رابطه [tex]T(n)=T(an/b) T(cn/d) ... f(n)[/tex] مجموع [tex]a/b c/d ...=1[/tex] آنگاه پیچیدگی تابع برابر خواهد بود با: [tex]O(Log n * f(n))[/tex] و در نتیجه جواب مسئله فوق برابر [tex]O(nlogn)[/tex] میشه..
سوال:آیا رابطه ای که بنده نوشته‌ام دارای اشکاله .فرق رابطه ای که بنده نوشتم با این رابطه در چیه؟لطفا بصورت تحلیلی پاسخ بدید.
و در واقع از کجا باید بفهمیم که باید زیر مسئله دوم رو بشکل [tex]9T(n/10)[/tex] بنویسیم و یا بشکل [tex]T(9n/10)[/tex].
اگه مرتب سازی ادغام رو به این ترتیب کمی تغییر بدیم که لیست به دوقسمت تقسیم شود که این قسمت‌ها با هم نسبت ۹ به ۱داشته باشند پیچیدگی زمانی الگوریتم در این حالت از چه مرتبه ایست؟
بنده این مسئله رو به این شکل حل کردم [tex]T(n)=T(n/10) 9T(n/10) cn[/tex] . و با استفاده از قضیه اصلی جواب بدست اومده شد [tex]O(n)[/tex]
اما جواب مسئله رو که دیدم رابطه بازگشتی رو به این شکل نوشته بود:
[tex]T(n)=T(n/10) T(9n/10) cn[/tex] و در ادامه آورده بود که اگه در رابطه [tex]T(n)=T(an/b) T(cn/d) ... f(n)[/tex] مجموع [tex]a/b c/d ...=1[/tex] آنگاه پیچیدگی تابع برابر خواهد بود با: [tex]O(Log n * f(n))[/tex] و در نتیجه جواب مسئله فوق برابر [tex]O(nlogn)[/tex] میشه..
سوال:آیا رابطه ای که بنده نوشته‌ام دارای اشکاله .فرق رابطه ای که بنده نوشتم با این رابطه در چیه؟لطفا بصورت تحلیلی پاسخ بدید.
و در واقع از کجا باید بفهمیم که باید زیر مسئله دوم رو بشکل [tex]9T(n/10)[/tex] بنویسیم و یا بشکل [tex]T(9n/10)[/tex].
۰
ارسال: #۲
RE: مرتب سازی ادغام با اندکی تغییر...
[tex]T(n/10) 9T(n/10)=10T(n/10)[/tex]
اینی که شما نوشتید یعنی این که بیایم مسئله‌ی اصلی رو تبدیل کنیم به ۱۰ تا مسئله‌ی کوچکتر که سایز هر کدوم ۱/۱۰ مسئله‌ی اصلی هست!
اما [tex]T(n)=T(n/10) T(9n/10)[/tex] یعنی که مسئله رو تبدیل کنید به دو زیر مسئله‌ی کوچکتر که سایز ورودی یکیش ۱/۱۰ مسئله‌ی اصلی و سایز ورودی دیگری ۹/۱۰ سایز ورودی اصلی هست. (همون چیزی که توی صورت سوال خواسته)
اگه با این مثال مشکلتون حل نشد بگید که باز توضیح بدم که چه طوری میشه فهمید ورودی‌ها و ضریب‌ها چی باشه!
اینی که شما نوشتید یعنی این که بیایم مسئله‌ی اصلی رو تبدیل کنیم به ۱۰ تا مسئله‌ی کوچکتر که سایز هر کدوم ۱/۱۰ مسئله‌ی اصلی هست!
اما [tex]T(n)=T(n/10) T(9n/10)[/tex] یعنی که مسئله رو تبدیل کنید به دو زیر مسئله‌ی کوچکتر که سایز ورودی یکیش ۱/۱۰ مسئله‌ی اصلی و سایز ورودی دیگری ۹/۱۰ سایز ورودی اصلی هست. (همون چیزی که توی صورت سوال خواسته)
اگه با این مثال مشکلتون حل نشد بگید که باز توضیح بدم که چه طوری میشه فهمید ورودی‌ها و ضریب‌ها چی باشه!
۰
۰
ارسال: #۴
RE: مرتب سازی ادغام با اندکی تغییر...
ما میایم مسئله رو به k تا زیر مسئله ای که شبیه مسئله‌ی اصلی هستند تقسیم میکنیم و چون شبیه مسئله‌ی اصلی هستند پس میشه از همون تابعی که برای محاسبه‌ی پیچیدگی مسئله‌ی اصلی استفاده میکنیم، برای حل زیرمسئله‌ها هم استفاده کنیم، یعنی این طوری: [tex]T(x)=T(x_1) T(x_2) ... T(x_k) f(x)[/tex]
خب همون طور که میبینید، x سایز ورودی مسئله‌ی اصلی هست، اما سایز ورودی زیرمسئله‌ها چیه؟ در واقع وقتی ما مسئله رو به چند زیرمسئله تقسیم کردیم، اومدیم مسائلی با ورودی کوچکتر رو حساب کردیم و نتایجش رو ترکیب کردیم پس ورودی زیرمسئله‌ها در واقع x هست که بینشون تقسیم شده، حالا مثلاً ممکنه این طوری تقسیم کنیم که نصف ورودی مسئله‌ی اصلی رو بدیم به یه زیر مسئله، نصفش رو بدیم به یه زیرمسئله‌ی دیگه پس این جا ورودی هر کدوم از زیرمسئله‌ها نصف ورودی مسئله میشن! (شبیه Quick Sort) یا ...
خب همون طور که میبینید، x سایز ورودی مسئله‌ی اصلی هست، اما سایز ورودی زیرمسئله‌ها چیه؟ در واقع وقتی ما مسئله رو به چند زیرمسئله تقسیم کردیم، اومدیم مسائلی با ورودی کوچکتر رو حساب کردیم و نتایجش رو ترکیب کردیم پس ورودی زیرمسئله‌ها در واقع x هست که بینشون تقسیم شده، حالا مثلاً ممکنه این طوری تقسیم کنیم که نصف ورودی مسئله‌ی اصلی رو بدیم به یه زیر مسئله، نصفش رو بدیم به یه زیرمسئله‌ی دیگه پس این جا ورودی هر کدوم از زیرمسئله‌ها نصف ورودی مسئله میشن! (شبیه Quick Sort) یا ...
۰
ارسال: #۵
مرتب سازی ادغام با اندکی تغییر...
ضریب پشت یعنی تعداد زیر مسأله ها
ضریب درون پرانتز یعنی سایز زیر مسأله ها
-----------------
اونطور که شما نوشتین یعنی ۱ زیر مساله و ۹ زیر مساله( یعنی در کل ۱۰ زیر مساله).
اونطور که باید می نوشتین (۹ داخل پرانتز) یعنی یک زیر مسأله با سایز ۱ و یک زیر مسأله با سایز ۱۰/۹ ام.
ضریب درون پرانتز یعنی سایز زیر مسأله ها
-----------------
اونطور که شما نوشتین یعنی ۱ زیر مساله و ۹ زیر مساله( یعنی در کل ۱۰ زیر مساله).
اونطور که باید می نوشتین (۹ داخل پرانتز) یعنی یک زیر مسأله با سایز ۱ و یک زیر مسأله با سایز ۱۰/۹ ام.
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close