تعداد مقایسه ها برای جستجوی موفق چند تاست؟ [بایگانی]

lvenoos

دوشنبه 28 آبان 1386, 15:32 عصر

icmaster

دوشنبه 28 آبان 1386, 20:00 عصر

در صورتی که آرایه مورد جستجو در جستجوی دودوی به صورت 7و6و5و4و3و2و1و0و1- باشد، متوسط تعداد مقایسه ها برای جستجوی موفق چیست؟
الف9/27 ب9/25 ج9/31 د هیچکدام
ببخشید اینجوری نوشتم اینها رو به صورت کسری فرض کنید. باتشکر

25/9 (ب) صحیح هست.

از اونجا که یک آرایه مرتب داریم درخت جستجوی دودیی کامل رو میشه براحتی تشکیل داد.
در نتیجه برای عناصر سطر اول یک مقایسه، برای عناصر سطر دوم 2 مقایسه، سطر سوم 3 مقایسه و ... لازم هست. با جمع تعداد مقایسه ها تقسیم اون بر تعداد عناصر(در اینجا 9) میانگین مقایسه ها بدست میاد.