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

مرتبه زمانی

ارسال:
  

kilookiloo پرسیده:

مرتبه زمانی

سلام
سوالاتی مشابه ۸/۱ یا ۱۶/۱ توی عکس های زیر رو چطور میشه با روشی تحلیلی حل کرد ؟ یعنی بدون استفاده از معادله ها و استقرا . مثلا رسم درخت بازگشت . چون من بیشتر سوالات رو با درخت بازگشت حل میکنم ولی این تیپ سوال رو نمیدونم چطور باید حل کنم[تصویر:  433683_bfvr_img_۲۰۱۷۰۳۲۴_۱۸۲۳۱۵.jpg]
[تصویر:  433683_h7yg_img_۲۰۱۷۰۳۲۴_۱۸۲۳۲۸.jpg]
نقل قول این ارسال در یک پاسخ

۱
ارسال:
  

msour44 پاسخ داده:

RE: مرتبه زمانی

سلام
دوست گرامی روش حل کلاسیک روابط بازگشتی از مباحث مهم به شمار می اید که گاها در تست ها مطرح می شود از جمله در سوالات ۱/۸ و ۱/۱۶ که شما مطرح کردید.اینکه بخواهید از روش دیگری مثلا درختی به جواب برسید گاهی سوال طوری است که بر مبنای خود مفاهیم روش کلاسیک است و استفاده از روش دیگر گاها غیرممکن ویا زمان بر است.بیشتر از روش های درختی و قضیه اصلی و قضیه اکرا و ... برای یافتن مرتبه استفاده می شود و لی گاها در سوال حل رابطه بازگشتی را می خواهد مثل ۱/۱۶ که صریحا عنوان پاسخ رابطه بازگشتی همگن را می خواهد.
در این دو سوال که شما عنوان کردید حتی اگر روش حل اصلی روابط بازگشتی را بلد نباشیم هم می توانیم جواب دهیم
در ۱/۱۶ گزینه ۱ مرتبه را مشخص میکند نه حل رابطه پس رد می شود. مقادیر توقف رابطه که در سوال ذکر شده در رابطه نهایی که در گزینه ها امده هم باید صدق کند[tex]T(0)=0\: \: \: \: \: \: T(1)=1\: \: \: \: \: T(2)=2[/tex]
برای گزینه ۳ [tex]T(0)=2^0-0\ast2^{-1}+C=0\: \: \rightarrow\: \: C=-1\: \: \: \: \: \: \: \: \: \: T(1)=2-1+C=1\: \: \: \rightarrow\: C=0[/tex]
که رد می شود چون دو مقدار متفاوت برای c بدست امد
برای گزینه ۴ هم [tex]T(0)=1+C=0\: \: \rightarrow\: \: C=-1\: \: \: \: \: \: T(1)=2-\frac{1}{2}+C=1\: \: \: \rightarrow\: \: C=-\frac{1}{2}[/tex]
که رد می شود پس گزینه دو درست است اگر رابطه را حل کنیم همیمن گزینه ۲ بدست می اید با C= -2
در ۱/۸ هم نیازی به حل کامل نیست
[tex]G_i=G_{i-1}+2G_{i-2}+G_{i-3}\le4G_{i-1}=4^iG_0[/tex]
که [tex]G_0=1[/tex] پس گزینه ۱ صحیح است شاید این سوال پیش اید که گزینه ۴ هم می تواند جواب باشد ولی در عنوان سوال گفته کدام یک جواب بهتری است.
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

alireza01 پاسخ داده:

RE: مرتبه زمانی

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

سوال ۱/۱۷ که تو عکستون علامت زدید سوال سختی هست با روش قضیه اصلی به راحتی قابل حل است ، به این صورت که مقدار [tex]n^c=n^{\log_b^a}=n^{\log_3^9}=n^2[/tex] که زمانی مقدار [tex]T(n)=\theta(f(n))[/tex] میشه که مقدار [tex]f(n)\ge n^2[/tex] حال باید بدانیم از بین مقدار های داده شده کدام یک از این مقدار بیشتر است . که ۴ عبارت [tex]\{n^2\: ,\: n^3\: ,\: n^2\log n\: ,n^2\log^2\: n\: \: \: \}[/tex] فقط این شرطو دارن یعنی گزینه ۴ .

سوال ۱۶/۱ هم با همین قضیه اصلی به راحتی حل میشه کافیه معادله عمومی رو تشکیل بدیم که به فرم [tex]x^3-5x^2+8x-4=(x-2)^2(x-1)[/tex] تبدیل کنیم که در نهایت به فرم [tex]T(n)=C_02^n+C_1n2^n+C[/tex] میشه که اگه مقادیر مرزی سوال که رو داده وارد کنیم در نهایت [tex]C=-2\: ,\: C_0=2\: ,\: C_1=-\frac{1}{2}[/tex] و مقدار کلی برابر [tex]T(n)=2^{n+1}-n2^{n-1}-2[/tex] یعنی گزینه ۲
نقل قول این ارسال در یک پاسخ

ارسال:
  

Behnam‌ پاسخ داده:

RE: مرتبه زمانی

(۰۵ فروردین ۱۳۹۶ ۱۲:۵۶ ق.ظ)alireza01 نوشته شده توسط:  سلام ، دوست گرامی ، در تکمیل صحبت های دوست گرامی آقای منصور عرض کنم که برای حل معادلات بازگشتی فقط به روش درخت بازگشتی اکتفا نکن ، روش های خوبی برای حل وجود داره که اساتید و دوستان نمونه زیادی ازشون حل کردن ( اکرا بازی - جایگزاری - قضیه اصلی و ... ) سعی کنید تا حد امکان همشونو یاد بگیرید . یا مهم ترین هاشو بررسی کنید ...

سوال ۱/۱۷ که تو عکستون علامت زدید سوال سختی هست با روش قضیه اصلی به راحتی قابل حل است ، به این صورت که مقدار [tex]n^c=n^{\log_b^a}=n^{\log_3^9}=n^2[/tex] که زمانی مقدار [tex]T(n)=\theta(f(n))[/tex] میشه که مقدار [tex]f(n)\ge n^2[/tex] حال باید بدانیم از بین مقدار های داده شده کدام یک از این مقدار بیشتر است . که ۴ عبارت [tex]\{n^2\:,\:n^3\:,\:n^2\log n\:,n^2\log^2\:n\:\:\:\}[/tex] فقط این شرطو دارن یعنی گزینه ۴ .

سوال ۱۶/۱ هم با همین قضیه اصلی به راحتی حل میشه کافیه معادله عمومی رو تشکیل بدیم که به فرم [tex]x^3-5x^2+8x-4=(x-2)^2(x-1)[/tex] تبدیل کنیم که در نهایت به فرم [tex]T(n)=C_02^n+C_1n2^n+C[/tex] میشه که اگه مقادیر مرزی سوال که رو داده وارد کنیم در نهایت [tex]C=-2\:,\:C_0=2\:,\:C_1=-\frac{1}{2}[/tex] و مقدار کلی برابر [tex]T(n)=2^{n+1}-n2^{n-1}-2[/tex] یعنی گزینه ۲

سوال دیگه هم که مشکل داشتین جناب منصور زحمتش رو کشیدن .
آقا گیر دادی اسم ایشون منصور هستا :D
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

ارسال:
  

alireza01 پاسخ داده:

RE: مرتبه زمانی

(۰۶ فروردین ۱۳۹۶ ۰۶:۱۶ ب.ظ)Behnam‌ نوشته شده توسط:  آقا گیر دادی اسم ایشون منصور هستا Big Grin

شرمنده فک کردم منصوره ، مگه نیست ؟ Big Grin دیگه اگه خواستم با اسم پروفایل صداشون میکنم ... Blush
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
Exclamation سلام لطفاً یکی به من بگه مرتبه زمانی ها چطوری به log تبدیل میشن فرمول داره؟؟ Azadam ۶ ۳,۸۴۲ ۰۶ دى ۱۴۰۰ ۰۹:۰۲ ق.ظ
آخرین ارسال: Soldier's life
  مرتبه ایجاد درخت rad.bahar ۱ ۳,۰۲۴ ۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ
آخرین ارسال: rad.bahar
  مرتبه شبه کد rad.bahar ۱ ۲,۰۴۲ ۲۲ مهر ۱۳۹۹ ۰۹:۳۲ ب.ظ
آخرین ارسال: BBumir
  حل مساله مرتبه زمانی حلقه های تو در تو sarashahi ۱۶ ۲۱,۲۰۰ ۱۹ خرداد ۱۳۹۹ ۰۱:۱۶ ب.ظ
آخرین ارسال: gillda
  مرتبه زمانی Sanazzz ۱۷ ۱۹,۱۳۶ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۶ ب.ظ
آخرین ارسال: mohsentafresh
  پیچیدگی زمانی اکشن های قابل اعمال در یک وضعیت اsepid8994 ۰ ۱,۵۶۸ ۲۹ اسفند ۱۳۹۸ ۱۲:۵۱ ب.ظ
آخرین ارسال: اsepid8994
  مرتبه زمانی یافتن قطر Sepideh96 ۲ ۳,۴۰۹ ۰۸ آذر ۱۳۹۸ ۰۴:۳۴ ب.ظ
آخرین ارسال: erfan30
  مرتبه مانی Sanazzz ۳ ۳,۲۸۵ ۰۵ خرداد ۱۳۹۸ ۰۲:۳۶ ب.ظ
آخرین ارسال: Sanazzz
Question یافتن دو عدد پیچیدگی زمانی O(n) porseshgar ۲ ۳,۵۰۶ ۱۵ بهمن ۱۳۹۷ ۱۲:۱۶ ب.ظ
آخرین ارسال: porseshgar
  مرتبه زمانی Sanazzz ۰ ۱,۸۲۹ ۰۴ بهمن ۱۳۹۷ ۰۵:۴۱ ب.ظ
آخرین ارسال: Sanazzz

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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