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

درود

این سوال رو سازمان سنجش حذف کرده، احتمالا چون جواب تو گزینه ها نبوده

حالا کسی می دونه جوابش چی میشه؟

(06 بهمن 1392 10:51 ق.ظ)tayebe68 نوشته شده توسط: [ -> ]درود

این سوال رو سازمان سنجش حذف کرده، احتمالا چون جواب تو گزینه ها نبوده

حالا کسی می دونه جوابش چی میشه؟

درود
مشابه این سوال مطرح شده بود
بدترین حالتش میشه nlogn میشه به این شکل که اول یه آرایه مرتب میشه بعد از آرایه نامرتب هر بار عددی گرفته و بوسیله جستجو دودوئی در آرایه مرتب چک میشه اگه وجود داشت یعنی در هردوتا هست
میانگینم n میشه که با هشینگ پیاده سازی میشه.

(08 بهمن 1392 11:21 ق.ظ)kh.jafarzade نوشته شده توسط: [ -> ]میانگینم n میشه که با هشینگ پیاده سازی میشه.

میشه لطفا توضیح بدید چجوری ؟؟

(08 بهمن 1392 01:23 ب.ظ)tayebe68 نوشته شده توسط: [ -> ]

(08 بهمن 1392 11:21 ق.ظ)kh.jafarzade نوشته شده توسط: [ -> ]میانگینم n میشه که با هشینگ پیاده سازی میشه.

میشه لطفا توضیح بدید چجوری ؟؟

توضیح دقیقی ندیدم ازش جایی..اما چیزی که منو قانع کرد این بود.
با یه حلقه از 1-n و یک جدول درهم ساز با خونهای کافی ویک تابع که مقادیرو بصورت یکنواخت در این خونها پخش کنه!
حالا با هر دور تکرار حلقه 1 مقدار از آرایه اول و یک مقدار از آرایه دوم خونده میشه و تابع درهم ساز روشون اعمال میشه و هرکدوم تو خونه ای از جدول درهم ساز درج میشن و به ازای هر برخوردی که در جدول درهم ساز بوجود بیاد یعنی این مقدار در دو آرایه مشترکه...!

(08 بهمن 1392 08:34 ب.ظ)kh.jafarzade نوشته شده توسط: [ -> ]توضیح دقیقی ندیدم ازش جایی..اما چیزی که منو قانع کرد این بود.
با یه حلقه از ۱-n و یک جدول درهم ساز با خونهای کافی ویک تابع که مقادیرو بصورت یکنواخت در این خونها پخش کنه!
حالا با هر دور تکرار حلقه ۱ مقدار از آرایه اول و یک مقدار از آرایه دوم خونده میشه و تابع درهم ساز روشون اعمال میشه و هرکدوم تو خونه ای از جدول درهم ساز درج میشن و به ازای هر برخوردی که در جدول درهم ساز بوجود بیاد یعنی این مقدار در دو آرایه مشترکه...!

به نظرم درست نیست این همه فرض رو برای یک سوال که جواب رو در حالت کلی می خواد در نظر بگیریم
طبق تعریف hash نمی شه عنوان کرد برای هر دو لیست دلخواه A و B برخورد به معنی تساوی اون دوتاست. مثل 27 و 127 و 227 که براشون برخورد پیش میاد ولی یکی نیستند.
و چون برای عناصر دو لیست هیچ محدودیتی مشخص نشده ، این که بتونیم یک تابع نگاشت تعریف کنیم که به هر عنصر یک شماره یکتا تخصیص بده منتفیه

(08 بهمن 1392 09:02 ب.ظ)tayebe68 نوشته شده توسط: [ -> ]

(08 بهمن 1392 08:34 ب.ظ)kh.jafarzade نوشته شده توسط: [ -> ]توضیح دقیقی ندیدم ازش جایی..اما چیزی که منو قانع کرد این بود.
با یه حلقه از ۱-n و یک جدول درهم ساز با خونهای کافی ویک تابع که مقادیرو بصورت یکنواخت در این خونها پخش کنه!
حالا با هر دور تکرار حلقه ۱ مقدار از آرایه اول و یک مقدار از آرایه دوم خونده میشه و تابع درهم ساز روشون اعمال میشه و هرکدوم تو خونه ای از جدول درهم ساز درج میشن و به ازای هر برخوردی که در جدول درهم ساز بوجود بیاد یعنی این مقدار در دو آرایه مشترکه...!

به نظرم درست نیست این همه فرض رو برای یک سوال که جواب رو در حالت کلی می خواد در نظر بگیریم
طبق تعریف hash نمی شه عنوان کرد برای هر دو لیست دلخواه A و B برخورد به معنی تساوی اون دوتاست. مثل ۲۷ و ۱۲۷ و ۲۲۷ که براشون برخورد پیش میاد ولی یکی نیستند.
و چون برای عناصر دو لیست هیچ محدودیتی مشخص نشده ، این که بتونیم یک تابع نگاشت تعریف کنیم که به هر عنصر یک شماره یکتا تخصیص بده منتفیه

درسته من مطمئن نیستم... اینکه 27 -127-227 براشون برخورد پیش بیاد فکر میکنم بستگی به تابع درهم ساز داشته باشه...و من فرضو بر این گذاشتم که بشه چنین تابعی تعریف کرد که بتونه آدرس یکتا برای هر مقدار تولید کنه جز اینم هیچ راه حل دیگه ای به ذهنم نرسید...!

(08 بهمن 1392 10:32 ب.ظ)kh.jafarzade نوشته شده توسط: [ -> ]درسته من مطمئن نیستم... اینکه ۲۷ -۱۲۷-۲۲۷ براشون برخورد پیش بیاد فکر میکنم بستگی به تابع درهم ساز داشته باشه...و من فرضو بر این گذاشتم که بشه چنین تابعی تعریف کرد که بتونه آدرس یکتا برای هر مقدار تولید کنه جز اینم هیچ راه حل دیگه ای به ذهنم نرسید...!

بله برخورد بین این سه عدد به تابع نگاشتمون بستگی داره، این رو به عنوان مثال فرض کردم

ولی در کل فکر کنم پیدا کردن این تابع نگاشت آرزوی مهندسان آیتی و کامپیوتر باشه، و بشه از توش چند تا مقاله ISI در آورد

(08 بهمن 1392 11:21 ق.ظ)kh.jafarzade نوشته شده توسط: [ -> ]

(06 بهمن 1392 10:51 ق.ظ)tayebe68 نوشته شده توسط: [ -> ]درود

این سوال رو سازمان سنجش حذف کرده، احتمالا چون جواب تو گزینه ها نبوده

حالا کسی می دونه جوابش چی میشه؟

درود
مشابه این سوال مطرح شده بود
بدترین حالتش میشه nlogn میشه به این شکل که اول یه آرایه مرتب میشه بعد از آرایه نامرتب هر بار عددی گرفته و بوسیله جستجو دودوئی در آرایه مرتب چک میشه اگه وجود داشت یعنی در هردوتا هست
میانگینم n میشه که با هشینگ پیاده سازی میشه.

این طوری که جواب تو گزینه ها هست پس چرا حذف شده !!!!!

با هشینگ عناصر یک لیست را درج میکنی (تصادف را با نجیره سازی پیاده میکنی اما نه با زنجیره سازی لیست بلکه برای هر حفره یک

بی اس تی میسازی )

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

الان حالت میانگین این روش چی میشه؟

[tex]O(n)[/tex] یا [tex]O(nlogn)[/tex] ؟

(12 بهمن 1392 11:38 ب.ظ)tayebe68 نوشته شده توسط: [ -> ]الان حالت میانگین این روش چی میشه؟

[tex]O(n)[/tex] یا [tex]O(logn)[/tex] ؟

[tex]O(nlogn)[/tex]