یا سلام.این سوال رو از فصل ۲کتاب آقای مقسمی آوردم.
اگه مرتب سازی ادغام رو به این ترتیب کمی تغییر بدیم که لیست به دوقسمت تقسیم شود که این قسمت‌ها با هم نسبت ۹ به ۱داشته باشند پیچیدگی زمانی الگوریتم در این حالت از چه مرتبه ایست؟
بنده این مسئله رو به این شکل حل کردم [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/10) 9T(n/10)=10T(n/10)[/tex]
اینی که شما نوشتید یعنی این که بیایم مسئله‌ی اصلی رو تبدیل کنیم به ۱۰ تا مسئله‌ی کوچکتر که سایز هر کدوم ۱/۱۰ مسئله‌ی اصلی هست!
اما [tex]T(n)=T(n/10) T(9n/10)[/tex] یعنی که مسئله رو تبدیل کنید به دو زیر مسئله‌ی کوچکتر که سایز ورودی یکیش ۱/۱۰ مسئله‌ی اصلی و سایز ورودی دیگری ۹/۱۰ سایز ورودی اصلی هست. (همون چیزی که توی صورت سوال خواسته)
اگه با این مثال مشکلتون حل نشد بگید که باز توضیح بدم که چه طوری میشه فهمید ورودی‌ها و ضریب‌ها چی باشه!
اگه وقتشو داشته باشید ممنون میشم که توضیح بدین...
ما میایم مسئله رو به k تا زیر مسئله ای که شبیه مسئله‌ی اصلی هستند تقسیم میکنیم و چون شبیه مسئله‌ی اصلی هستند پس میشه از همون تابعی که برای محاسبه‌ی پیچیدگی مسئله‌ی اصلی استفاده میکنیم، برای حل زیرمسئله‌ها هم استفاده کنیم، یعنی این طوری: [tex]T(x)=T(x_1) T(x_2) ... T(x_k) f(x)[/tex]
خب همون طور که میبینید، x سایز ورودی مسئله‌ی اصلی هست، اما سایز ورودی زیرمسئله‌ها چیه؟ در واقع وقتی ما مسئله رو به چند زیرمسئله تقسیم کردیم، اومدیم مسائلی با ورودی کوچکتر رو حساب کردیم و نتایجش رو ترکیب کردیم پس ورودی زیرمسئله‌ها در واقع x هست که بینشون تقسیم شده، حالا مثلاً ممکنه این طوری تقسیم کنیم که نصف ورودی مسئله‌ی اصلی رو بدیم به یه زیر مسئله، نصفش رو بدیم به یه زیرمسئله‌ی دیگه پس این جا ورودی هر کدوم از زیرمسئله‌ها نصف ورودی مسئله میشن! (شبیه Quick Sort) یا ...
ضریب پشت یعنی تعداد زیر مسأله ها
ضریب درون پرانتز یعنی سایز زیر مسأله ها
-----------------
اونطور که شما نوشتین یعنی ۱ زیر مساله و ۹ زیر مساله( یعنی در کل ۱۰ زیر مساله).
اونطور که باید می نوشتین (۹ داخل پرانتز) یعنی یک زیر مسأله با سایز ۱ و یک زیر مسأله با سایز ۱۰/۹ ام.