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

محاسبه مرتبه اجرایی این کدها

ارسال:
  

one hacker alone پرسیده:

محاسبه مرتبه اجرایی این کدها

سلام دوستان من با روش زیگما مشکل دارم
دوستان اگه وقت کردن ممنون میشم هر کی حوصله داشت یکی از کد های زیر رو حساب کنه
در کل یه دوست برای سه کد زیر میخوایم Smile
کد:
==================۱)
void p(int n)
{
    int sum=0,i=1,j=1;
    while(i<=n)
    {
        for(j=1;j<n;j++)
            sum=sum+j;
        i=i*3;
    }
}
==================۲)
s=0
for(i=1;i<n;i++)
{
    j=1;
    while(j<n)
    {
        s=s+i*j;
        j=j*3;
    }
}
cout<<"s="<<s;


=================۳)
void s(int a[],int n)
{
    for(i=1;i<=n;i++)
    {
        v=a[i];
        j=i-1;
        while(v<a[j] && j>0)
        {
            a[j+1]=a[j];
            j--;
        }
        a[j+1]=v;
    }
}

۰
ارسال:
  

ف.ش پاسخ داده:

RE: محاسبه مرتبه اجرایی این کدها

شما هر بار که به حلقه for می رسید اون رو n بار اجرا می کنید و هر بار فقط یک عمل جمع انجام میدین ، یعنی یک بار به ازای j=1 یکبار به ازای j=2 و .... یعنی دارید :
[tex]\sum_{j=1}^{n-1} 1=n-1[/tex]

هر بار که وارد حلقه while می شید هم for رو اجرا می کنید و هم یک عمل ضرب ، اما چه زمانی وارد حلقه while می شید ؟
ازi=1 و هر بار i*3 میشه تا حداکثر به n برسید. یعنی [tex]\left \lfloor \log n \right \rfloor[/tex] بار (در مبنای ۳)

میتونید n=8 بگیرید تا دلیل حدپایین گذاشتن رو متوجه بشید.

چون i هر بار ۳ برابر میشه نمیشه با سیگما نشونش داد پس من از متغیر k استفاده کردم.

که k=logn در مبنای ۳ هست و در نتیجه i=3^k

[tex]\sum_{k=0}^{\left \lfloor logn \right \rfloor-1}[/tex] بار عملیات داخل while تکرار میشه :

[tex]\sum_{k=0}^{\left \lfloor log n \right \rfloor -1} ( \sum_{j=1}^{n-1}1 1)=(\left \lfloor log n \right \rfloor((n-1) 1))=\left \lfloor log n \right \rfloor(n)[/tex]


-------------------------------

حالا اگه مثلا حلقه for به جای j<n بود j<=i اونوقت اندیس سیگمای درونی وابسته میشد به اندیس سیگمای بیرونی.

[tex]\sum_{k=0}^{\left \lfloor log n \right \rfloor-1}( \sum_{j=1}^{3^{k}}1 1)[/tex]

ارسال:
  

riga پاسخ داده:

RE: محاسبه مرتبه اجرایی این کدها

(۲۷ خرداد ۱۳۹۱ ۰۲:۰۰ ق.ظ)afagh1389 نوشته شده توسط:  شما هر بار که به حلقه for می رسید اون رو n بار اجرا می کنید و هر بار فقط یک عمل جمع انجام میدین ، یعنی یک بار به ازای j=1 یکبار به ازای j=2 و .... یعنی دارید :
[tex]\sum_{j=1}^{n-1} 1=n-1[/tex]

هر بار که وارد حلقه while می شید هم for رو اجرا می کنید و هم یک عمل ضرب ، اما چه زمانی وارد حلقه while می شید ؟
ازi=1 و هر بار i*3 میشه تا حداکثر به n برسید. یعنی [tex]\left \lfloor \log n \right \rfloor[/tex] بار (در مبنای ۳)

میتونید n=8 بگیرید تا دلیل حدپایین گذاشتن رو متوجه بشید.

چون i هر بار ۳ برابر میشه نمیشه با سیگما نشونش داد پس من از متغیر k استفاده کردم.

که k=logn در مبنای ۳ هست و در نتیجه i=3^k

[tex]\sum_{k=0}^{\left \lfloor logn \right \rfloor-1}[/tex] بار عملیات داخل while تکرار میشه :

[tex]\sum_{k=0}^{\left \lfloor log n \right \rfloor -1} ( \sum_{j=1}^{n-1}1 1)=(\left \lfloor log n \right \rfloor((n-1) 1))=\left \lfloor log n \right \rfloor(n)[/tex]

سلام
مرسی توضیحاتتون خیلی خوب بود.فقط یه راهنمایی میخواستم از شماک این که تو توضیحاتتون از نمادهای ریاضی مثل سیگما وتوان استفاده کردین ولی راستش من هر کاری میکردم نمی تونستم اینجا بنویسمشون ، همه چی بهم می ریخت ، واسه همین اونارو توی word نوشتم وبعد attach کردم.

-------------------------------

حالا اگه مثلا حلقه for به جای j<n بود j<=i اونوقت اندیس سیگمای درونی وابسته میشد به اندیس سیگمای بیرونی.

[tex]\sum_{k=0}^{\left \lfloor log n \right \rfloor-1}( \sum_{j=1}^{3^{k}}1 1)[/tex]
یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

riga پاسخ داده:

RE: محاسبه مرتبه اجرایی این کدها

سلام
به نظرم اینجوریهSmile


فایل‌(های) پیوست شده



۰
ارسال:
  

one hacker alone پاسخ داده:

محاسبه مرتبه اجرایی این کدها

دوست عزیز ممنون از جوابتون اما من مراحل کار رو میخواستم بدونم و شما خیلی کلی گفتین
اگه امکان داره هر کدوم از دوستان که وقت میکنن مراحل حل رو بگن به روش زیگما

۰
ارسال:
  

Premier Homme پاسخ داده:

محاسبه مرتبه اجرایی این کدها

ببینید در حالت کلی حلقه وایل از مرتبه logn هست
و حلقه فور از مرتبه n

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

۰
ارسال:
  

ف.ش پاسخ داده:

محاسبه مرتبه اجرایی این کدها

riga جان

موقعی که پاسخ جدید رو میزنید زیر کادر متن نوشته شده نوشتن فرمول در Tex اونجا میتونید راحت فرمولها رو بنویسید و نیازی به Attach هم نداره.

روش نقل قول کردنتون اشتباهه!! باید نوشته های خودتون بعد از نوشته های من باشه نه وسطتش.

۰
ارسال:
  

riga پاسخ داده:

محاسبه مرتبه اجرایی این کدها

این یکی رو بلد بودم ولی اشتباه شد
ممنون از توضیحاتتون.



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
Exclamation سلام لطفاً یکی به من بگه مرتبه زمانی ها چطوری به log تبدیل میشن فرمول داره؟؟ Azadam ۶ ۳,۸۴۱ ۰۶ دى ۱۴۰۰ ۰۹:۰۲ ق.ظ
آخرین ارسال: Soldier's life
  کمک در باره این تروجان Ghasemiyeh ۲ ۲,۶۲۰ ۲۵ آذر ۱۴۰۰ ۰۳:۰۰ ق.ظ
آخرین ارسال: one hacker alone
  سلام بچه های کدهای سیستم تهویه هوا رو کسی داره فاطمه دیبا ۰ ۱,۱۵۷ ۱۲ آبان ۱۴۰۰ ۰۹:۱۲ ق.ظ
آخرین ارسال: فاطمه دیبا
  مرتبه ایجاد درخت rad.bahar ۱ ۳,۰۲۳ ۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ
آخرین ارسال: rad.bahar
  مرتبه شبه کد rad.bahar ۱ ۲,۰۴۰ ۲۲ مهر ۱۳۹۹ ۰۹:۳۲ ب.ظ
آخرین ارسال: BBumir
  چگونه این خطا را موقع اجرای sql server 2014 رفع کنم ؟ farahnaz ۲ ۲,۵۹۶ ۱۹ مهر ۱۳۹۹ ۰۲:۱۸ ق.ظ
آخرین ارسال: farahnaz
  حل مساله مرتبه زمانی حلقه های تو در تو sarashahi ۱۶ ۲۱,۲۰۰ ۱۹ خرداد ۱۳۹۹ ۰۱:۱۶ ب.ظ
آخرین ارسال: gillda
  محاسبه ارتفاع درخت.... baharkhanoom ۳ ۷,۴۵۳ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۸ ب.ظ
آخرین ارسال: mohsentafresh
  مرتبه زمانی Sanazzz ۱۷ ۱۹,۱۳۵ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۶ ب.ظ
آخرین ارسال: mohsentafresh
  پایتون (طراحی وب یا دیتا ساینس؟) مساله این است... sirvan.t ۲ ۳,۱۹۹ ۱۹ بهمن ۱۳۹۸ ۱۲:۰۱ ب.ظ
آخرین ارسال: sirvan.t

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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