سلام دوستان. کسی میتونه اینو برای من توضیح بده که چطوری ۱ میشه؟
ممنون میشم
[attachment=14992]
سلام
بدترین حالت میشه که ما یکی مرتب کنیم و دو آرایه رو با هم ادعام کنیم که میشه 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) باشه.
راسته که تستش حذف شده! اگر تحلیل شما درست باشه چرا حذف شده؟؟؟