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

اگر در داخل یک آرایه [tex]a\left ( 1...n \right )[/tex] تمام اعداد صحیح صفر تا n به صورت باینری فقط یکبار دیده شوند و فقط عدد صحیح [tex]x\epsilon a\left ( 1...n \right )[/tex] در داخل آرایه نباشد ،در این صورت پیچدگی زمانی که عدد از دست رفته x را میتوان یافت کدام است؟
جواب:[tex]o(n)[/tex]

(16 مهر 1391 12:51 ق.ظ)mahtab_rafiei نوشته شده توسط: [ -> ]اگر در داخل یک آرایه [tex]a\left ( 1...n \right )[/tex] تمام اعداد صحیح صفر تا n به صورت باینری فقط یکبار دیده شوند و فقط عدد صحیح [tex]x\epsilon a\left ( 1...n \right )[/tex] در داخل آرایه نباشد ،در این صورت پیچدگی زمانی که عدد از دست رفته x را میتوان یافت کدام است؟
جواب:[tex]o(n)[/tex]

سلام
مشکلی نیست که ! یه آرایه پر از قبل آماده میکنیم به صورتی که هر عددی که داخل هر خونش هست،همان اندیس آرایه هست
یعنی : a[i]=i بعد این آرایه رو با آرایه خودمون با استفاده از یک حلقه فور چک میکنیم و تست میکنیم که کجا همخوانی نداره
هزینه حلقه هم n میشود.

یک راه ساده تر و البته خلاقانه تر دارم!
اعداد 1 تا n رو با هم جمع کنین
این حاصل رو از مجموع اعداد داخل آرایه کم کنین
جواب به دست اومد!
روش سریع با مرتبه اجرایی خطی

(16 مهر 1391 09:51 ق.ظ)naderx نوشته شده توسط: [ -> ]یه آرایه پر از قبل آماده میکنیم به صورتی که هر عددی که داخل هر خونش هست،همان اندیس آرایه هست
یعنی : a[i]=i بعد این آرایه رو با آرایه خودمون با استفاده از یک حلقه فور چک میکنیم و تست میکنیم که کجا همخوانی نداره
هزینه حلقه هم n میشود.

این روش غلطه
ضمنا اگر بخواییم طوری تغییرش بدیم که درست باشه مرتبه اجرایی خطی نخواهد داشت.
کمی بهش فکر کنین، خودتون میتونین متوجه اشتباه بودنش بشین.
روی سوال نگفته هر عدد تو جای خودشه! پس این چک کردنی که شما گفتین، با مرتبه خطی جواب درستی نخواهد داشت. (چون هر عدد رو باید یه بار با کل آرایه چک کنیم ... البته طبق روش شما)

(18 مهر 1391 01:12 ق.ظ)mohammad-a نوشته شده توسط: [ -> ]یه مسئله: به نظر شما قصد سوال از اینکه گفته اعداد به صورت باینری هستند٬ چی بوده؟ (قصد داشته چه بخشی رو گمراه کنه؟ )

قصدش این بوده که داوطلب فکر کنه باید با تک تک بیت های اعداد کار کنه و چون تعداد بیت های هر عدد زیاد میشه، پس ذهنش اصلا به سمت مرتبه اجرایی خطی نمیره و مرتبه اجرایی بزرگتری رو برای جواب انتخاب میکنه و در نتیجه تو تله طراح میوفته

(18 مهر 1391 12:20 ب.ظ)mohammad-a نوشته شده توسط: [ -> ]فکر کنم در اینصورت٬ [tex]N^2[/tex] میشد. نه؟

بازم بستگی به راه انتخابی داشت. ولی چیزی بین nlogn و n^2 میشه اگه کسی تو این دام بیوفته.

این سوال منظورش اینه که فقط باید از باینری استفاده کنیم و تنها حرکتی که می تونیم بکنیم دستیابی به j امین بیت درایه a[i] هست خوب برای اینکار ما اول بایدتشخیص بدهیم عدد فرده یا زوج پس کافیه به بیت logn ام هر خونه از درایه با مرتبه زمانی o[1] دسترسی پیدا کنیم که اگه تا آخر بریم میشود n حال اگه تعداد عناصر زوج از n/2 یکی کمتر باشه پس معلوم میشه عدد یکی از اعداد زوج آرایه هست وبلعکس .فرض میکنیم زوج باشه خوب حال n/2-1 عدد داریم که ایندفعه باید بیت logn -1 رو چک کنیم توجه کنید در اینجا چون گفته اعداد از یک تا n هستن اینکارو میکنیم . تو این مرحله باز اون دسته ای که بیت log n-1 شان n/4-1 باشه رو دوباره همون حرکتای بالایی رو روش میزنیم با تقسیم و غلبه (کدش هم میشه راحت نوشت) و همینطوری تا n/n پیش میریم که در نهایت میشه n+n/2+ n/4+n/8+...+n/2i که سری 1 تقسیم بر 2 به توان i همانطور که میدونین میشه 2 پس در کل زمانش 2n و از مرتبه o(n) میشه.