سلام
بدترین حالت میشه که ما یکی مرتب کنیم و دو آرایه رو با هم ادعام کنیم که میشه nlgn

واسه حالت متوسط ما باید از hash table استفاده کنیم که ابتدا یکی از آرایه ها رو درج میکنیم و واسه آرایه دومی n بار به طور متوسط هر بار [tex]O(1)[/tex] چک میکنیم که آیا این عنصر در جدول هش وجود داره یا نه! مه در مجموع میشه n

(۰۷ بهمن ۱۳۹۲ ۰۱:۱۷ ق.ظ)Riemann نوشته شده توسط:  سلام
بدترین حالت میشه که ما یکی مرتب کنیم و دو آرایه رو با هم ادعام کنیم که میشه nlgn

واسه حالت متوسط ما باید از hash table استفاده کنیم که ابتدا یکی از آرایه ها رو درج میکنیم و واسه آرایه دومی n بار به طور متوسط هر بار [tex]O(1)[/tex] چک میکنیم که آیا این عنصر در جدول هش وجود داره یا نه! مه در مجموع میشه n

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

(۰۷ بهمن ۱۳۹۲ ۰۱:۱۷ ق.ظ)Riemann نوشته شده توسط:  سلام
بدترین حالت میشه که ما یکی مرتب کنیم و دو آرایه رو با هم ادعام کنیم که میشه nlgn

واسه حالت متوسط ما باید از hash table استفاده کنیم که ابتدا یکی از آرایه ها رو درج میکنیم و واسه آرایه دومی n بار به طور متوسط هر بار [tex]O(1)[/tex] چک میکنیم که آیا این عنصر در جدول هش وجود داره یا نه! مه در مجموع میشه n

ببخشید یه سوال! تحلیل هش یکم مشکل اونم واسه حالتی که بخوایم ۲n عضو رو به یک ارایه n عضوی هش کنیم. مسئله برخوردها باعث میشن که تعداد مقایسه ها خیلی بیشتر از n بشه تحلیل شما بیشتر برای بهترین حالت کاربرد داره تا حالت میانگین.

بله این گفته حالت متوسط و فکر کنم هش حالت متوسطش O 1 میشه اگه تابع هش رو درست انتخاب کنیم(uniform) باشه.

(۰۹ بهمن ۱۳۹۲ ۰۲:۱۹ ق.ظ)Riemann نوشته شده توسط:  بله این گفته حالت متوسط و فکر کنم هش حالت متوسطش O 1 میشه اگه تابع هش رو درست انتخاب کنیم(uniform) باشه.

راسته که تستش حذف شده! اگر تحلیل شما درست باشه چرا حذف شده؟؟؟

این سوال رو سازمان سنجش حذف کرده بودا !

مطمئنید از جوابتون، قاعدتا باید یه اشکالی داشته باشه