۰
subtitle
ارسال: #۱
مرتبه زمانی
مرتبه ی زمانی این تابع چگونه به دست می آید؟
۱
ارسال: #۲
RE: مرتبه زمانی
این تابع مجموع اعداد به توان ۲ است که از مرتبه [tex]O(n^3)[/tex] است.
اگر بخوایم بطور دقیقتر بحث کنیم در این تابع از روال پارتیشن استفاده میشه(مانند Quick sort) که بجای اینکه محور در وسط باشد در یک سمت قرار گرفته که در یک سمت n-1 عدد دیگه داره و در سمت دیگه عددی نیست(تهی است). حال اگر زمان اجرای روال پارتیشن به [tex]n^2[/tex] مقایسه نیاز داشته باشند چنین تابع بازگشتی برای حل بوجود میاد.
اگر بخوایم بطور دقیقتر بحث کنیم در این تابع از روال پارتیشن استفاده میشه(مانند Quick sort) که بجای اینکه محور در وسط باشد در یک سمت قرار گرفته که در یک سمت n-1 عدد دیگه داره و در سمت دیگه عددی نیست(تهی است). حال اگر زمان اجرای روال پارتیشن به [tex]n^2[/tex] مقایسه نیاز داشته باشند چنین تابع بازگشتی برای حل بوجود میاد.
ارسال: #۳
RE: مرتبه زمانی
(۰۴ مهر ۱۳۹۳ ۰۸:۵۶ ب.ظ)m@hboobe نوشته شده توسط: این تابع مجموع اعداد به توان ۲ است که از مرتبه [tex]O(n^3)[/tex] است.
اگر بخوایم بطور دقیقتر بحث کنیم در این تابع از روال پارتیشن استفاده میشه(مانند Quick sort) که بجای اینکه محور در وسط باشد در یک سمت قرار گرفته که در یک سمت n-1 عدد دیگه داره و در سمت دیگه عددی نیست(تهی است). حال اگر زمان اجرای روال پارتیشن به [tex]n^2[/tex] مقایسه نیاز داشته باشند چنین تابع بازگشتی برای حل بوجود میاد.
دوست عزیز میشه یه راهنماییم کنین که کدوم منبع این قسمتو خوب توضیح داده تا از روی اون بخونم؟تشکر
ارسال: #۴
RE: مرتبه زمانی
(۰۴ مهر ۱۳۹۳ ۰۹:۵۵ ب.ظ)ziba.O نوشته شده توسط:توضیحی که من گفتم در فهم این رابطه بازگشتی بهتون کمک میکنه وگرنه حلش که از طریق جایگذاری ساده هم همون جور که دوستان گفتن بدست میاد(04 مهر ۱۳۹۳ ۰۸:۵۶ ب.ظ)m@hboobe نوشته شده توسط: این تابع مجموع اعداد به توان ۲ است که از مرتبه [tex]O(n^3)[/tex] است.
اگر بخوایم بطور دقیقتر بحث کنیم در این تابع از روال پارتیشن استفاده میشه(مانند Quick sort) که بجای اینکه محور در وسط باشد در یک سمت قرار گرفته که در یک سمت n-1 عدد دیگه داره و در سمت دیگه عددی نیست(تهی است). حال اگر زمان اجرای روال پارتیشن به [tex]n^2[/tex] مقایسه نیاز داشته باشند چنین تابع بازگشتی برای حل بوجود میاد.
دوست عزیز میشه یه راهنماییم کنین که کدوم منبع این قسمتو خوب توضیح داده تا از روی اون بخونم؟تشکر
در مورد این توضیح هم کتاب CLRS و طراحی الگوریتم مدرسان مطالبی دارند.
این نکته رو هم بدونید که
[tex]\sum_{i=1}^ni^k\: =\: 1^k\: \: 2^k\: \: 3^k\: ....\: n^k\: \sim\frac{1}{k 1}\: n^{k 1}\: =\: Theta(n^{K 1})[/tex]
کتاب پوران ساختمان و طراحی فصل اول این نکته اومده
ارسال: #۵
RE: مرتبه زمانی
(۰۴ مهر ۱۳۹۳ ۱۱:۲۸ ب.ظ)m@hboobe نوشته شده توسط:(04 مهر ۱۳۹۳ ۰۹:۵۵ ب.ظ)ziba.O نوشته شده توسط:توضیحی که من گفتم در فهم این رابطه بازگشتی بهتون کمک میکنه وگرنه حلش که از طریق جایگذاری ساده هم همون جور که دوستان گفتن بدست میاد(04 مهر ۱۳۹۳ ۰۸:۵۶ ب.ظ)m@hboobe نوشته شده توسط: این تابع مجموع اعداد به توان ۲ است که از مرتبه [tex]O(n^3)[/tex] است.
اگر بخوایم بطور دقیقتر بحث کنیم در این تابع از روال پارتیشن استفاده میشه(مانند Quick sort) که بجای اینکه محور در وسط باشد در یک سمت قرار گرفته که در یک سمت n-1 عدد دیگه داره و در سمت دیگه عددی نیست(تهی است). حال اگر زمان اجرای روال پارتیشن به [tex]n^2[/tex] مقایسه نیاز داشته باشند چنین تابع بازگشتی برای حل بوجود میاد.
دوست عزیز میشه یه راهنماییم کنین که کدوم منبع این قسمتو خوب توضیح داده تا از روی اون بخونم؟تشکر
در مورد این توضیح هم کتاب CLRS و طراحی الگوریتم مدرسان مطالبی دارند.
این نکته رو هم بدونید که
[tex]\sum_{i=1}^ni^k\: =\: 1^k\: \: 2^k\: \: 3^k\: ....\: n^k\: \sim\frac{1}{k 1}\: n^{k 1}\: =\: Theta(n^{K 1})[/tex]
کتاب پوران ساختمان و طراحی فصل اول این نکته اومده
ممنون دوست عزیز
۱
ارسال: #۶
RE: مرتبه زمانی
حل رابطه با استفاده از جایگزینی:
رابطه اصلی ما اینه:
[tex]T(n)=T(n-1) n^2[/tex]
روش حل اینه ما جمله بازگشتی رو با مقدارش توی رابطه جایگزین میکنیم
ما اینجا به جمله ی [tex]T(n-1)[/tex] احتیاج دارم ،پس این مقدار رو به دست میاریم و توی رابطه اصلی میذاریم:
[tex]T(n-1)=T(n-2) (n-1)^2[/tex]
پس رابطه اصلی میشه:
[tex]T(n)=T(n-2) (n-1)^2 n^2[/tex]
خب حالا به جمله [tex]T(n-2)[/tex] احتیاج داریم پس عملیات بالا رو تکرار میکنیم:
[tex]T(n-2)=T(n-3) (n-2)^2[/tex]
پس رابطه اصلی میشه:
[tex]T(n)=T(n-3) (n-2)^2 (n-1)^2 n^2[/tex]
ان قدر این کار رو تکرار میکنیک تا به حالت پایه برسیم
حالت پایه حالتیه که رابطه بیشتر از اون کوچیک نمیشه
خب حالا ما که نمیتونیم این همه جمله رو محاسبه کنیم پس باید دنبال یه ریتم باشیم که ببینیم مقدار جملات ما چه ریتمی دارن:
الان جملات ما اینشکلین:
[tex]1^2 2^2 3^2 ... (n-2)^2 (n-1)^2 n^2[/tex]
که طبق این سیگما داریم:
[tex]\sum i^2=1^2 2^2 3^2 ... (n-2)^2 (n-1)^2 n^2=\theta(n^3)[/tex]
پس رابطه ما از مرتبه [tex]\theta(n^3)[/tex] هستش
رابطه اصلی ما اینه:
[tex]T(n)=T(n-1) n^2[/tex]
روش حل اینه ما جمله بازگشتی رو با مقدارش توی رابطه جایگزین میکنیم
ما اینجا به جمله ی [tex]T(n-1)[/tex] احتیاج دارم ،پس این مقدار رو به دست میاریم و توی رابطه اصلی میذاریم:
[tex]T(n-1)=T(n-2) (n-1)^2[/tex]
پس رابطه اصلی میشه:
[tex]T(n)=T(n-2) (n-1)^2 n^2[/tex]
خب حالا به جمله [tex]T(n-2)[/tex] احتیاج داریم پس عملیات بالا رو تکرار میکنیم:
[tex]T(n-2)=T(n-3) (n-2)^2[/tex]
پس رابطه اصلی میشه:
[tex]T(n)=T(n-3) (n-2)^2 (n-1)^2 n^2[/tex]
ان قدر این کار رو تکرار میکنیک تا به حالت پایه برسیم
حالت پایه حالتیه که رابطه بیشتر از اون کوچیک نمیشه
خب حالا ما که نمیتونیم این همه جمله رو محاسبه کنیم پس باید دنبال یه ریتم باشیم که ببینیم مقدار جملات ما چه ریتمی دارن:
الان جملات ما اینشکلین:
[tex]1^2 2^2 3^2 ... (n-2)^2 (n-1)^2 n^2[/tex]
که طبق این سیگما داریم:
[tex]\sum i^2=1^2 2^2 3^2 ... (n-2)^2 (n-1)^2 n^2=\theta(n^3)[/tex]
پس رابطه ما از مرتبه [tex]\theta(n^3)[/tex] هستش
۱
ارسال: #۸
RE: مرتبه زمانی
ارسال: #۹
RE: مرتبه زمانی
۰
۰
ارسال: #۱۲
RE: مرتبه زمانی
ارسال: #۱۳
RE: مرتبه زمانی
۰
ارسال: #۱۴
RE: مرتبه زمانی
بفرمایید اینم پاسخ کلی تر به سوال
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
Bache Mosbat، در تاریخ ۱۱ مهر ۱۳۹۳ ۰۳:۰۷ ب.ظ برای این مطلب یک پانوشت گذاشته است:
اگر میشه جوابتون رو تو تاپیک هم بنویسید.
ارسال: #۱۵
RE: مرتبه زمانی
(۰۵ مهر ۱۳۹۳ ۱۲:۵۳ ب.ظ)miladcr7 نوشته شده توسط: بفرمایید اینم پاسخ کلی تر به سوال
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
سلام دستت درد نکنه اون پاسختونو امروز بخونم اگه متوجه نشدم تا شب اعلام میکنم،ممنون از زحمتی که کشیدین
ارسال: #۱۶
RE: مرتبه زمانی
(۰۵ مهر ۱۳۹۳ ۰۱:۵۱ ب.ظ)ziba.O نوشته شده توسط:(05 مهر ۱۳۹۳ ۱۲:۵۳ ب.ظ)miladcr7 نوشته شده توسط: بفرمایید اینم پاسخ کلی تر به سوال
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
سلام دستت درد نکنه اون پاسختونو امروز بخونم اگه متوجه نشدم تا شب اعلام میکنم،ممنون از زحمتی که کشیدین
سلام.خواهش میکنم ولی فکر کنم جوابی که تو همین تاپیک گذاشتم واضح تر از اونیه که براتون فرسادم
ارسال: #۱۷
RE: مرتبه زمانی
(۰۵ مهر ۱۳۹۳ ۰۳:۱۴ ب.ظ)miladcr7 نوشته شده توسط:(05 مهر ۱۳۹۳ ۰۱:۵۱ ب.ظ)ziba.O نوشته شده توسط:(05 مهر ۱۳۹۳ ۱۲:۵۳ ب.ظ)miladcr7 نوشته شده توسط: بفرمایید اینم پاسخ کلی تر به سوال
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
سلام دستت درد نکنه اون پاسختونو امروز بخونم اگه متوجه نشدم تا شب اعلام میکنم،ممنون از زحمتی که کشیدین
سلام.خواهش میکنم ولی فکر کنم جوابی که تو همین تاپیک گذاشتم واضح تر از اونیه که براتون فرسادم
نه من که فهمیدم چی شد و اون مرتبه از کجا اومد دستتون درد نکنه
۰
ارسال: #۱۹
RE: مرتبه زمانی
۰
ارسال: #۲۱
RE: مرتبه زمانی
(۱۱ مهر ۱۳۹۳ ۱۰:۲۰ ق.ظ)kingmax نوشته شده توسط: سلام دوستان این اشتباه نکرده
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
آخه رابطه چهارمی ۴n-1000 چجوری مرتبه ۲ شده؟
خواسته O رو بیشتر توضیح داده واسش مثالهای خیلی کوچیکتر از خودشم آورده.نه اشتباه نیس چون
ارسال: #۲۲
RE: مرتبه زمانی
(۱۱ مهر ۱۳۹۳ ۱۰:۲۰ ق.ظ)kingmax نوشته شده توسط: سلام دوستان این اشتباه نکرده
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
آخه رابطه چهارمی ۴n-1000 چجوری مرتبه ۲ شده؟
سلام
اشتباه نکرده.توابعی عضو [tex]O(n^2)[/tex] هستند که رشدشون کوچکتر یا مساوی [tex]n^2[/tex] باشه خب؟
حالا اونی که شما گفتی رشدش از مرتبه [tex]n[/tex] هستش که کوچکتر از [tex]n^2[/tex] هست پس رابطه درسته
۰
ارسال: #۲۳
RE: مرتبه زمانی
سپاس و تشکر من تازه امروز ساختمان شروع کردم یه خورده گیج میزنم ببخشید تازه دیروز کتابش بدستم رسیده
ارسال: #۲۴
RE: مرتبه زمانی
۰
ارسال: #۲۶
RE: مرتبه زمانی
(۱۳ مهر ۱۳۹۳ ۰۲:۱۷ ب.ظ)kingmax نوشته شده توسط: سلام بچه ها این اشکالی من از حل این مثال گرفتم درسته؟اگه نیست لطفا توضیح بدیدسلام
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
ببین برای اینکه سریعتر به جواب برسی یه تاپیک برای سوالت ایجاد کن
حالا میشه بگی تحلیلت از اضافه کردن اون ۱ چی بوده؟
ارسال: #۲۷
RE: مرتبه زمانی
(۱۳ مهر ۱۳۹۳ ۰۸:۴۲ ب.ظ)miladcr7 نوشته شده توسط:لطفا سوالهاتون رو مجزا بپرسید اینجوری همه چی قاطی میشه!(13 مهر ۱۳۹۳ ۰۲:۱۷ ب.ظ)kingmax نوشته شده توسط: سلام بچه ها این اشکالی من از حل این مثال گرفتم درسته؟اگه نیست لطفا توضیح بدیدسلام میشه بگی تحلیلت از اضافه کردن اون ۱ چی بوده؟
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
ایشون با اضافه کردن یک تعداد گام های این تکه کد رو در نظر گرفتن... در صورتی که در صورت مثال نوشته تکرار حلقه که منظور حلقه while بیرونی است
ارسال: #۲۸
RE: مرتبه زمانی
(۱۳ مهر ۱۳۹۳ ۰۸:۴۹ ب.ظ)m@hboobe نوشته شده توسط:(13 مهر ۱۳۹۳ ۰۸:۴۲ ب.ظ)miladcr7 نوشته شده توسط:لطفا سوالهاتون رو مجزا بپرسید اینجوری همه چی قاطی میشه!(13 مهر ۱۳۹۳ ۰۲:۱۷ ب.ظ)kingmax نوشته شده توسط: سلام بچه ها این اشکالی من از حل این مثال گرفتم درسته؟اگه نیست لطفا توضیح بدیدسلام میشه بگی تحلیلت از اضافه کردن اون ۱ چی بوده؟
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
ایشون با اضافه کردن یک تعداد گام های این تکه کد رو در نظر گرفتن... در صورتی که در صورت مثال نوشته تکرار حلقه که منظور حلقه while بیرونی است
درسته منم بهشون گفتم برای اینکه سریعتر به جواب برسن.و نیازی به اون یک نیست.جواب خود مسئله درسته
۰
ارسال: #۳۰
RE: مرتبه زمانی
موضوع‌های مرتبط با این موضوع... |
|||||
| موضوع: | نویسنده | پاسخ: | بازدید: | آخرین ارسال | |
 |
سلام لطفاً یکی به من بگه مرتبه زمانی ها چطوری به 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