زمان کنونی: ۱۰ فروردین ۱۴۰۳, ۰۳:۳۴ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

سوال ۵۲ مهندسی ۹۲ - مرتبه میانگین یافتن کمینه (در جایگشت n عنصر)

ارسال:
  

tayebe68 پرسیده:

سوال ۵۲ مهندسی ۹۲ - مرتبه میانگین یافتن کمینه (در جایگشت n عنصر)

پاسخ سنجش: گزینه ۱

چطوری میشه log n ؟ لطفا روش کار رو توضیح بدید

فقط تا اینجا رو می دونم که کمینه با احتمال [tex]\frac{1}{n}[/tex] می تونه در هر کدوم از n خونه باشه
برای ادامه ش گیج شدم


فایل‌(های) پیوست شده

نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

masoud67 پاسخ داده:

RE: سوال ۵۲ مهندسی ۹۲ - مرتبه میانگین یافتن کمینه (در جایگشت n عنصر)

روش کار اینجوریه که قراره عنصر مین یا ماکس (چون صورت الگوریتم مشکل داره) پیدا کنه
اول کار عنصر اول آرایه را میبینه، با چه احتمالی عنصر مین هست ؟ [tex]1/n[/tex]
پس با این احتمال در مرتبه اول خط چهار اجرا میشه

مرحله بعد، دومین عنصر آرایه رو با مین مقایسه میکنه؟ احتمال اینکه این عنصر مین باشه چقدره ؟ [tex]1/(n-1)[/tex]
چون n-1 عنصر باقی مونده و با این احتمال میتونه مین باشه

و مراحل بعدی و احتمال های بعدی که جمع این احتمالها میشه logn
این فرمول نویسی Tex مشکل داشت ، نتونستم درست رابطه رو بنویسم
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

izadan11 پاسخ داده:

RE: سوال ۵۲ مهندسی ۹۲ - مرتبه میانگین یافتن کمینه (در جایگشت n عنصر)

ما به دنبال مین اصلی هستیم وقتی مین پیدا شد دیگه شرط ما صدق نمی کنه وقتی دنبال یه عدد خاص در یک آرایه هستیم احتمال بودن اون عدد در هر ایندکس یک nام (یک تقسیم بر n) هست هدف ما پیدا کردن حالت متوسط یا امید ریاضیه
پس میشه مجموع ایندکس هر عدد ضرب در احتمالش
این جمع میشه n+1 تقسیم بر دو یعنی در حالت متوسط مین وسط آرایه میوفته پس در سمت راست آرایه شرط دیگر صادق نمی شه حالا آرایه نصف شده و باز همون مسئله پس
T(N)=T(N/2)+1
که میشه همون لاگ ان
این مسئله اسمش استخدام منشیه فصل ۵ clrs اثبات دقیقش هست
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  جایگشت( ارشد علوم کامپیوتر ۹۸ ) ss311 ۰ ۱,۶۹۵ ۰۳ اسفند ۱۳۹۸ ۱۲:۴۵ ب.ظ
آخرین ارسال: ss311
  سوال مهندسی نرم افزار سال ۸۶(مهندسی نیازمندی ها) tarane1992 ۴ ۴,۸۲۶ ۲۲ بهمن ۱۳۹۷ ۰۲:۳۷ ق.ظ
آخرین ارسال: Bon_Nemesis
Question رسم درخت با ۲۶ گره و ارتفاع کمینه porseshgar ۰ ۱,۵۴۴ ۱۶ بهمن ۱۳۹۷ ۱۲:۱۱ ب.ظ
آخرین ارسال: porseshgar
Question یافتن دو عدد پیچیدگی زمانی O(n) porseshgar ۲ ۳,۵۰۶ ۱۵ بهمن ۱۳۹۷ ۱۲:۱۶ ب.ظ
آخرین ارسال: porseshgar
  محاسبه چندمین عنصر آرایه Mr.R3ZA ۶ ۶,۰۹۵ ۱۹ شهریور ۱۳۹۷ ۰۸:۱۲ ب.ظ
آخرین ارسال: Saman
  فرق بین مهندسی کامپیوتر گرایش نرم افزار با مهندسی کامپیوتر نرم افزار Rafaat ۰ ۳,۷۸۸ ۲۵ اردیبهشت ۱۳۹۷ ۰۲:۴۵ ب.ظ
آخرین ارسال: Rafaat
  یافتن مسیر در گراف کامل دو بخشی Sepideh96 ۳ ۳,۶۸۴ ۲۶ بهمن ۱۳۹۶ ۱۲:۴۲ ب.ظ
آخرین ارسال: αɾια
  راه حلی برای یافتن تداخل در روشهای تقدم Sepideh96 ۱ ۱,۹۴۴ ۰۷ بهمن ۱۳۹۶ ۱۱:۵۹ ب.ظ
آخرین ارسال: alilash
  جایگشت اعداد ss311 ۰ ۱,۱۷۹ ۰۶ بهمن ۱۳۹۶ ۰۲:۰۴ ب.ظ
آخرین ارسال: ss311
  kمین کوچکترین عنصر در یک هرم کمینه؟ Iranian Wizard ۳ ۳,۹۶۰ ۰۳ بهمن ۱۳۹۶ ۰۵:۰۸ ق.ظ
آخرین ارسال: molayi

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close