سلام
دوستان میشه بگین این سوال چطوری حل میشه؟
جواب گزینه ۱
تشکر
سلام...
بررسی اینکه یک دنباله به طول n زیر دنباله یک دنباله به طول m است از مرتبه n+m است.
برای یافتن Max که B^i زیر دنباله A باشد واضح است که i نمی تواند از n/mبیشتر باشه پس بیشترین مقدار i برابر n/m است حالا باید چک کنیم برای i=n/m جواب می دهد یا نه!
ابتدا i را برابر ۱/۲*n/m قرار می دهیم یعنی نصف n/m اگر B^i زیر دنباله A باشد شبیه جستجوی دودویی مقادیر کوچکتر از سقف n/m را نادیده بگیرید و اگر B^i زیر دنباله A نبود مقادیر بیشتر از ۱/۲ سقف n/m را نادیده بگیرید و با روش دودویی این عمل را انجام دهید تعداد بررسی ها برای یافتن Max(i برابر سقف log n/m است پس زمان اجرا برابر
n+m*logn/m است که چون n از m بیشتر است جواب n*logn/mمی شه!
یعنی در واقع باید بیاییم یه چیزی شبیه جستجوی دودویی هی قسمت های نصف سقف n/m را در داخل A در نظر گرفته هر قسمت را بررسی تا ببینیم آیا زیر دنباله هست یا نه و اون قسمت را اگر زیر دنباله بود که در مرحله بعدی در نظر بگیریم و اگر نبود در نظرش نگیریم و چون باید n بار logn/m را هی بررسی کنیم ج می شه nlogn/m ....
موفق باشید
دهنم سرویس شد تا فهمیدم راه حلش چی می گه
(۱۸ بهمن ۱۳۹۲ ۰۲:۱۵ ب.ظ)mahsalove نوشته شده توسط: سلام...
بررسی اینکه یک دنباله به طول n زیر دنباله یک دنباله به طول m است از مرتبه n+m است.
برای یافتن Max که B^i زیر دنباله A باشد واضح است که i نمی تواند از n/mبیشتر باشه پس بیشترین مقدار i برابر n/m است حالا باید چک کنیم برای i=n/m جواب می دهد یا نه!
ابتدا i را برابر ۱/۲*n/m قرار می دهیم یعنی نصف n/m اگر B^i زیر دنباله A باشد شبیه جستجوی دودویی مقادیر کوچکتر از سقف n/m را نادیده بگیرید و اگر B^i زیر دنباله A نبود مقادیر بیشتر از ۱/۲ سقف n/m را نادیده بگیرید و با روش دودویی این عمل را انجام دهید تعداد بررسی ها برای یافتن Max(i برابر سقف log n/m است پس زمان اجرا برابر
n+m*logn/m است که چون n از m بیشتر است جواب n*logn/mمی شه!
یعنی در واقع باید بیاییم یه چیزی شبیه جستجوی دودویی هی قسمت های نصف سقف n/m را در داخل A در نظر گرفته هر قسمت را بررسی تا ببینیم آیا زیر دنباله هست یا نه و اون قسمت را اگر زیر دنباله بود که در مرحله بعدی در نظر بگیریم و اگر نبود در نظرش نگیریم و چون باید n بار logn/m را هی بررسی کنیم ج می شه nlogn/m ....
موفق باشید
دهنم سرویس شد تا فهمیدم راه حلش چی می گه
وقتی که ما میخواهیم برای [tex]i = \frac{n}{2m}[/tex] چک کنیم که ایا [tex]B^i[/tex] یک زیر دنباله هست یا نه یه هزینه ای باید بدیم که توی تحلیل شما تی پاراگراف اول این هزینه حساب نشده و یه جای کار میلنگه!
(۱۸ بهمن ۱۳۹۲ ۰۲:۴۳ ب.ظ)Riemann نوشته شده توسط:(18 بهمن ۱۳۹۲ ۰۲:۱۵ ب.ظ)mahsalove نوشته شده توسط: سلام...
بررسی اینکه یک دنباله به طول n زیر دنباله یک دنباله به طول m است از مرتبه n+m است.
برای یافتن Max که B^i زیر دنباله A باشد واضح است که i نمی تواند از n/mبیشتر باشه پس بیشترین مقدار i برابر n/m است حالا باید چک کنیم برای i=n/m جواب می دهد یا نه!
ابتدا i را برابر ۱/۲*n/m قرار می دهیم یعنی نصف n/m اگر B^i زیر دنباله A باشد شبیه جستجوی دودویی مقادیر کوچکتر از سقف n/m را نادیده بگیرید و اگر B^i زیر دنباله A نبود مقادیر بیشتر از ۱/۲ سقف n/m را نادیده بگیرید و با روش دودویی این عمل را انجام دهید تعداد بررسی ها برای یافتن Max(i برابر سقف log n/m است پس زمان اجرا برابر
n+m*logn/m است که چون n از m بیشتر است جواب n*logn/mمی شه!
یعنی در واقع باید بیاییم یه چیزی شبیه جستجوی دودویی هی قسمت های نصف سقف n/m را در داخل A در نظر گرفته هر قسمت را بررسی تا ببینیم آیا زیر دنباله هست یا نه و اون قسمت را اگر زیر دنباله بود که در مرحله بعدی در نظر بگیریم و اگر نبود در نظرش نگیریم و چون باید n بار logn/m را هی بررسی کنیم ج می شه nlogn/m ....
موفق باشید
دهنم سرویس شد تا فهمیدم راه حلش چی می گه
وقتی که ما میخواهیم برای [tex]i = \frac{n}{2m}[/tex] چک کنیم که ایا [tex]B^i[/tex] یک زیر دنباله هست یا نه یه هزینه ای باید بدیم که توی تحلیل شما تی پاراگراف اول این هزینه حساب نشده و یه جای کار میلنگه!
منم خیلی روی این قسمت پاسخشون فکر کردم..
ولی فکر میکنم ایشون ابتدا تعداد بررسیها رو حساب کردند و در اخر ضرب در هزینه هر بررسی کردند!!