صفحهها: ۱ ۲
(۱۹ بهمن ۱۳۹۰ ۰۴:۵۸ ب.ظ)homa نوشته شده توسط:(13 دى ۱۳۹۰ ۰۸:۲۳ ب.ظ)rad.bahar نوشته شده توسط: در کتاب نیپولیتان فصل ۷ تمرین ۱ صفحه ۳۳۶ سوالی مشابه داده شده با این مضمون
فرض کنید که s,t دو ارایه m,n عنصری باشند الگوریتمی بنویسید که تمامی عناصر مشترک را پیدا کند و انها را در ارایه u ذخیره کند نشان دهید که این کار می تواند در زمان (n+m)تتا انجام شود
اگر چنین است پس جواب سوال کنکور( n)تتا است؟!!! کسی نظری داره
در مورد راه حلش توضیحی نداده ؟؟؟
من هم قبلا این مطلب رو خونده بودم.
فکر کنم جواب در حالتی است که دو آرایه مرتب باشند.فرض کنیم n>m
به ازای هر عنصر در n الگوریتم دنبال مشابه آن در آرایه m می گردد و در بدترین حالت باید تا آخر آرایه رو جستجو کند که m بار جستجو می شود.
تتا(n+m) =تتا(n)