ورود به حساب ثبت نام جدید فراموشی کلمه عبور
برای ورود به حساب کاربری خود، نام کاربری و کلمه عبورتان را در زیر وارد کرده و روی “ ورود به حساب” کلیک کنید.





اگر فرم ثبت نام برای شما نمایش داده نمیشود، اینجا را کلیک کنید.









اگر فرم بازیابی کلمه عبور برای شما نمایش داده نمیشود، اینجا را کلیک کنید.





نمایش نتایج: از 1 به 2 از 2
  1. #1
    adminmsp
    مدیر کل و موسس سایت
    تاریخ عضویت
    1970 Jan
    محل سکونت
    M.S.P Soft
    نوشته ها
    1,588
    759
    419

    مقالات تحلیل مقدماتی الگوریتمها به همراه نمونه كد

    سوال:

    چگونه می*توانیم زمان اجرای یک الگوریتم را محاسبه کنیم؟
    چگونه می*توانیم دو تا الگوریتم را با هم مقایسه کنیم؟
    چگونه می*توانیم بگوییم که یک الگوریتم بهینه هست؟

    جواب:
    تعداد عملیات پایه که الگوریتم با بدترین ورودی اجرا می*کند.

    عملیات پایه می*توانند یکی از موارد زیر باشند:

    یک انتساب (Assignment)
    مقایسه*ى دو تا متغییر (Comparison)
    یک محاسبه ریاضی بین دو تا متغیر (Arithmatic Operation)

    بدترین ورودی هم، آن ورودیی است که باعث اجرای بیشترین عملیات پایه می*شود. به عنوان مثال در حلقه زیر با بدترین ورودی بیشترین تکرار 5 است:

        n := 5;
    loop
    get(m);
    n := n -1;
    until (m=0 or n=0)


    و در حلقه زیر با بدترین ورودی بیشترین تکرار n می*باشد:


        get(n);
    loop
    get(m);
    n := n -1;
    until (m=0 or n=0)


    حالا چطور تعداد عملیات پایه را بشماریم؟ برای ساختارهای مختلف الگوریتم به شرح زیر عمل می*کنیم:

    توالی (Sequence):
    P و Q قسمتهای یک الگوریتم هستند.

    زمان کل = زمان(P) + زمان(Q)

    حلقه (Iteration):


      while < condition > loop
    P;
    end loop


    یا

      for i in 1..n loop
    P;
    end loop


    زمان کل = زمان<span dir=ltr>x (P)</span> بیشترین تعداد تکرار

    شرط (Conditional):

     if &lt; condition > then
    P;
    else
    Q;
    end if;



    زمان کل = زمان(P) اگر شرط برقرار باشد
    زمان کل = زمان(Q) اگر شرط برقرار نباشد

    روتینهای بازگشتی (Recursive Procedures):
    در ادامه بحث "تکنیکهای طراحی الگوریتم - روش تقسیم و تسخیر"، در مورد زمان اجرای روتینهای بازگشتی شرح مختصری داده خواهد شد. در اینجا تنها به این نکته بسنده می*کنم که زمان اجرای این روتینها بسته به اندازه ورودی تابعی (توابعی) لگاریتمی است.

    خوب٬ برای نمونه الگوریتم زیر رو در نظر بگیرید:


    for i in 1..n loop
    for j in 1..n loop
    if i &lt; j then
    swop &#40;a&#40;i,j&#41;, a&#40;j,i&#41;&#41;; -- Basic operation
    end if;
    end loop;
    end loop;


    تعداد عملیات پایه &lt; <span dir=ltr>n^2</span> = <span dir=ltr>(n * n * 1)</span>
    با M.S.P Soft به دنياي برنامه نويسي وارد شويد[برای نمایش لینک باید عضو شوید. ]
  2. #2
    adminmsp
    مدیر کل و موسس سایت
    تاریخ عضویت
    1970 Jan
    محل سکونت
    M.S.P Soft
    نوشته ها
    1,588
    759
    419
    برای پیدا کردن یک الگوریتم بهینه٬ در بیشتر موارد میزان افزایش زمان اجرای یک الگوریتم با افزایش اندازه*ی مسئله مورد توجه ماست.

    فرض کنید که سه تا الگوریتم به نامهای P و Q و R داریم که با اندازه ورودیهای مختلف در بدترین شرایط زمان اجرایی طبق جدول زیر دارند:



    n       P             Q              R
    1 1 5 100
    10 1024 500 1000
    100 2^100 50,000 10,000
    1000 2^1000 5,000,000 100,000


    اگر هر کدوم از این الگوریتمها توسط ماشینی که در هر ثانیه یک میلیون <span dir=ltr>(10^6)</span> عمل پایه رو اجرا می*کند اجرا بشوند٬ داریم:


    n       P             Q              R
    1 1 µs 5 µs 100 µs
    10 1 ms 0.5 ms 1 ms
    100 2^70 years 0.05 sec. 0.01 sec.
    1000 2^970 years 5 sec. 0.1 sec.


    همانطور که می*بینید٬ بیان میزان رشد زمان بر حسب <span dir=ltr>(2^n, n^2; n) n</span> معنی*دارتر از بیان آن با فاکتورهای ثابت <span dir=ltr>(1; 5; 100)</span> است.


    نماد O

    فرض کنید <span dir=ltr>f.N -> R</span> و <span dir=ltr>g.N -> R</span> در این صورت داریم:
    1

    f&#40;n&#41; = O&#40;g&#40;n&#41;&#41;


    این به این معناست که مقادیر n0 و c ای وجود دارند که:

    f&#40;n&#41; &lt;= c * g&#40;n&#41;
    که
    n >= n0


    و بر این اساس می*توانیم زمان اجرای یک الگوریتم را بر حسب اندازه ورودی بیان کنیم.

    به عنوان نمونه:

    الگوریتمی برای مرتب کردن n عنصر وجود دارد (mergesort) که زمان اجرای آن <span dir=ltr>O(n log n)</span> است.
    الگوریتمی برای ضرب دو عدد n رقمی وجود دارد که زمان اجرای آن <span dir=ltr>O(n^2)</span> است.
    الگوریتمی برای بدست آوردن nامین عدد سری فیبوناچی وجود دارد که زمان اجرای آن <span dir=ltr>O(log n)</span> است.

    نماد OM

    این نماد برای بیان این مفهوم که یک الگوریتم حداقل نیاز به اجرای تعدادی مرحله دارد بکار می*رود.

    دوباره فرض کنید <span dir=ltr>f.N -> R</span> و <span dir=ltr>g.N -> R</span> در این صورت داریم:
    1

    f&#40;n&#41; = OM&#40;g&#40;n&#41;&#41;


    این به این معناست که مقادیر n0 و c ای وجود دارند که:

     
    f&#40;n&#41; >= c * g&#40;n&#41;
    که
    n >= n0



    نماد THETA

    دوباره فرض کنید <span dir=ltr>f.N -> R</span> و <span dir=ltr>g.N -> R</span>
    اگر <span dir=ltr>f(n)=O(g(n))</span> و <span dir=ltr>f(n)=OM(g(n))</span> داریم:
    1

    f&#40;n&#41; = THETA&#40;g&#40;n&#41;&#41;


    در اینصورت گفته می*شود <span dir=ltr>f(n)</span> با تقریب بسیار کمی با <span dir=ltr>g(n)</span> برابر است.

    اگر <span dir=ltr>f(n) = THETA(g(n))</span> باشد٬ الگوریتمهایی با زمان اجرای <span dir=ltr>f(n)</span> و <span dir=ltr>g(n)</span> با افزایش n بطور برابر افزایش زمان پیدا می*کند.


    روابط بین نمادهای O و OM

    <span dir=ltr>f(n)=O(g(n))</span> اگر و فقط اگر <span dir=ltr>g(n)=OM(f(n))</span>

    اگر <span dir=ltr>f(n)=O(g(n))</span> در اینصورت داریم:

    f&#40;n&#41; + g&#40;n&#41; = O&#40;g&#40;n&#41;&#41; 
    f&#40;n&#41; + g&#40;n&#41; = OM&#40;g&#40;n&#41;&#41;

    f&#40;n&#41; * g&#40;n&#41; = O&#40;g&#40;n&#41;^2&#41;
    f&#40;n&#41; * g&#40;n&#41; = OM&#40;f&#40;n&#41;^2&#41;


    به عنوان نمونه اگر <span dir=ltr>f(n)=10n</span> و <span dir=ltr>g(n)=2n^2</span> باشند:

    f&#40;n&#41; = O&#40;g&#40;n&#41;&#41;
    10n + 2n^2 = O&#40;n^2&#41;
    10n + 2n^2 = OM&#40;n^2&#41;
    &#40;10n&#41; * &#40;2n^2&#41; = O&#40;n^4&#41;
    &#40;10n&#41; * &#40;2n^2&#41; = OM&#40;n^2&#41;
    با M.S.P Soft به دنياي برنامه نويسي وارد شويد[برای نمایش لینک باید عضو شوید. ]
نمایش نتایج: از 1 به 2 از 2

اطلاعات موضوع

کاربرانی که در حال مشاهده این موضوع هستند

در حال حاضر 1 کاربر در حال مشاهده این موضوع است. (0 کاربران و 1 مهمان ها)

موضوعات مشابه

  1. الگوریتم بازگشتی تعیین اول بودن یک عدد
    توسط sina در انجمن الگوریتم، کامپایلر، هوش مصنوعی و ساختمان داده ها
    پاسخ: 0
    آخرين نوشته: 2012-01-14, 07:19 PM
  2. الگوریتم بازگشتی بزرگترین مقسوم علیه دو عدد
    توسط sina در انجمن الگوریتم، کامپایلر، هوش مصنوعی و ساختمان داده ها
    پاسخ: 0
    آخرين نوشته: 2012-01-14, 03:13 PM

کلمات کلیدی این موضوع

مجوز های ارسال و ویرایش

  • شما نمیتوانید موضوع جدیدی ارسال کنید
  • شما امکان ارسال پاسخ را ندارید
  • شما نمیتوانید فایل پیوست کنید.
  • شما نمیتوانید پست های خود را ویرایش کنید
  •  

Content Relevant URLs by vBSEO 3.6.0 RC 2