سلام و خسته نباشید ... دوستان من یک مثال زدم که این سوال خیلی عجیبه که در logn بشه حلش کنیم !
از آنجایی که خودم در تمامی کنکور های آزمایشی پارسه و ... رتبه زیر ۱۰۰ داشتم و در این درس تسلط شدید دارم خواهش میکنم کسانی که تخصص لازم دارن که باعث نشه از بحث دور شیم
در این سوال کمترین هزینه [tex]O(n/2)[/tex] هست که میشه همون [tex]O(n)[/tex]
یک عکس ضمیمه کردم که اینو اثبات میکنه که شما حتما n/2 مقایسه باید انجام بدید
اگر دو آریه وجود نداشت و یک آرایه به صورت صعودی بود آنوقت هزینه k امین عنصر برابر ۱ ... مراجه به اندیس مورد نظر
اما اینجا ۲ آرایه متفاوت هستند به اندازه [tex]n/2[/tex] که k امین عنصر اجتماع آن دو را میخواد در نتیجه میتونه همه جای آرایه قرار بگیره( به عکس مراجعه شود)
هایفل اثبات کرد که حد پایین برای یافتن کوچکترین کلید در مجموعه n کلیدی برای k>1 به صورت زیر است
[tex]n ( k-1 )[ log(n/k-1)] - k [/tex] که برابر میشه با [tex]O(n)[/tex]
page 129 مقسمی
والا کمتر از این من جایی ندیدم کسی موفق شده باشه شاید طراح سوال تونسته یا دانشمندی به تازگی مقاله علمیشو ثبت کرده ما بی اطلاع هستیم !!!!
شاید من اشتباه میکنم اگه روشه حلشو بلدین به منم بگید ممنون میشم
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
من خودم چونکه سر جلسه"لوگ کا" توی گزینه‌ها نبود گفتم حتما راه حل بالا مد نظرش نبوده و برای همین گزینه ۴ رو زدم.
من اعتراض کردم.و گزینه "سئوال فاقد گزینه صحیح است" را انتخاب کردم.
با سلام
سوال ۳۳ کاملا درسته تو چند کتاب طراحی الگوریتم هم اورده شده است جواب این سوال همونه رجوع کن به فصل ۲۱ قسمت عملیاتunion,find
منظورشون کتاب clrs
ببخشید کتاب دیگه ای مد نظرتون هست ... ؟ آخه کتاب کرمن امانت دستم بود پس دادم
کتاب های زیرو دارم
الگوریتم مقسمی
الگوریتم پوران
الگوریتم قلی زاده
ساختمان قدسی
ساختمان پارسه
لطفا صفحه یکی از این کتاب‌ها رو بگید... گرچه همشو میدونم و منم دارم حرف اینارو میزنم... میتونم شماره صفحه بدم
همگی روی n اتفاق نظر دارن
این استدلال که میگید می تونه تو همه‌ی خونه‌ها باشه پس باید همه‌ی خونه‌ها مقایسه بشه درست نیست، پس الگوریتم BinarySearch به چه دردی می خوره؟
مثال مشابه اینه که یه آرایه‌ی مرتب با n عنصر داریم و می خوایم ببینیم عدد x در کجای آرایه هست که طبق استدلال شما چون x در همه جای آرایه می تونه باشه پس باید همه‌ی خونه‌ها رو چک کنیم و میشه از [tex]O(n)[/tex] در حالی که می دونیم با یه BS میشه x رو پیدا کرد با [tex]O(log n)[/tex]
الگوریتم با [tex]O(log n)[/tex] یه کم سخته توضیح دادنش اینجا، ولی یه روش واضح با [tex]O(log^{2} n)[/tex] وجود داره به این صورت که فرض می کنیم که kامین عدد در آرایه‌ی A باشه (یکبار هم همین کار رو برای B انجام میدیم) حالا روی آرایه‌ی A الگوریتم BS رو اجرا می کنیم به این صورت که هر بار که یک عنصر میانی در A رو در نظر گرفتیم (فرض کنید [tex]A[i][/tex]) با یه BS دیگه روی B می فهمیم که چندتا از عناصر B از [tex]A[i][/tex] کوچکتر هستند و در نتیجه می تونیم بفهمیم که [tex]A[i][/tex] در صورت ادغام ۲ آرایه عنصر چندم خواهد بود. که اگه از K کمتر بود به سمت اعداد بزرگتر میریم و اگه بیشتر بود بلعکس.
به این ترتیب با ۲ تا BS تو در تو تونستیم kامین عنصر رو پیدا کنیم که میشه از [tex]O (log^{2}n)[/tex]
اگه جاییش نامفهومه بگید توضیح میدم و اگر هم فکر میکنید غلطه ایرادش رو بگید بررسی کنم
اگر هم الگوریتم از [tex]O (logn)[/tex] رو خواستید بگید خلاصه بنویسم
قبلا در قسمت طراحی الگوریتمباتوضیچش در فایل گذاشتمبرین ببینینجواب این سوال تغییر نمیکنه در ضمن اینم بگم تو الگوریتم بهترین زمان را باید حساب کنیم حرفای شما با یه الگوریتم هایی که میگین درسته ولی بهترین نیستندواسه همین تو جلد دوم کتاب مقدمه ای بر الگوریتم کورمن مترجم جعفر نژاد قمی دقیقا اینو یه نکته نوشته.
(۱۲ اسفند ۱۳۸۹ ۰۳:۳۳ ق.ظ)poopi نوشته شده توسط: این استدلال که میگید می تونه تو همه‌ی خونه‌ها باشه پس باید همه‌ی خونه‌ها مقایسه بشه درست نیست، پس الگوریتم BinarySearch به چه دردی می خوره؟
مثال مشابه اینه که یه آرایه‌ی مرتب با n عنصر داریم و می خوایم ببینیم عدد x در کجای آرایه هست که طبق استدلال شما چون x در همه جای آرایه می تونه باشه پس باید همه‌ی خونه‌ها رو چک کنیم و میشه از [tex]O(n)[/tex] در حالی که می دونیم با یه BS میشه x رو پیدا کرد با [tex]O(log n)[/tex]
الگوریتم با [tex]O(log n)[/tex] یه کم سخته توضیح دادنش اینجا، ولی یه روش واضح با [tex]O(log^{2} n)[/tex] وجود داره به این صورت که فرض می کنیم که kامین عدد در آرایه‌ی A باشه (یکبار هم همین کار رو برای B انجام میدیم) حالا روی آرایه‌ی A الگوریتم BS رو اجرا می کنیم به این صورت که هر بار که یک عنصر میانی در A رو در نظر گرفتیم (فرض کنید [tex]A[i][/tex]) با یه BS دیگه روی B می فهمیم که چندتا از عناصر B از [tex]A[i][/tex] کوچکتر هستند و در نتیجه می تونیم بفهمیم که [tex]A[i][/tex] در صورت ادغام ۲ آرایه عنصر چندم خواهد بود. که اگه از K کمتر بود به سمت اعداد بزرگتر میریم و اگه بیشتر بود بلعکس.
به این ترتیب با ۲ تا BS تو در تو تونستیم kامین عنصر رو پیدا کنیم که میشه از [tex]O (log^{2}n)[/tex]
اگه جاییش نامفهومه بگید توضیح میدم و اگر هم فکر میکنید غلطه ایرادش رو بگید بررسی کنم
اگر هم الگوریتم از [tex]O (logn)[/tex] رو خواستید بگید خلاصه بنویسم
خیلی ممنون از گفته هاتون... راستش در مورد ج اولتون که bs به چه دردی میخوره کاملا موافقم اما این سوال یه فرقایی داره آخه لیست باید ادغام بشه در نتیجه لیست باز نا مرتب میشه که توی شکل نشون دادم فرض کن عکسی که دادم آرایه b رو به انتهای a بچسبونیم...... حالا فرض میکنیم( گرچه میدونم که راه درستش اینه که اصلا ادغام نکنیم تا بتونیم پیچدگی کمتری پیدا کنیم و لیست به هم نریزه )که نباید ادغام بشن از روشی که گفتین میریم جلو اما من چند تا مشکل اساسی پیدا کردم که ممنون میشم بازم یه توضیح بدید شاید من بهشون توجه نکردم
۱/ برای پیدا کردن k امین عنصر توی یه لیست مرتب نیازی به جستجوی دودویی نیست و میشه به اندیس مورد نظر روجوع کرد که از [tex]O(1)[/tex] میشه که دیگه نیازی نداری [tex]A[i][/tex] چک کنی که توی آرایه A چندمین عنصر میشه.
۲/ دومین نکته روشی که شما گفتید ما رو به k امین عنصر نمیرسونه( دلیل: اول اینکه ما میخواهیم جستجوی دودویی رو با چه مقداری مقایسه کنیم ما که مقادیر آرایه رو نمیدونیم از کجا بدونیم که با چه مقادیری مقایسه بشه (" حالا عکسی رو که پایین دادم بگیرش و نگاش کن و ببینم با چه مقداری جستجوی دودویی میخوای بری و به سومین عنصر برسی.... به فرض یکی از عناصر خود آرایه که [tex]A[i][/tex] باشه..؟ خوب این که فقط تکلیف این خونه رو به ما میگه که جایگاهش تو B کجاست من که نشون دادم امکان داره هر جای آرایه قرار بگیره بازم ج اشتباه میشه و با چه فلسفه ای ما بدونیم [tex]A[i][/tex] حتما کاندید هست واسه جستجو درون آرایه B اگر بخواهیم تکلیف همه‌ی [tex]A[i][/tex] رو بدونیم هزینه [tex]O(n/2*logn)[/tex] میشه که برابر با [tex]O(nlogn)[/tex] که حتی از [tex]O(n)[/tex] بیشتر میشه! ") تا به k امین عنصر برسیم! دوم اینکه الگوریتمی که شما گفتید ۱ بار بر روی a و یک بار بر روی b جستجوی دودویی انجام دادید ( به صورت جدا از هم ... جداگانه) که هزینه‌ها با هم ضرب نمیشن بلکه جمع میشن [tex]O(log n)[/tex] + [tex]O(log n)[/tex] = [tex]O(log n)[/tex]
دوباره یه نگاه به عکس بنداز خودت حرفی رو که زدی رو این شکل انجام بده, اصلا با چی میخوای مقایسه کنی جستجوی دودویی رو گرچه لیست مرتب هست و یه راست میتونی بری سر اغ اندیس ولی ۲ تا آرایه شده بحث فرق داره. ببینم به سومین عنصر میرسی با این روشی که گفتی.... بازم من میگم شاید الگوریتمی با [tex]O(log n)[/tex] این پیدا بشه که من نمیدونم اما روش شما اشتباه هست.
من گفته های شما رو چک کردم و مو به مو انجام دادم . خوشحال میشم یکی از دوستان ج صحیح رو بده
لطفا این کارایی رو که گفتم حتما انجام بدین و چک کنین
دوستان دقیقا یادمه که یافتن کلید میانه در این شرایط با log n به دست میومد که میانه خودش یه کلید kام هست!
حمیدجان با توضیحاتی که شما دادی (مخصوصا راجع به پیچیدگی زمانی الگوریتمی که من گفتم) به نظر میرسه شما اصلا روش من رو متوجه نشدی، یه بار دیگه توضیح میدم اگه به توافق رسیدیم روش اصلی رو هم توضیح میدم.
(۱۳ اسفند ۱۳۸۹ ۰۵:۵۵ ب.ظ)hamidj نوشته شده توسط: 1. برای پیدا کردن k امین عنصر توی یه لیست مرتب نیازی به جستجوی دودویی نیست و میشه به اندیس مورد نظر روجوع کرد که از [tex]O(1)[/tex] میشه که دیگه نیازی نداری [tex][tex]A[i][/tex][/tex] چک کنی که توی آرایه A چندمین عنصر میشه.
اول اینکه من گفتم برای پیدا کردن عدد x در آرایه باید از BS استفاده کنیم نه برای پیدا کردن kامین عنصر. یعتی مثلا توی همین عکسی که خود شما فرستادین برای پیدا کردن ۱۳۹۰ توی آرایه دوم باید از BS استفاده کنیم.
(۱۳ اسفند ۱۳۸۹ ۰۵:۵۵ ب.ظ)hamidj نوشته شده توسط: 2. دومین نکته روشی که شما گفتید ما رو به k امین عنصر نمیرسونه( دلیل: اول اینکه ما میخواهیم جستجوی دودویی رو با چه مقداری مقایسه کنیم ما که مقادیر آرایه رو نمیدونیم از کجا بدونیم که با چه مقادیری مقایسه بشه (" حالا عکسی رو که پایین دادم بگیرش و نگاش کن و ببینم با چه مقداری جستجوی دودویی میخوای بری و به سومین عنصر برسی.... به فرض یکی از عناصر خود آرایه که [tex][tex]A[i][/tex][/tex] باشه..؟ خوب این که فقط تکلیف این خونه رو به ما میگه که جایگاهش تو B کجاست من که نشون دادم امکان داره هر جای آرایه قرار بگیره بازم ج اشتباه میشه و با چه فلسفه ای ما بدونیم [tex][tex]A[i][/tex][/tex] حتما کاندید هست واسه جستجو درون آرایه B اگر بخواهیم تکلیف همه‌ی [tex][tex]A[i][/tex][/tex] رو بدونیم هزینه [tex]O(n/2*logn)[/tex] میشه که برابر با [tex]O(nlogn)[/tex] که حتی از [tex]O(n)[/tex] بیشتر میشه! ") تا به k امین عنصر برسیم! دوم اینکه الگوریتمی که شما گفتید ۱ بار بر روی a و یک بار بر روی b جستجوی دودویی انجام دادید ( به صورت جدا از هم ... جداگانه) که هزینه‌ها با هم ضرب نمیشن بلکه جمع میشن [tex][tex]O(log n)[/tex][/tex] + [tex][tex]O(log n)[/tex][/tex] = [tex][tex]O(log n)[/tex][/tex]
هیچ کدوم از پیچیدگی زمانی هایی که گفتید درست نیست. ما نه برای کل [tex][tex]A[i][/tex][/tex]ها در B جستجو می کنیم و نه اینکه یکبار بر روی A و یکبار بر روی B. ببینید روش کلی اینطوریه، ما روی عناصر [tex][tex]A[i][/tex][/tex] جستجوی دودویی می کنیم( دقیقترش رو پایینتر میگم )و به ازای هر عنصر در A که در جستجو بهش بر می خوریم یک بار روی B جستجو می کنیم پس ۲ تا جستجو تو در تو هستند و هزینه‌ها در هم ضرب میشه
*امیدوارم کلیت رو خوب توضیح داده باشم و دیگه توش مشکلی نداشته باشیم
(۱۳ اسفند ۱۳۸۹ ۰۵:۵۵ ب.ظ)hamidj نوشته شده توسط: دوباره یه نگاه به عکس بنداز خودت حرفی رو که زدی رو این شکل انجام بده, اصلا با چی میخوای مقایسه کنی جستجوی دودویی رو گرچه لیست مرتب هست و یه راست میتونی بری سر اغ اندیس ولی ۲ تا آرایه شده بحث فرق داره. ببینم به سومین عنصر میرسی با این روشی که گفتی.... بازم من میگم شاید الگوریتمی با [tex][tex]O(log n)[/tex][/tex] این پیدا بشه که من نمیدونم اما روش شما اشتباه هست.
بینید ما روی مقادیر عناصر آرایه‌ی A جستجوی دودویی انجام نمیدیم بذارید یه طور دیگه الگوریتم رو مطرح کنیم. فرض کنید یه آرایه C داریم که [tex]C[i][/tex] برابر میشه با اندیس عنصر [tex][tex]A[i][/tex][/tex] در آرایه ادغام شده (آرایه ای که از ادغام ۲ آرایه A و B بدست می آید) مثلا اگر در شکلی که شما فرستادید آرایه‌ی پایینی را A در نظر بگیریم آرایه‌ی C می شود همان اعدادی که شما در زیر آرایه‌ی A نوشته اید. (فعلا فرض کنید آرایه‌ی C را از ابتدا می سازیم که خب پیچیدگی زمانی زیاد می شود ولی بعد ثابت می کنیم که لازم نبوده همه را بسازیم )می دانیم که برای یافتن [tex]C[i][/tex] کافی است روی آرایه‌ی B یک جستجوی دودویی با مقدار [tex][tex]A[i][/tex][/tex] بزنیم تا ببینیم که [tex][tex]A[i][/tex][/tex] از چند عنصر در B بزرگتر است( فرض کنید جواب میشود j )پس داریم [tex]C[i] = i j[/tex]( با یک مثال از شکل خودتون، مطلب مفهوم خواهد بود )در نتیجه برای یافتن هر عنصر C باید [tex][tex]O(log n)[/tex][/tex] هزینه کنیم. حال آرایه‌ی C رو در نظر بگیرید با مقدار K روی این آرایه جستجوی دودویی انجام می دهیم یعنی عناصر C رو با K مقایسه می کنیم. که میشه [tex][tex]O(log n)[/tex][/tex] اگه دقیقا خود K پیدا شد مثلا [tex]c[i]=k[/tex] اونوقت [tex][tex]A[i][/tex][/tex] همون عنصر Kام آرایه‌ی ادغام شدس و اگه هم K در C نبود یعنی Kامین عنصر در A نیست و اونوقت یکبار همین مراحل رو برای آرایه‌ی B انجام میدیم.
و اما در مورد پیچیدگی زمانی: همونطور که میدونیم آرایه C صعودیه و میشه از الگوریتم BS روش استفاده کرد که از [tex][tex]O(log n)[/tex][/tex] هستش، خوب ما وقتی که می خوایم از این الگوریتم استفاده کنیم لازم نیست که همه‌ی مقادیر آرایه رو بدونیم و میشه هربار که به یه عنصر نیاز داشتیم اون رو حساب کنیم. قبلا گفتیم که حساب کردن یه خونه از آرایه‌ی C از [tex][tex]O(log n)[/tex][/tex] هستش و چون در BS به [tex][tex]O(log n)[/tex][/tex] تا از خونه های C نیاز داریم پس میشه [tex]O(log^{2} n)[/tex]
امیدوارم توضیحات کامل و واضح بوده باشه و حوصله‌ی خوندنش رو داشته باشید
(۱۴ اسفند ۱۳۸۹ ۰۲:۴۶ ق.ظ)poopi نوشته شده توسط: حمیدجان با توضیحاتی که شما دادی (مخصوصا راجع به پیچیدگی زمانی الگوریتمی که منما عدد X رو نداریم و مسئله میگه مقداره X که چهارمین عنصر یا هفتمین عنصر این دو آرایه هست به ما بده....
گفتم) به نظر میرسه شما اصلا روش من رو متوجه نشدی، یه بار دیگه توضیح میدم اگه به توافق رسیدیم روش اصلی رو هم توضیح میدم.
[quote='poopi' pid='18795' dateline='1299245103']
مثال مشابه اینه که یه آرایه‌ی مرتب با n عنصر داریم و می خوایم ببینیم عدد x در کجای آرایه هست که طبق استدلال شما چون x در همه جای آرایه می تونه باشه پس باید همه‌ی خونه‌ها رو چک کنیم و میشه از در حالی که می دونیم با یه BS میشه x رو پیدا کرد با [tex]O(logn)[/tex]
(۱۳ اسفند ۱۳۸۹ ۰۵:۵۵ ب.ظ)poopi نوشته شده توسط: هیچ کدوم از پیچیدگی زمانی هایی که گفتید درست نیست.پیچیدگی هایی که گفته بودم درست بودند ولی منظور شما رو خوب نفهمیده بودم( خداییش خیلی بد توضیح میدی
)واسه همین این پیچیدگی‌ها بدست اومد دیگه...(۱۳ اسفند ۱۳۸۹ ۰۵:۵۵ ب.ظ)poopi نوشته شده توسط: ببینید روش کلی اینطوریه، ما روی عناصر [tex]A[i][/tex] جستجوی دودویی می کنیم( دقیقترش رو پایینتر میگم )و به ازای هر عنصر در A که در جستجو بهش بر می خوریم یک بار روی B جستجو می کنیم پس ۲ تا جستجو تو در تو هستند و هزینه‌ها در هم ضرب میشههمچین الگوریتمی که در کل گفتی قبول دارم که انقدر هزینه داره و اگر منظورتو بد فهمیدم ببخشید
*امیدوارم کلیت رو خوب توضیح داده باشم و دیگه توش مشکلی نداشته باشیم
[tex] O(logn) * O(logn) [/tex]=[tex]O(log^{2} n)[/tex]
واقعا از اینجا به بعدش خیلی بد گفتی پوپی جان
۳۰بار خوندم ولی گفتم قبل از ج دادن از خودت بپرسم بهتره تا دوباره جواب هایی که هیچ ربطی به صحبت های شما نداره بدم
(۱۳ اسفند ۱۳۸۹ ۰۵:۵۵ ب.ظ)poopi نوشته شده توسط: فرض کنید یه آرایه C داریم که [tex]C[i][/tex] برابر میشه با اندیس عنصر [tex]A[i][/tex] در آرایه ادغام شده (آرایه ای که از ادغام ۲ آرایه A و B بدست می آید) مثلا اگر در شکلی که شما فرستادید آرایه‌ی پایینی را A در نظر بگیریم آرایه‌ی C می شود همان اعدادی که شما در زیر آرایه‌ی A نوشته اید.واقعا اینجا رگ به رگ شد مغزم
۲تا برداشت کردم اگه بگی آرایه C کدومش هست ممنون میشم۱/ آرایه B و A ادغام میشن با هم ... و آرایه C به صورت صعودی تشکیل میدن . لایت قرمز اول
۲/ یه کپی از آرایه A میزنیم و نام اونو C میزاریم آخه حرفی از B توی لایت قرمز دوم گفته نشده و گفتید میشود همان A
اگه منظورت دومی بود حالا ما یه C داریم که مرتب هست و با [tex]O(1)[/tex] به انیدس مورد نظر میریم و مقدار X رو به دست میاریم
اینجوری C[k] = x
اما گفتی نیازی به C نیست که بعدا اثبات میکنی
[/color](۱۳ اسفند ۱۳۸۹ ۰۵:۵۵ ب.ظ)poopi نوشته شده توسط: حال آرایه‌ی C رو در نظر بگیرید با مقدار K روی این آرایه جستجوی دودویی انجام می دهیم یعنی عناصر C رو با K مقایسه می کنیم. که میشه [tex]O(logn)[/tex] اگه دقیقا خود K پیدا شد مثلا [tex]C[i]=k[/tex] اونوقت همون عنصر [tex]A[i][/tex]تو این K رو از کجا میاری
من رو اینا خیلی مشکل دارم پوپیمسئله به ما گفته که k امین عنصر رو پیدا کن و بگو مقدارش چنده . همون X.
مثلا K=3 حالا X چند؟
تو گفتی [tex]C[i]=K[/tex] بود پس k امین عنصره
به فرض توی [tex]C[i][/tex] برابر با ۱۳۹۰ هست تو از کجا میفهمی ۱۳۹۰ = ۴ هست... اصلا هیچی error دادم.
فکر کنم بد منظورتو فهمیدم یه جورایی اینم روشن کن که منظورت چیه؟
(۱۳ اسفند ۱۳۸۹ ۰۵:۵۵ ب.ظ)poopi نوشته شده توسط: (فعلا فرض کنید آرایه‌ی C را از ابتدا می سازیم که خب پیچیدگی زمانی زیاد می شود ولی بعد ثابت می کنیم که لازم نبوده همه را بسازیم )اثبات نشده اما فعلا لازم نیست اگر لازم شد راجبه اینم صحبت میکنیم. گرچه مهمترینش همینه.
حمیدجان وقتی پستت رو خوندم کلی خندیدم چون به نظر میرسه که اصلا صحبت هام برات مفهوم نبوده و جالب‌تر اینکه منم صحبت های شما رو خوب متوجه نمیشم. حالا ۲ راه داریم
۱) کلا بیخیال شیم چون بنظر میرسه زبون هم رو خوب نمی فهمیم (اصلا با این روش موافق نیستم)
۲) ریز ریز باهم جلو بریم تا ذهن هامون به هم نزدیک بشه
برای شروع بذار اول سر آرایه‌ی C به توافق برسیم.
یه آرایه‌ی Final در نظر بگیر به اینصورت که A و B رو ادغام می کنیم و بعد مرتب میکنیم. از این به بعد در جاهایی که لازم داشتیم از این اسم استفاده می کنیم( این همون برداشت اول شما از آرایه‌ی C هستش که اشتباه بود: rolleyes
و اما C، یه آرایه به اندازه‌ی آرایه‌ی A در نظر بگیر. این آرایه رو به اینصورت میسازیم. برای ساختن [tex]C[i][/tex] میریم توی آرایه‌ی A و [tex]A[i][/tex] رو می بینیم چه عددی هستش. فرض کن عدد a هست. بعد میریم توی Final میبینیم a چندمین عنصر هستش. فرض کن rامین عنصره بعد قرار میدیم [tex]C[i]=r[/tex] مثلا توی همین شکلی که فرستادی فرض کن آرایه‌ی پایینی A هست. بعد می خوایم [tex]C[2][/tex] رو حساب کنیم. داریم [tex]A[2] = 1390[/tex] حالا آرایه‌ی Final رو برای این مثال در نظر بگیر بعد توی اون آرایه ۱۳۹۰ میشه ۵امین عنصر پس قرار میدیم [tex]C[2] = 5[/tex].
*این آرایه ای که میسازیم میشه همون اعدادی که خود شما زیر آرایه نوشتی
اگه تا اینجا رو متوجه شدی بقیه رو بخون اگه نه که سر همون قسمت قبلی صحبت کنیم
حالا چه جوری میشه بدون ساختن آرایه‌ی Final آرایه‌ی C رو ساخت؟ گفتیم [tex]C[i]=r[/tex] یعنی اینکه [tex]A[i][/tex]، rامین عنصر در آرایه‌ی Final هست. خوب این معادل اینه که بگیم [tex]A[i][/tex] از r-1 تا از اعداد موجود در ۲ آرایه‌ی A و B بزرگتره.
حالا چه جوری میشه این مقدار رو حساب کرد؟ برای A که [tex]A[i][/tex] دقیقا از i-1 عنصر بزرگتره و برای B هم که این مقدار رو با یک BS می فهمیم، و نهایتا دوتا عدد رو با هم جمع می کنیم و میشه تعداد اعدادی که [tex]A[i][/tex] از اونها بزرگتره فرض کن میشه x وخب داریم که x = r - 1 پس C[i] = x + 1 مفهوم بود؟
پس میشه هر عنصر از C رو با [tex]O(logn)[/tex] ساخت.
خدا خیرت بده همون اول اینجوری توضیح میدادی .
تا اونجایی که گفتی متوجه شدم
اما یه سوال واسه ساختنه C مگه نباید از تک تک عناصر A استفاده کرد و در B چک کرد ؟
ببخشید یکم دیر شد
(۱۵ اسفند ۱۳۸۹ ۰۱:۲۱ ق.ظ)hamidj نوشته شده توسط: خدا خیرت بده همون اول اینجوری توضیح میدادی .اگه بخوای کل آرایه رو بسازی آره باید از کل A استفاده کنی و میشه از [tex]O(nlogn)[/tex] ولی طبق توضیحاتی که خواهم داد میبینی که لازم نیست کل C رو بسازیم.
تا اونجایی که گفتی متوجه شدم
اما یه سوال واسه ساختنه C مگه نباید از تک تک عناصر A استفاده کرد و در B چک کرد ؟
ادامه‌ی مطلب:
گفتیم اگه C[i] = r باشه یعنی اینکه [tex]A[i][/tex]، rامین عنصر در آرایه‌ی Final هست. پس وقتی که دنبال kامین عنصر از آرایه‌ی Final می گردیم معادل اینه که می خواهیم C[i] = k رو پیدا کنیم. یعنی یک i پیدا کنیم که به ازای اون C[i] = k باشه و در این صورت [tex]A[i][/tex] همون kامین عنصر در آرایه‌ی Final هست.
*توجه داشته باشین که ما می خوایم بدون ساختن آرایه‌ی Final این عنصر رو پیدا کنیم چون برای ساختن آرایه‌ی Final پیچیدگی زمانی از [tex]O(n)[/tex] لازمه که برای راه حل ما پیچیدگی زیادیه.
خب حالا می دونیم که آرایه‌ی C صعودیه و ما می خوایم یه i پیدا کنیم که C[i] = k و k هم که در مسئله داده شده این دقیقا معادل همون جستجوی دودویی هست. و با یه جستجوی دودویی می تونیم ایندکس مناسب و در نتیجه جواب مسئله رو پیدا کنیم.
*اگه در جستجوی دودویی هیچ C[i] = k پیدا نشد یعنی kامین عنصر در A نبوده و یک بار همه‌ی مراحل رو برای B تکرار می کنیم.
اگه تا اینجا رو متوجه شدین میریم سراغ قسمت آخر:
پیچیدگی زمانی:
میدونیم که برای جستجوی دودویی در آرایه‌ی C باید حدودا logn خونه از C رو بررسی یا همون [tex]O(logn)[/tex]، اگه به یک خونه از آرایه‌ی C در جستجو سر نزنیم. (می دونیم که خیلی از خونه‌ها اینطوری هستن. یعنی تو BS اصلا سراغشون نمیریم) اصلا نیازی نیست که اون خونه رو بسازیم چون هیچ جای دیگه هم بهش نیاز نداریم. پس به جای اینکه اول آرایه‌ی C رو بطور کامل بسازیم و بعد از BS استفاده کنیم. شروع می کنیم و جستجوی دودویی رو انجام میدیم و به هر خونه از C که رسیدیم ابتدا مقدارش رو حساب می کنیم و بعد، از اون مقدار برای ادامه‌ی جستجو استفاده می کنیم.
همونطور که گفتیم ساختن یه خونه از آرایه‌ی C از [tex]O(logn)[/tex] هستش و چون در BS تعداد خونه هایی که بررسی میشن از [tex]O(logn)[/tex] هستن پس در کل پیچیدگی زمانی الگوریتم از [tex]O(log^{2}n)[/tex] هستش.
تمام