من یه مشکلی دارم نمیفهمم کی مرتبه ها رو در یه الگوریتم جمع میکنیم کی ضرب..بیچارم کرده این مشکل....
مثلا در سواله :مرتب کردن رادیکالn عنصر از کوچکترین عناصر یک ارایه چه مرتبه ای داره؟
گفنه در جواب که:
۱///ابتدا رادیکالn امین عنصر ارایه را با زمان n میابیم.
۲///بعد با الگوریتم پارنیشن بازمانn تمام رادیکالn کوچکترین عنصرو میبریم قبلش.
۳///حالا کافیه با یه الگوریتم مرتب سازی این رادیکالn عنصرو مرتب کنیم با زمان رادیکال n لوگ رادیکالn
بعد گفته در نهایت
جواب سوال هست همون رادیکال n لوگ رادیکال nیعنی ۳ تا مرحله جمع شدن.....چرا؟
کی ضرب میشه؟
سلام
ابتدا با زمان [tex]O(n)[/tex]، [tex]\sqrt{n}[/tex] عنصر رو پیدا کنید-سپس این رادیکال n عنصر رو در یک آرایه بریرزید و در زمان گفته شده مرتب کنید در نهایت مرتبه [tex]O(\sqrt{n\: }\log\: \sqrt{n}\: \: n)[/tex]
(۲۹ آذر ۱۳۹۳ ۰۷:۱۵ ب.ظ)ریحان نوشته شده توسط: من یه مشکلی دارم نمیفهمم کی مرتبه ها رو در یه الگوریتم جمع میکنیم کی ضرب..بیچارم کرده این مشکل....
مثلا در سواله :مرتب کردن رادیکالn عنصر از کوچکترین عناصر یک ارایه چه مرتبه ای داره؟
گفنه در جواب که:
۱///ابتدا رادیکالn امین عنصر ارایه را با زمان n میابیم.
۲///بعد با الگوریتم پارنیشن بازمانn تمام رادیکالn کوچکترین عنصرو میبریم قبلش.
۳///حالا کافیه با یه الگوریتم مرتب سازی این رادیکالn عنصرو مرتب کنیم با زمان رادیکال n لوگ رادیکالn
بعد گفته در نهایت
جواب سوال هست همون رادیکال n لوگ رادیکال nیعنی ۳ تا مرحله جمع شدن.....چرا؟
کی ضرب میشه؟
=====================
ببین این مراحل مجزا هست وهر کدام جدا گانه و جزا
مرحله اول انتخاب kایمن کوچکترین یا همون رادیکال nامین با مرتبه nبا روش ۵عنصری کردن
مرحله دوم افراز هست مرتبه n
مرتبه ۳ اخریشه رادیکال n عنصر رو مرتب کن اگرn عنصر بود میشد nlognاما چون رادیکال nعنصر هست میشه nlogرادیکال ان
توجه بفرمایید اگر در صورت سوال گفته بود اعدا صحیح هستن محدودیت گذاشته بود با مرتب سازی شمارشی میرفتیم میشدn
همین
(۲۹ آذر ۱۳۹۳ ۰۸:۴۶ ب.ظ)flowerirani نوشته شده توسط:(29 آذر ۱۳۹۳ ۰۷:۱۵ ب.ظ)ریحان نوشته شده توسط: من یه مشکلی دارم نمیفهمم کی مرتبه ها رو در یه الگوریتم جمع میکنیم کی ضرب..بیچارم کرده این مشکل....
مثلا در سواله :مرتب کردن رادیکالn عنصر از کوچکترین عناصر یک ارایه چه مرتبه ای داره؟
گفنه در جواب که:
۱///ابتدا رادیکالn امین عنصر ارایه را با زمان n میابیم.
۲///بعد با الگوریتم پارنیشن بازمانn تمام رادیکالn کوچکترین عنصرو میبریم قبلش.
۳///حالا کافیه با یه الگوریتم مرتب سازی این رادیکالn عنصرو مرتب کنیم با زمان رادیکال n لوگ رادیکالn
بعد گفته در نهایت
جواب سوال هست همون رادیکال n لوگ رادیکال nیعنی ۳ تا مرحله جمع شدن.....چرا؟
کی ضرب میشه؟
=====================
ببین این مراحل مجزا هست وهر کدام جدا گانه و جزا
مرحله اول انتخاب kایمن کوچکترین یا همون رادیکال nامین با مرتبه nبا روش ۵عنصری کردن
مرحله دوم افراز هست مرتبه n
مرتبه ۳ اخریشه رادیکال n عنصر رو مرتب کن اگرn عنصر بود میشد nlognاما چون رادیکال nعنصر هست میشه nlogرادیکال ان
توجه بفرمایید اگر در صورت سوال گفته بود اعدا صحیح هستن محدودیت گذاشته بود با مرتب سازی شمارشی میرفتیم میشدn
همین
ممنون میشه کمی بیشتر در مورد نکته ای که گفتین توضیح بدید...اعداد صیح و مرتب سازی شمارشی...