دوستان میشه بدترین حالت و حالت میانگین این الگوریتم رو توضیح بدید؟؟
دو لیست نامرتب A و B .هرکدام با n عنصر داده شده است.میخواهیم بصورت بهینه لیست [tex]A\: \cap\: B[/tex]
را بدست آوریم
یعنی کسی نمیدونه؟؟؟؟؟؟؟
البته فقط سوالم اینه که برای حالت متوسط که از hash استفاده میکنیم و این جدول رو بسازیم که مرتبه اش [tex]\theta(n)[/tex]
میشه . و بعد اعناصر لیست دوم رو در جدول جستجو کنیم
حالا جرا مرتبه جستجوی هر عنصر تو جدول درهم رو [tex]O(1)[/tex]
درنظر میگیریم ؟
مرتبه جستجو مگه [tex]O(\frac{n}{B})[/tex] نیست؟
B طول جدول