عدد طبیعی n و عدد طبیعی a_1, …, a_n داده شده است. قصد داریم بدانیم دو اندیس i و j وجود دارد که 0 < a_i - a_j ≤ 5 یا خیر. زمان متوسط لازم برای این منظور با استفاده از درهمسازی (Hashing) از چه مرتبهای است؟

سوال ۷۲ کنکور ارشد علوم کامپیوتر ۱۴۰۲

ساختمان دادهمتوسطدرهم‌سازی و جدول‌های درهم‌سازی

اهمیت

۰/۵

عدد طبیعی $n$ و عدد طبیعی $a_1, \ldots, a_n$ داده شده است. قصد داریم بدانیم دو اندیس $i$ و $j$ وجود دارد که $0 < |a_i - a_j| \le 5$ یا خیر. زمان متوسط لازم برای این منظور با استفاده از درهم‌سازی (Hashing) از چه مرتبه‌ای است؟

#hashing#hash-table#expected-time#close-pair#constant-neighbors