۰
subtitle
ارسال: #۱
  
مرتبه زمانی بازگشتی
کسی میتونه بگه چرا مرتبه زمانی این سوال از nlogn هست؟؟
[tex]T(n)\: =\: \frac{2}{n}\sum^{n-1}_{k=0^{ }}T(k)\: \: n[/tex]
واسه راهنمایی گفته شده که طرفین رو در n ضرب کنیم و سپس T(n-1) رو پیدا کرده و از T(n) کم کنیم ولی من با این راه به جواب n میرسم!!!
راه حلم توی ضمیمه هست. البته آخرش رو شانسی گفتم میشه n
[tex]T(n)\: =\: \frac{2}{n}\sum^{n-1}_{k=0^{ }}T(k)\: \: n[/tex]
واسه راهنمایی گفته شده که طرفین رو در n ضرب کنیم و سپس T(n-1) رو پیدا کرده و از T(n) کم کنیم ولی من با این راه به جواب n میرسم!!!
راه حلم توی ضمیمه هست. البته آخرش رو شانسی گفتم میشه n
۰
ارسال: #۲
  
RE: مرتبه زمانی بازگشتی
سلام.
فکر میکنم خط چهارم راه حلتون درست نیست. به علاوه اینکه توجه کنید حتی اگر به همین جواب آخر هم میرسیدید، مرتبهی جواب از n نمیشد و از مرتبهی [tex]O(n^2)[/tex] میشد.
فکر میکنم راه حل سؤال به این شکل هست:
[tex]nT(n)=2\sum_{k=0}^{n-1}T(k) n[/tex]
[tex](n-1)T(n-1)=2\sum_{k=0}^{n-2}T(k) n-1[/tex]
[tex]nT(n)-(n-1)T(n-1)=2T(n-1) 1[/tex]
[tex]nT(n)=(n 1)T(n-1) 1[/tex]
[tex]T(n)=\frac{n 1}{n}T(n-1) \frac{1}{n}[/tex]
بعد از این برای پیدا کردن مرتبه، میشه از جایگذاری مکرر کمک گرفت:
[tex]T(n)=\frac{n 1}{n}(\frac{n}{n-1}(\frac{n-1}{n-2}...(\frac{n-n 2}{n-n 1})) \frac{1}{n})[/tex]
همانطور که میبینید، در این ضربهای مکرر، صورت و مخرجهای پیدرپی با هم ساده میشن، در نهایت فکر میکنم چیزی که میمونه اینطور میشه:
[tex]2(n 1)logn \in O(nlogn)[/tex]
چون [tex]\frac{1}{n}[/tex] در نهایت مرتبهی logn داره و در جایگذاری مکرر هم دیدیم که یک مرتبهی در logn ضرب خواهد شد.
فکر میکنم خط چهارم راه حلتون درست نیست. به علاوه اینکه توجه کنید حتی اگر به همین جواب آخر هم میرسیدید، مرتبهی جواب از n نمیشد و از مرتبهی [tex]O(n^2)[/tex] میشد.
فکر میکنم راه حل سؤال به این شکل هست:
[tex]nT(n)=2\sum_{k=0}^{n-1}T(k) n[/tex]
[tex](n-1)T(n-1)=2\sum_{k=0}^{n-2}T(k) n-1[/tex]
[tex]nT(n)-(n-1)T(n-1)=2T(n-1) 1[/tex]
[tex]nT(n)=(n 1)T(n-1) 1[/tex]
[tex]T(n)=\frac{n 1}{n}T(n-1) \frac{1}{n}[/tex]
بعد از این برای پیدا کردن مرتبه، میشه از جایگذاری مکرر کمک گرفت:
[tex]T(n)=\frac{n 1}{n}(\frac{n}{n-1}(\frac{n-1}{n-2}...(\frac{n-n 2}{n-n 1})) \frac{1}{n})[/tex]
همانطور که میبینید، در این ضربهای مکرر، صورت و مخرجهای پیدرپی با هم ساده میشن، در نهایت فکر میکنم چیزی که میمونه اینطور میشه:
[tex]2(n 1)logn \in O(nlogn)[/tex]
چون [tex]\frac{1}{n}[/tex] در نهایت مرتبهی logn داره و در جایگذاری مکرر هم دیدیم که یک مرتبهی در logn ضرب خواهد شد.
موضوعهای مرتبط با این موضوع... |
|||||
موضوع: | نویسنده | پاسخ: | بازدید: | آخرین ارسال | |
سلام لطفاً یکی به من بگه مرتبه زمانی ها چطوری به log تبدیل میشن فرمول داره؟؟ | Azadam | ۶ | ۵,۰۳۸ |
۰۶ دى ۱۴۰۰ ۰۹:۰۲ ق.ظ آخرین ارسال: Soldier's life |
|
مرتبه ایجاد درخت | rad.bahar | ۱ | ۳,۴۱۴ |
۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ آخرین ارسال: rad.bahar |
|
مرتبه شبه کد | rad.bahar | ۱ | ۲,۳۷۳ |
۲۲ مهر ۱۳۹۹ ۰۹:۳۲ ب.ظ آخرین ارسال: BBumir |
|
حل مساله مرتبه زمانی حلقه های تو در تو | sarashahi | ۱۶ | ۲۳,۲۳۱ |
۱۹ خرداد ۱۳۹۹ ۰۱:۱۶ ب.ظ آخرین ارسال: gillda |
|
مرتبه زمانی | Sanazzz | ۱۷ | ۲۱,۷۸۲ |
۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۶ ب.ظ آخرین ارسال: mohsentafresh |
|
پیچیدگی زمانی اکشن های قابل اعمال در یک وضعیت | اsepid8994 | ۰ | ۱,۸۱۷ |
۲۹ اسفند ۱۳۹۸ ۱۲:۵۱ ب.ظ آخرین ارسال: اsepid8994 |
|
مرتبه زمانی یافتن قطر | Sepideh96 | ۲ | ۳,۸۵۱ |
۰۸ آذر ۱۳۹۸ ۰۴:۳۴ ب.ظ آخرین ارسال: erfan30 |
|
مرتبه مانی | Sanazzz | ۳ | ۳,۷۶۹ |
۰۵ خرداد ۱۳۹۸ ۰۲:۳۶ ب.ظ آخرین ارسال: Sanazzz |
|
یافتن دو عدد پیچیدگی زمانی O(n) | porseshgar | ۲ | ۳,۹۷۷ |
۱۵ بهمن ۱۳۹۷ ۱۲:۱۶ ب.ظ آخرین ارسال: porseshgar |
|
مرتبه زمانی | Sanazzz | ۰ | ۲,۰۶۴ |
۰۴ بهمن ۱۳۹۷ ۰۵:۴۱ ب.ظ آخرین ارسال: Sanazzz |
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close