تالار گفتمان مانشت

یک ارایه n تایی از اعداد صحیح با شرط های زیر داده شده است
۱- [tex]A(1)=x,A(n)=y,x<y[/tex]
۲- [tex]\forall i \left | A(i)- A(i 1) \right |\leq 1[/tex]
یک الگوریتم کارا برای جستجوی w به طوری که [tex]x\leq w\leq y[/tex] در ازایه A طراحی شده است. این الگوریتم اندیس w را در صورت وجود به دست می آورد. پیچیدگی الگوریتم در بدترین حالت و حالت متوسط چیست

کتاب پوران به این سوال این جواب را داده که(صفحه ۱۴۴)
با توجه به شرط های بیان شده ارایه مرتب است و برای ارایه مرتب می توان ار جستجوی دودویی استفاده کردو این جستجو در بدترین حالت و حالت متوسط دارای پیچیدگی O(log(n می باشد
ولی اگر به شرط ها دقت کنیم لزومی ندارد ارایه مرتب باشد بلکه به نظر من در بهترین حالت ارایه مرتب است به عنوان مثال اگر فرض کنیم y=x+2 و n=6 باشد. یک مقدار برای ارایه از اندیس ۱ تا n به ترتیب از چپ به راست برابر است با
x-1,x,x-1,x,x+1,x+2
با این حساب جواب این سوال چیست؟

باز هم درست در میاد
چون درسته که آرایه یی که شما مثال زدید مرتب نیست ولی دارای داده های تکراری هست و اگه داده های تکراری را حذف کنید به شکل مرتب در میاد و جستجوی دودویی بدرستی در زمان log n جواب را برمیگردونه
ولی اگه حتی داده های تکراری را حذف هم نکنید باز هم جستجوی دودیی روی مثال شما با زمان log n جواب را بر میگردونه. چون شما داده تکراری دارید و w را با هرکدوم از داده های تکراری که مقایسه کنیم برای ما فرقی نداره
مثلا مقدار w برابر مقدار x باشه: اونوقت w را با مقدار وسط(x-1) مقایسه میکنه و چون بزرگتره میاد توی نیمه دوم و در مرحله بعد با عنصر پنجم و در آخر با عنصر چهارم مقایسه و پیدا میشه

(15 مرداد 1392 08:43 ب.ظ)mhm-pc نوشته شده توسط: [ -> ]باز هم درست در میاد
چون درسته که آرایه یی که شما مثال زدید مرتب نیست ولی دارای داده های تکراری هست و اگه داده های تکراری را حذف کنید به شکل مرتب در میاد و جستجوی دودویی بدرستی در زمان log n جواب را برمیگردونه
ولی اگه حتی داده های تکراری را حذف هم نکنید باز هم جستجوی دودیی روی مثال شما با زمان log n جواب را بر میگردونه. چون شما داده تکراری دارید و w را با هرکدوم از داده های تکراری که مقایسه کنیم برای ما فرقی نداره
مثلا مقدار w برابر مقدار x باشه: اونوقت w را با مقدار وسط(x-1) مقایسه میکنه و چون بزرگتره میاد توی نیمه دوم و در مرحله بعد با عنصر پنجم و در آخر با عنصر چهارم مقایسه و پیدا میشه

سلام جواب بالا من را قانع نمی کند. ایا کسی جواب بهتری برای این سوال دارد؟

سلام
من کلاس های دکتر یوسفی را می رفتم
بین کلاس ها این سوال رو ازشونپرسیدم و گفتم فکر کنم اینجای کتابتون غلط باشه
ایشون گفتند خودم هم این جوابی که نوشتم را قبول ندارم و دکتر قدسی معتقدند که ارایه مرتب است اما گویا اشتباه فکر می کنند
و در کتاب یودی منبر(Udi manber) هم نوشته شده که این کار در زمان لگاریتمی قابل حل است اما ننوشته که چطور