hashMap رو نمیشه توی این موقعیت و برای این سوال به کار برد. شما تابع hash رو چه طور میخوای معرفی کنی که دو عضو غیر همتا هیچ برخوردی با هم نداشته باشند؟ دقت کنید که ما هیچ اطلاعی از نوع دادههای دو لیست نداریم. اگر به فرض مثال میدونستیم که همه داده‌ها عدد صحیح هستند و ... میشد با برخی کارها الگوریتم از مرتبه n ارایه داد اما الان چنین فرضی رو نمیشه کرد. فرض کنید که اعداد داخل آرایه از نوع اعشاری با تعداد بی نهایت اعشار باشند. شما چه hashMap ای رو میتونی طراحی کنی که بتونه این مسئله رو حل کنه؟ اصلاً این خودش یه مسئله NP هست که بشه یه ترتیب dictionary برای این اعداد پیدا کرد. چرا که بین هر دو عدد میتونه یه عدد دیگه قرار بگیره. در مورد مصاحبه شرکتها و غیره:
متد ۱ اش: که پیچیدگی مرتبسازی رو غلط نوشته! nlogn هست نه logn.
متد ۲ اش: با فرض مقدار صحیح بودن از hashMap استفاده کرده که کاری بس آسان و شدنی است. اما با فرضهای دیگه محال و غیر ممکن است.
سوال ۵۵ ساختمان داده:
فرض میکنیم n=16 پس ما چهار تا عنصر داریم فرض کنیم هر چهر عنصر ما عدد ۲ باشد.
اگر از روش هش استفاده کنیم(با توجه به فصل ۱۱ کتاب کورمن میدانیم ۳ روش هش با ادرس دهی باز عبارتند از ۱-خطی ۲- مجذوری ۳- مضاعف) اگر از روش زنجیر استفاده کنیم چون گفته عناصر تکراری هیچ فرقی باهم ندارند برای درج ما چهار بار باید در خانه ۲ درج کنیم یعنی اگر تمام عناصر تکراری باشد بهn به توان یک دوم برای درج نیاز خواهیم داشت. پس روش هش جواب نمیدهد. در ضمن اگر از هر کدام از ۳ روش استفاده کنیم باز همون زمان بالا برقرار خواهد بود.
با توجه به فصل ۱۴ کتاب کورمن و با استفاده از درخت آماره پویا هر سه عمل جواب lgn میباشد.
با این اوصاف گزینه ۳ درست است.
(۰۴ اسفند ۱۳۸۹ ۰۱:۳۶ ب.ظ)www نوشته شده توسط: سوال ۵۵ ساختمان داده:موقعی که الگوریتم بهتری داریمO(1) گزینه ۳ که قابل قبول نیست!
فرض میکنیم n=16 پس ما چهار تا عنصر داریم فرض کنیم هر چهر عنصر ما عدد ۲ باشد.
اگر از روش هش استفاده کنیم(با توجه به فصل ۱۱ کتاب کورمن میدانیم ۳ روش هش با ادرس دهی باز عبارتند از ۱-خطی ۲- مجذوری ۳- مضاعف) اگر از روش زنجیر استفاده کنیم چون گفته عناصر تکراری هیچ فرقی باهم ندارند برای درج ما چهار بار باید در خانه ۲ درج کنیم یعنی اگر تمام عناصر تکراری باشد بهn به توان یک دوم برای درج نیاز خواهیم داشت. پس روش هش جواب نمیدهد. در ضمن اگر از هر کدام از ۳ روش استفاده کنیم باز همون زمان بالا برقرار خواهد بود.
با توجه به فصل ۱۴ کتاب کورمن و با استفاده از درخت آماره پویا هر سه عمل جواب lgn میباشد.
با این اوصاف گزینه ۳ درست است.
نقل قول: سوال ۵۵ ساختمان داده:
فرض میکنیم n=16 پس ما چهار تا عنصر داریم فرض کنیم هر چهر عنصر ما عدد ۲ باشد.
اگر از روش هش استفاده کنیم(با توجه به فصل ۱۱ کتاب کورمن میدانیم ۳ روش هش با ادرس دهی باز عبارتند از ۱-خطی ۲- مجذوری ۳- مضاعف) اگر از روش زنجیر استفاده کنیم چون گفته عناصر تکراری هیچ فرقی باهم ندارند برای درج ما چهار بار باید در خانه ۲ درج کنیم یعنی اگر تمام عناصر تکراری باشد بهn به توان یک دوم برای درج نیاز خواهیم داشت. پس روش هش جواب نمیدهد. در ضمن اگر از هر کدام از ۳ روش استفاده کنیم باز همون زمان بالا برقرار خواهد بود.
با توجه به فصل ۱۴ کتاب کورمن و با استفاده از درخت آماره پویا هر سه عمل جواب lgn میباشد.
با این اوصاف گزینه ۳ درست است.
موقعی که الگوریتم بهتری داریمO(1) گزینه ۳ که قابل قبول نیست!
الگوریتم بهتر را میشه توضیح بدهید؟
(۰۴ اسفند ۱۳۸۹ ۰۲:۲۵ ب.ظ)www نوشته شده توسط:دکتر تنهایی که گفتن.نقل قول: سوال ۵۵ ساختمان داده:
فرض میکنیم n=16 پس ما چهار تا عنصر داریم فرض کنیم هر چهر عنصر ما عدد ۲ باشد.
اگر از روش هش استفاده کنیم(با توجه به فصل ۱۱ کتاب کورمن میدانیم ۳ روش هش با ادرس دهی باز عبارتند از ۱-خطی ۲- مجذوری ۳- مضاعف) اگر از روش زنجیر استفاده کنیم چون گفته عناصر تکراری هیچ فرقی باهم ندارند برای درج ما چهار بار باید در خانه ۲ درج کنیم یعنی اگر تمام عناصر تکراری باشد بهn به توان یک دوم برای درج نیاز خواهیم داشت. پس روش هش جواب نمیدهد. در ضمن اگر از هر کدام از ۳ روش استفاده کنیم باز همون زمان بالا برقرار خواهد بود.
با توجه به فصل ۱۴ کتاب کورمن و با استفاده از درخت آماره پویا هر سه عمل جواب lgn میباشد.
با این اوصاف گزینه ۳ درست است.
موقعی که الگوریتم بهتری داریمO(1) گزینه ۳ که قابل قبول نیست!
الگوریتم بهتر را میشه توضیح بدهید؟
اون روش به نظر من نمیشه کتاب مرجع کتاب کورمن هستش تو اونم اینو نوشته نظرات شخصی جواب نمیده.
لااقل بجای اینکه از گفتن این حرفا یه سر میرفتین کورمنو میخوندین.
امیدوارم که موفق باشید.
(۰۴ اسفند ۱۳۸۹ ۰۱:۴۳ ق.ظ)admin نوشته شده توسط: hashMap رو نمیشه توی این موقعیت و برای این سوال به کار برد. شما تابع hash رو چه طور میخوای معرفی کنی که دو عضو غیر همتا هیچ برخوردی با هم نداشته باشند؟ دقت کنید که ما هیچ اطلاعی از نوع دادههای دو لیست نداریم. اگر به فرض مثال میدونستیم که همه داده‌ها عدد صحیح هستند و ... میشد با برخی کارها الگوریتم از مرتبه n ارایه داد اما الان چنین فرضی رو نمیشه کرد. فرض کنید که اعداد داخل آرایه از نوع اعشاری با تعداد بی نهایت اعشار باشند. شما چه hashMap ای رو میتونی طراحی کنی که بتونه این مسئله رو حل کنه؟ اصلاً این خودش یه مسئله NP هست که بشه یه ترتیب dictionary برای این اعداد پیدا کرد. چرا که بین هر دو عدد میتونه یه عدد دیگه قرار بگیره. در مورد مصاحبه شرکتها و غیره:
متد ۱ اش: که پیچیدگی مرتبسازی رو غلط نوشته! nlogn هست نه logn.
متد ۲ اش: با فرض مقدار صحیح بودن از hashMap استفاده کرده که کاری بس آسان و شدنی است. اما با فرضهای دیگه محال و غیر ممکن است.
البته اگر اعداد double هم باشند فکر میکنم مشکلی برای hash کردنشون وجود نداره. چون میتونیم این اعداد double رو به صورت یک عدد مثلا ۶۴ بیتی درنظر بگیریم و بعد عملیات hash رو روی داده‌ها انجام بدیم!
در مورد سوال ۵۵ من این نظرم مینویسمو بس اگراز روش هش با الگوریتم گفته شده استفاده کنیم برای پیاده سازی این کد باید یه حلقه از ۱ تا رادیکال ان بنویسی و در درون حلقه شرط برابری مقدار را با یکی از خانه‌ها را انجام دهی که اگر با هر خونه ای برابر شد یک واحد در درج به ان اضافه یا در حذف کم کنی و در جستجو هم بگردی با این اوصاف جواب این حلقه میشه رادیکال ان. این تفسیر من از الگوریتم شماست. اگه اشتبا میکنمشماتوضیح دهید.[/php]
گویا شما hash رو درست متوجه نشدین! من شیوه دسترسی بر اساس o1 رو توضیح دادم. خیلی واضح و مشخصه این سوال و جای هیچ شک و شبههای نداره.
در مورد کتاب کورمن: دوستان به جای ارجاع کردن وقت و بی وقت به این کتاب به شرایط مسایل دقت کنند. کتاب کورمن هم میتونه اشکال داشته باشه. ما اینجا دلایل عقلی میآوریم و دوستان جوابهای نقلی!
کی گفته تنها تابع hash رو به سه روش میشه ساخت؟ به هر روشی میشه این تابع رو ساخت و اصلاً این ساختن این توابع برای خودش صنعتی مهم به حساب میاد! اگه به همین سادگی و سر راستی بود که بسیاری از شرکتها واسه به دست آوردن اعداد اول بزرگ پولهای هنگفت هزینه نمیکردن. من یه تابع hash خیلی ساده( به قول شما خطی) پیشنهاد دادم و شما اصرار بر غلط بودن دارید.
در نظر داشته باشید که من کنکوری نیستم و ذینفع جوابها هم نیستم. تنها به اصرار دوستان توی این مباحث شرکت کردم
من خودم این سوال اجتماع رو اشتباه زدم چون به مرتب بودن دو لیست دقت نکردم ولی قبلا یه سوال دیده بودم مشابه این سوال که میخواست میانه رو پیدا کنه و logn میشد(البته در پایه ۴/۳)
(۰۴ اسفند ۱۳۸۹ ۰۱:۴۳ ق.ظ)admin نوشته شده توسط: hashMap رو نمیشه توی این موقعیت و برای این سوال به کار برد. شما تابع hash رو چه طور میخوای معرفی کنی که دو عضو غیر همتا هیچ برخوردی با هم نداشته باشند؟ دقت کنید که ما هیچ اطلاعی از نوع دادههای دو لیست نداریم. اگر به فرض مثال میدونستیم که همه داده‌ها عدد صحیح هستند و ... میشد با برخی کارها الگوریتم از مرتبه n ارایه داد اما الان چنین فرضی رو نمیشه کرد. فرض کنید که اعداد داخل آرایه از نوع اعشاری با تعداد بی نهایت اعشار باشند. شما چه hashMap ای رو میتونی طراحی کنی که بتونه این مسئله رو حل کنه؟ اصلاً این خودش یه مسئله NP هست که بشه یه ترتیب dictionary برای این اعداد پیدا کرد. چرا که بین هر دو عدد میتونه یه عدد دیگه قرار بگیره.
سلام
کلا وقتی صحبت از کامپیوتر هست، همیشه محدودیتی هم وجود داره. این مورد رو در نظر بگیرید که اگر اعداد اعشاری با بینهایت رقم اعشار داشیم حتی نمی شد این اعداد رو با nlogn مرتب کرد. (با روش های مبتی بر مقایسه) چون زمان مقایسه هم دو عنصر را دیگه نمی شد ثابت در نظر گرفت. طراح حتما در ذهن خودش فرض ثابت بودن زمان مقایسه عناصر رو داشته چون در غیر این صورت تست کلا غلط خواهد بود. در رابطه با روش hash کردن داده های مختلف، می شه هر عنصر با هر نوع داده ای رو به صورت دنباله ای از ۰ و ۱ در نظر گرفت و اون وقت دیگه hash کردن کاره دشواری نیست. (همون چیزی که خودتون هم اشاره کردید) بنابراین اگر در حالت میانگین بخواهیم بررسی کنیم، می شه پراکندگی عناصر در خانه های جدول hash را برابر فرض کرد. بنابراین من هم فکر می کنم که گزینه ۲ صحیح باشه. من خودم گزینه ۱ رو زدم اما با توجه به این که ما هیچ شناختی از ماهیت داده‌ها نداریم قاعدتا نمی شه تابع بهینه hash رو در تحلیل مد نظر قرار داد.