سلام دوستان
میگم برای فهمیدن مرتبه اجرایی حلقه های تودرتو وابسته در سر جلسه کنکور چه راهی بهتر از trace کردن چند مرحله از الگوریتم است که سریع به جواب برسیم
مثلا
for(i=1;i<=n;i*2)
for(j=1;j<=i;j*2
{
x++;
{
(۱۰ مرداد ۱۳۹۳ ۱۲:۲۶ ق.ظ)bernova نوشته شده توسط: سلام دوستاننه فکر نمی کنم روش دیگه ای وجود داشته باشه خود این روش trace کردن هم به نظرم مشکل نیست اگه چند نمونه از این مساله ها حل کنید زود راه می افتید. برای مساله بالا هم با trace کردن به جواب (O(logn می رسیم.
میگم برای فهمیدن مرتبه اجرایی حلقه های تودرتو وابسته در سر جلسه کنکور چه راهی بهتر از trace کردن چند مرحله از الگوریتم است که سریع به جواب برسیم
مثلا
for(i=1;i<=n;i*2)
for(j=1;j<=i;j*2
{
x++;
{
(۲۶ تیر ۱۳۹۳ ۰۲:۰۳ ب.ظ)Ava.arshad94 نوشته شده توسط: الان من توو تفاوت این دوتا موندم
به این فرمول رسیدم [tex]o(f)\subseteq O(f)-Omega(f)[/tex] و گفته شده دلیلش اینه که توو سمت راستی توابعی هست که توو سمت چپی نیس. خب این که تعریفه این یکیه [tex]\subset[/tex]
سلام.
این درسته :
[tex]o(f)\subset O(f)-Omega(f)[/tex]
سلام دوست عزیز
منمنون از توجه تون
لطفا به حلقه تودرتو زیر نیز یه نگاه بنداز تو جزوه امیرکبیر یه جواب داده ، پارسه هم یه جواب
مرتبه اجراییی الگوریتم زیر چقدر است
for(i=0;i<n;i++[/align]
(۱۱ مرداد ۱۳۹۳ ۱۰:۳۸ ب.ظ)bernova نوشته شده توسط: سلام دوست عزیزبرای حلقه ی for خالی که مرتبه تعیین نمی کنن. از روی این حلقه ای که شما نوشتید فقط تعداد دفعات تکرار خود for به اضافه ی تعداد تکرار داخل حلقه ی for مشخص می شه.اگه هدف ما تعیین مرتبه باشه بایستی دنبال دستور اصلی باشیم.
منمنون از توجه تون
لطفا به حلقه تودرتو زیر نیز یه نگاه بنداز تو جزوه امیرکبیر یه جواب داده ، پارسه هم یه جواب
مرتبه اجراییی الگوریتم زیر چقدر است
for(i=0;i<n;i++[/align]
اقا شرمنده من نمیدونم چرا حلقه for اینطوری پست شد اینجا منظورم مرتبه اجرایی حلقه زیر است
for(I=1;I<n;I++)1
for(j=1;j<n;J++)1
{
x++
n++
}
بازم ببخشید
(۱۲ مرداد ۱۳۹۳ ۰۴:۳۵ ب.ظ)bernova نوشته شده توسط: اقا شرمنده من نمیدونم چرا حلقه for اینطوری پست شد اینجا منظورم مرتبه اجرایی حلقه زیر است
for(I=1;I<n;I++)1
for(j=1;j<n;J++)1
{
x++
n++
}
بازم ببخشید
مطمعنین اون n++ هست و n-- نیست؟
ببینم فکر کنم --n باشه نه ++n؟
اره n-- ,است . یکی از مثال های پارسه است
منظورم اینه که تو پارسه میگه O(n و جزوه امیرکبیر میگه O(nlogn به نظر من دومی است
به نظر من همون مرتبه n درسته
براساس تریس که کردین شد n
دوستان این روابط بازگشتی و این چیزارو با کدوم کتاب خوب یاد میگیرم.
هیچ جوره من یادش نمیگیرم
اره یه تریس کنید معلوم میشه
(۱۲ مرداد ۱۳۹۳ ۰۴:۳۵ ب.ظ)bernova نوشته شده توسط: اقا شرمنده من نمیدونم چرا حلقه for اینطوری پست شد اینجا منظورم مرتبه اجرایی حلقه زیر استمراحل trace:
for(I=1;I<n;I++)1
for(j=1;j<n;J++)1
}
x++
n--
{
{
بازم ببخشید
i=1---------------> بار n/2
i=2---------------> بار n/4
i=3---------------> بار n/8
i=4--------------> بار n/16
.....................................
i=log n---> بار n/2^ log n
جمع تعداد دفعات تکرار: (n/2+n/4+n/8+n/16+...+n/n=n(1/2+1/4+1/8+...+1/n)=n(1-1/n)=n-1=O(n
(۱۲ مرداد ۱۳۹۳ ۱۰:۳۹ ب.ظ)bernova نوشته شده توسط: اره n-- ,است . یکی از مثال های پارسه استدوستان منم فکر می کنم n log n درست باشه، چون شمارنده حلقه ها به هم وابسته نیستند تعداد تکرار حلقه ها در هم ضرب میشن.
منظورم اینه که تو پارسه میگه O(n و جزوه امیرکبیر میگه O(nlogn به نظر من دومی است
در حلقه داخلی هر بار ۲واحد کاهش داریم چون یک بار j را می بریم جلو و یکبار از n کم می کنیم، پس حقه داخلی هربار n/2 بار اجرا میشه که مرتبه اجراییش میشه n، حالا وقتی از حلقه داخلی خارج میشم n شده n/2 یعنی بازه حلقه بیرونی شده از یک تا n/2 پس مثل اینه که گام کاهش حلقه بیرونی تقسیم بر ۲ هست که مرتبه اجراییش میشه log n ، پس مرتبه اجرایی دو حلقه میشه n log n
کسی فهمید من چی گفتم؟