نمایش نتایج 1 تا 15 از 15

نام تاپیک: تکنیکهای طراحی الگوریتم - روش تقسیم و تسخیر

  1. #1
    کاربر دائمی
    تاریخ عضویت
    مرداد 1382
    محل زندگی
    تهران
    پست
    484

    تکنیکهای طراحی الگوریتم - روش تقسیم و تسخیر

    تقسیم و تسخیر <span dir=ltr>(Divide-and-Conquer)</span>

    طراحی الگوریتم در این روش بدین صورت حاصل می‌شود که:
    مورد اصلی مسئله‌ی داده شده برای حل را به چندین مورد کوچکتر (از همان نوع مورد اصلی) تقسیم می‌کنیم٬ سپس موارد کوچکتر را بطور مجزا حل و نتیجه حاصل از هر زیر مورد را با هم ترکیب کرده تا نتیجه مورد اصلی مسئله را بیابیم.

    اگر تاکنون از روتینهای بازگشتی (Recursive Procedures) برای حل مسائل استفاده کرده باشید با روش کار تقسیم و تسخیر از پیش آشنایی دارید.

    الگوریتمهایی که با این روش طراحی می‌‌شوند از دید من بسیار زیبا٬ ساده و خوانا هستند. اما این نکته منفی را هم نباید از قلم انداخت که اگر تعداد موارد منقسم شده از مورد اصلی زیاد باشد٬ ممکن است بازده الگوریتم حاصل از روش تقسیم و تسخیر افت کند.

    مثال 1: جستجوی دودویی (Binary Search)
    در نظر بگیرید که فهرستی از اسامی و آدرسهای مرتبط به هر اسم داشته باشیم و این فهرست دارای N جفت اسم و آدرس باشد که به ترتیب حروف الفبا بر اساس اسم مرتب شده و در دو آرایه نگهداری شوند:

    Names&#40;1..N&#41;
    Numbers&#40;1..N&#41;

    می‌خواهیم با دادن هر اسم٬ آدرس مربوط به اسم را بیابیم. در این مثال فرض می‌کنیم که هر اسم مورد پرسش حتما در آرایه وجود دارد تا الگوریتم و شرح آن را ساده‌تر کرده باشیم.

    الگوریتم تقسیم و تسخیری که این مسئله را حل می‌کند٬ ساده‌ترین الگوریتم در این مدل الگوریتمی است که حاصل نگرشی بگونه زیر است:

    اسم داده شده
    یا
    درست در وسط فهرست قرار دارد
    یا
    در نیمه بالایی فهرست (بالا)
    یا
    در نیمه پایینی فهرست (پایین)

    چون فهرست مرتب شده است٬ پس شرط بالا در صورتی درست است که اسم داده شده کوچکتر از اسم قرارگرفته در قسمت میانی باشد. و شرط پایین در صورتی درست است که اسم داده شده بزرگتر از اسم قرارگرفته در قسمت میانی باشد.

    این دید به مسئله٬ الگوریتم زیر را در پی خواهد داشت:

    function Search&#40;X&#58; name;  Start, Finish&#58; integer&#41;  return address
    Middle&#58; integer
    begin
    Middle &lt;- &#40;Start + Finish&#41; / 2
    if X = Names&#40;Middle&#41; then
    return Numbers&#40;Middle&#41;
    elseif X &lt; Names&#40;Middle&#41; then
    return Search&#40;X, Start, Middle - 1&#41;
    else -- X > Names&#40;Middle&#41;
    return Search&#40;X, Middle + 1, Finish&#41;
    endif
    end

    الگوریتم بالا رو چگونه باید اصلاح کرد تا جوابگوی حالتی باشد که اسم وارد شده در فهرست موجود نیست؟ یا با عبارت متداول برای الگوریتمهای تقسیم و تسخیر، در چه مرحله‌ای این اصلاح صورت گرفته شود؟

    مثال 2: بدست آوردن همه ترکیبهای مجموعه‌ای از عناصر (Permutations)
    با چیدن اعداد 4 و 5 و 8 چه اعدادی می‌توان بدست آورد؟ با چیدن حروف الف و میم و لام در کنار هم چه واژه‌های می‌توان ساخت؟ شرح و الگوریتم حل این مسئله با روش تقسیم و تسخیر را قبلا در جواب پرسش یکی از دوستان در پست دیگری نوشته ام. لطفا به لینک زیر رجوع کنید:
    http://www.barnamenevis.org/vi...?p=13185#13185

    ----------------------------------------------------------------------------------------------------------
    تکنیکهای طراحی الگوریتم - مقدمه

  2. #2
    با سلام

    برای سوال اول :

    function Search&#40;X&#58; name; Start, Finish&#58; integer&#41; return address
    Middle&#58; integer
    begin

    if&#40; finish&lt;start&#41;or&#40;x&lt;start&#41;or&#40;x >finish&#41; then
    return&#40;'موجود نبید'&#41;
    else if

    Middle &lt;- &#40;Start + Finish&#41; / 2
    if X = Names&#40;Middle&#41; then
    return Numbers&#40;Middle&#41;
    elseif X &lt; Names&#40;Middle&#41; then
    return Search&#40;X, Start, Middle - 1&#41;
    else -- X > Names&#40;Middle&#41;
    return Search&#40;X, Middle + 1, Finish&#41;
    endif

    endif
    end


    با تشکر از DelphiArea جهت توجه به این بخش :)

  3. #3
    کاربر دائمی
    تاریخ عضویت
    مرداد 1382
    محل زندگی
    تهران
    پست
    484
    تا حدودی درسته! :wink:

    دونستن اینکه پارامتر Start بزرگتر یا مساوی پارامتر Finish هست کافیه که بدونیم هنوز چیزی برای جستجو (تقسیم) داریم. بطور کلی در روش تقسیم و تسخیر وقتیکه دیگه مسئله قابل تقسیم نیست به معنی اینه که کار تموم شده و نوبت این رسیده که نتایج حاصل از حل زیر مسائل رو برای بدست آوردن نتیجه‌ی مسئله اصلی با هم ترکیب کنیم. به این مرحله مبنای بازگشت (Recursive Base) هم گفته می‌شه.

    اما چرا گفتم که اصلاحی که انجام دادی تا حدودی درسته؟ پارامتر X که به روال فرستاده شده حاوی اسمی است که می‌خواهیم دنبالش بگردیم٬ در صورتی که پارامترهای Start و Finish عددی بوده و نشان دهنده بازه‌ای از آرایه هستند که باید جستجو در آن بازه صورت بگیرد. بنابر‌این منطقا" نمی‌توانیم X را با Start یا Finish مقایسه کنیم. جدا از اینکه نیازی هم به شروط بیشتر نیست.

    function Search&#40;X&#58; name;  Start, Finish&#58; integer&#41;  return address  
    Middle&#58; integer
    begin
    if Start > Finish then
    return موجود نبید
    else
    Middle &lt;- &#40;Start + Finish&#41; / 2
    if X = Names&#40;Middle&#41; then
    return Numbers&#40;Middle&#41;
    elseif X &lt; Names&#40;Middle&#41; then
    return Search&#40;X, Start, Middle - 1&#41;
    else -- X > Names&#40;Middle&#41;
    return Search&#40;X, Middle + 1, Finish&#41;
    endif
    endif
    end

    نقل قول نوشته شده توسط (امید)
    با تشکر از DelphiArea جهت توجه به این بخش :)
    خواهش می‌کنم٬ فقط دارم دست و پا شکسته انجام وظیفه می‌کنم.

  4. #4
    کاربر دائمی
    تاریخ عضویت
    مرداد 1382
    محل زندگی
    تهران
    پست
    484
    در خصوص روش تقسیم و تسخیر یک سوال دیگه مطرح می‌کنم تا نکات بیشتری از این روش روشن بشه.

    در الگوریتم جستجوی بالا٬ ما در هربار نیمی از فهرست را که امکان وجود مورد جستجو در آن نبود، از رده خارج کردیم و جستجو را در نیمه دیگر ادامه دادیم.

    حال فرض کنید که به جای دو قسمت٬ فهرست را به سه قسمت تقسیم می‌کردیم. در این صورت در هر بار فقط یک سوم از فهرست را می‌گشتیم.

    و اما پرسش: آیا با افزایش تقسیمات زمان رسیدن به نتیجه کم می‌شود؟

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

    لطفا تنها خواننده مطالب نباشید و سعی کنید چیزی در پاسخ به این پرسش بنویسید. درست یا نادرست بودن جواب اصلا" مهم نیست٬ مهم درگیر شدن با مسئله و شنیدن همه نقطه نظرات هست.

  5. #5
    فکر میکنم زمان جستجو بشدت کاهش پیدا کنه.در حقیقت جستجوی دودویی که از مدل گراف

    درخت اقتباص شده بصورت ساختار گراف با n نود در میاد یه چیزی تو مایه ها ی ایندکس.

  6. #6
    با سلام

    فکر کنم با زیاد کردن تقسیمات تعداد دستورات IF هم بیشتر شود که در این صورت احتمالا سرعت تفاوت چندانی نخواهد کرد . ( دستور IF دستور سنگین و زمانبری می باشد ).
    برای مثال در تقسیم به 3 قسمت ما 2 IF دیگر هم خواهیم داشت.یعنی در این صورت فرض کنید middle1,middle2 را داریم برای حالت اول که ببینیم x مساوی با middle1 است یا کوچکتر یا مساوی که 2 if داریم و اگر بزرگتر بود همین کار برای middle2 .

  7. #7
    سلام
    من هم اول به این موضوع فکر کردم .البته تا حدودی درسته و این در صورتی هست که تعداد اعضای لیست کم باشه.
    با لیستی با تعداد زیاد تعداد تقسیمات بیشتر که متعاقبا تعداد if بیشتری داره به صرفه تر میشه

  8. #8
    کاربر دائمی
    تاریخ عضویت
    مرداد 1382
    محل زندگی
    تهران
    پست
    484
    قبل از ادامه دادن بحث لازم بود که توضیحی رو در خصوص مقدمات تحلیل یک الگوریتم بگم. پس قبل از خواندن ادامه صحبتم لطفا "تحلیل مقدماتی الگوریتمها" رو بخوانید.

    در مثال جستجوی دودویی، ظاهر امر اینجور نشون می‌ده که هر چی تعداد تقسیمها بیشتر باشه٬ در هر بار تلاش ناموفق٬ ما حجم بیشتری از فهرست رو کنار می‌گذاریم.

    ببینیم اگر تعداد تقسیمات رو به اندازه طول فهرست (N) برسونیم چه حاصلی در بر داره. در این حالت در اولین ورود به روال باید جستجو رو تو یکی از N قسمت انجام بدیم و اگر این قسمت٬ قسمت مورد نظرمون نبود٬ باید جستجو رو در یک قسمت دیگه دنبال کنیم. خوب با این حساب در هر بار ما فقط یک قسمت از N قسمت رو کنار می‌گذاریم در صورتیکه وقتی تعداد تقسیمات کمتر بود قسمت کنار گذاشته شده بزرگتر بود.

    در حقیقت با داشتن N قسمت جستجوی دودویی ما تبدیل میشه به یک جستجوی متوالی به صورت زیر:

    function Search&#40;X&#58; name; N&#58; Integer&#41; return address is
    begin
    for i &#58;= 1 to N loop
    if Names&#40;i&#41; = X then
    return Address&#40;i&#41;
    endif
    end


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

    خوب فعلا"مثال جستجوی دودوئی رو بگذارید کنار تا با مثالی یک کم کلی‌تر رابطه بین تعداد تقسیمات و اندازه‌ی مسئله رو دنبال کنیم تا ببینیم در چه شرایطی به الگوریتم سریعتری خواهیم رسید.

    پرسش:

    در نظر بگیرید که الگوریتمی داریم به نام A که می‌دانیم قادر است مسئله‌ای به اندازه‌ی N را در c N^2 مرحله حل کند (c ضرب در N به توان 2 و c عددی است ثابت). بعدا" الگوریتمی پیدا می‌کنیم به نام B که همان مسئله را بصورت زیر حل می‌کند:
    1. هر مورد از مسئله را به 3 قسمت هر یک به اندازه N / 2 تقسیم می‌کند
    2. 3 قسمت را حل می کند
    3. نتایج حاصل را در d N مرحله ترکیب می‌کند (d ضرب در N و d عددی است ثابت)
    فرض کنید که الگوریتم A برای حل زیر مسائل در مرحله 2 بکار می‌رود.

    با استفاده از رابطه‌ی الگوریتمهای A و B ببینید کدام الگوریتم سریعتر است. و آیا سریعتر بودن یک الگوریتم نسبت به دیگری با اندازه‌ی مسئله رابطه دارد؟

  9. #9
    کاربر دائمی
    تاریخ عضویت
    مرداد 1382
    محل زندگی
    تهران
    پست
    484
    مسئله‌ای که در پرسش پست قبلیم مطرح کردم الگوریتم محاسبه‌ی حاصل ضرب دو عدد n رقمی است.

    ورودیها دو عدد N رقمی مثبت می‌باشند که به صورت زیر نمایش داده می‌شوند:

    و خروجی یک عدد 2N رقمی خواهد بود که به صورت زیر نمایش داده می‌شود:


    طبق الگوریتمی که در مدرسه ابتدایی آموخته‌ایم برای برای بدست آوردن حاصل ضرب دو عدد، تک تک ارقام یک عدد را در عدد دیگر ضرب کرده و حاصلها را با هم جمع می‌کنیم تا حاصل ضرب نهایی دو عدد را بیابیم. این الگوریتم به <span dir=ltr>O(N^2)</span> مرحله برای ضرب دو عدد N رقمی نیاز دارد.

    منظور از مرحله در عبارت بالا عملیات پایه‌‌ی ریاضی است که بر روی دو رقم (عدد تک رقمی) صورت می‌گیرد. مانند 3+4 یا 5*6.

    در سال 1992 فردی به نام <span dir=ltr>A.A. Karatsuba</span> الگوریتم ضرب سریعتری به روش تقسیم و تسخیر یافت که به نام او الگوریتم ضرب کاراتسوبا <span dir=ltr>Karatsuba Multiplication</span> نامیده می‌شود. تعداد مراحل مورد نیاز این الگوریتم <span dir=ltr>O(N^(log 3))</span> یا به عبارتی <span dir=ltr>O(N^1.59)</span> است. الگوریتم کاراتسوبا برای تمام مبناهای عددی معتبر است.

    حالا ببینیم این الگوریتم بر چه اساسی بدست آمده است. اعداد ورودی x و y را در نظر بگیرید:

    واضح است که این دو عدد را می‌توان بصورت زیر هم نمایش داد:

    و نتیجه حاصل ضرب <span dir=ltr>z = x * y</span> را بصورت زیر بیان کرد:


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


    حال فرض کنید که ما ارقام اعداد x و y را به دو قسمت تقسیم کنیم:

    اکنون می‌توانیم اعداد x و y را با استفاده از اعداد a و b و c و d به صورت زیر بیان کنیم:


    با این نگرش به اعداد x و y حاصل ضرب آنها را می‌توانیم به صورت زیر بدست آوریم:

    که در آن عبارتهای (a*c) و (a*d) و (b*c) و (b*d) حاصل ضرب دو عدد N/2 رقمی می‌باشند.

    بدین ترتیب حاصل ضرب دو عدد x و y با استفاده از ترمهای a و b و c و d بدین صورت بیان می‌شود که:
    1. دو عدد تک رقمی بی‌درنگ با هم ضرب می‌شوند. (مبنای بازگشت)
    2. اگر <span dir=ltr>N > 1</span> بود در اینصورت حاصل ضرب دو عدد N رقمی می‌تواند بصورت ترمهایی از 4 عمل ضرب بر روی دو عدد N/2 رقمی بیان شود. (مرحله تقسیم و تسخیر)
    3. برای محاسبه نتیجه حاصل ضرب اعداد x و y داده شده٬ تنها نیاز به جمع 4 حاصل ضرب بدست آمده در مرحله قبل (که در <span dir=ltr>O(N)</span> مرحله صورت می‌گیرد) و ضرب کردن در توانی از 10 هست (که این هم می‌تواند در <span dir=ltr>O(N)</span> مرحله صورت بگیرد٬ زیرا که تنها نیاز است به تعداد لازم صفر در انتهای عدد قرار گیرد). (مرحله ترکیب)

    به عنوان مثال اگر داشته باشیم:
    n = 4
    x = 1026
    y = 7329

    در اینصورت خواهیم داشت:
    a = 10
    b = 26
    c = 73
    d = 29

    پس اعداد x و y بصورت زیر قابل نمایش خواهند بود:

    و در نتیجه حاصل ضرب x و y بصورت زیر محاسبه خواهد شد:


    کاراتسوبا فهمید که می‌توان 4 عمل ضرب موجود در مرحله‌ی تقسیم و تسخیر الگوریتم ساده‌ی بالا را به 3 عمل ضرب کاهش داد. البته کاهش یک عمل ضرب در مرحله تقسیم و تسخیر باعث افزایش جزئی تعداد عملیات پایه در مرحله ترکیب می‌شود (هرچند باز به <span dir=ltr>O(N)</span> مرحله نیاز خواهد داشت).

    چگونه 4 عمل ضرب می‌تواند به 3 عمل ضرب تبدیل شود؟ یک جایگزینی ساده. :idea:
    U = a * c
    V = b * d
    W = &#40;a + b&#41; * &#40;c + d&#41;

    با استفاده از U و V و W خواهیم داشت:
    a * d + b * c = W - U - V

    به همین سادگی 4 عمل ضرب به 3 عمل ضرب تبدیل شد و اکنون می‌توانیم حاصل ضرب دو عدد N رقمی x و y را بصورت زیر بیان کنیم:


    الگوریتم ضرب کاراتسوبا بطور کامل:

    function Karatsuba  &#40;xunder, yunder &#58; n-digit integer;   
    n &#58; integer&#41;
    return &#40;2n&#41;-digit integer

    a, b, c, d &#58; &#40;n/2&#41;-digit integer
    U, V, W &#58; n-digit integer
    begin
    if n = 1 then
    return x&#40;0&#41; * y&#40;0&#41;
    else
    a &#58;= x&#40;n-1&#41; ... x&#40;n/2&#41;
    b &#58;= x&#40;n/2-1&#41; ... x&#40;0&#41;
    c &#58;= y&#40;n-1&#41; ... y&#40;n/2&#41;
    d &#58;= y&#40;n/2-1&#41; ... y&#40;0&#41;
    U &#58;= Karatsuba &#40; a, c, n/2 &#41;
    V &#58;= Karatsuba &#40; b, d, n/2 &#41;
    W &#58;= Karatsuba &#40; a+b, c+d, n/2 &#41;
    return U * 10^n + &#40;W-U-V&#41; * 10^&#40;n/2&#41; + V
    end if
    end Karatsuba

  10. #10
    کاربر دائمی
    تاریخ عضویت
    مرداد 1382
    محل زندگی
    تهران
    پست
    484
    خوب برگردیم سر پرسش بی‌جوابی که داریم:

    در نظر بگیرید که الگوریتمی داریم به نام A که می‌دانیم قادر است مسئله‌ای به اندازه‌ی N را در c N^2 مرحله حل کند (c ضرب در N به توان 2 و c عددی است ثابت). بعدا" الگوریتمی پیدا می‌کنیم به نام B که همان مسئله را بصورت زیر حل می‌کند:
    1. هر مورد از مسئله را به 3 قسمت هر یک به اندازه N / 2 تقسیم می‌کند
    2. 3 قسمت را حل می کند
    3. نتایج حاصل را در d N مرحله ترکیب می‌کند (d ضرب در N و d عددی است ثابت)
    فرض کنید که در مرحله ٬2 از الگوریتم A برای حل زیر مسائل استفاده می‌شود.

    می‌خواهیم با استفاده از رابطه‌ی الگوریتمهای A و B ببینیم کدام الگوریتم سریعتر است٬ و آیا سریعتر بودن یک الگوریتم نسبت به دیگری به اندازه‌ی مسئله رابطه‌ای دارد یا نه.

    با استفاده از فرضیات بالا داریم:
    T&#40;A&#41;&#40;n&#41; = c * &#40;n^2&#41;        طبق تعریف


    T&#40;B&#41;&#40;n&#41; = 3 * T&#40;A&#41;&#40;n/2&#41; + d * n

    = 3 * &#40;c * &#40;n/2&#41;^2&#41; + d * n

    = &#40;3/4&#41; * &#40;c * &#40;n^2&#41;&#41; + d * n

    = &#40;3/4&#41; * T&#40;A&#41;&#40;n&#41; + d * n

    با این حساب برای اینکه زمان اجرای B زمان اجرای A کمتر باشد، باید شرط زیر برقرار باشد:

    d * n &lt; &#40;1/4&#41; * T&#40;A&#41;&#40;n&#41;

    که با جایگزینی زمان اجرای A در شرط بالا خواهیم داشت:
    d * n  &lt;  &#40;1/4&#41; * &#40;c * &#40;n^2&#41;&#41;

    d &lt; &#40;c * n&#41; / 4

    یا به عبارتی

    n > &#40;4 * d&#41; / c


    پس برای مقادیری از N (اندازه مسئله) که N از 4d/c (که عددی است ثابت) بزرگتر است٬ الگوریتم B از الگوریتم A سریعتر خواهد بود.

    با توجه به رابطه‌ی الگوریتم A و B براساس فقط مقدار ثابت 4d/c ٬ می‌توانیم بگوییم که اگر اندازه‌‌ی مسئله (N) به اندازه‌ی بزرگ بود که داشته باشیم:
    n      >  4d/c
    n/2 > 4d/c
    n/4 > 4d/c

    . . .

    n/i^2 > 4d/c

    پیشنهاد می‌شود که از الگوریتم B بجای الگوریتم A استفاده شود و با تکرار الگوریتم B در این مرحله، هر زیر مسئله را به زیر مسائل کوچکتر تقسیم کرده و هرگاه اندازه‌ی زیر مسئله‌ای به مقدار N0 که مساوی یا کوچکتر از 4d/c است رسید٬ ادامه حل آن را با الگوریتم A دنبال کنیم.

  11. #11
    کاربر دائمی
    تاریخ عضویت
    مرداد 1382
    محل زندگی
    تهران
    پست
    484
    شکل کامل یک الگوریتم تقسیم و تسخیر به صورت زیر نوشته می‌شود:
    • اندازه‌ی مسئله (N)
    • مقدار بحرانی اندازه‌ی مسئله که برای کمتر از آن تقسیمی صورت نمی‌گیرد. مقدار بحرانی را مقدار مبنا یا مبنای بازگشت هم میگویند. (N0)
    • اندازه هر زیرمسئله که از تقسیم مسئلهی اصلی حاصل شده است. معمول این است که این اندازه بصورت نسبتی از اندازه‌ی‌ مسئله‌ اصلی به اندازه‌ی زیرمسائل بیان شود. (M)
    • تعداد تقسیمات مسئله‌ی اصلی به زیرمسائل. (R)

    procedure D-and-C &#40;N &#58; input size&#41;
    begin
    if N &lt;= N0 then
    Solve problem without further sub-division
    else
    Split into R sub-instances each of size N/M
    for each of the R sub-instances do
    D-and-C &#40;N/M&#41;
    end for
    Combine the R resulting sub-solutions
    to produce the solution to the original problem
    end if
    end D-and-C

    همانگونه که دیده شد در محاسبه زمان اجرای الگوریتمهای تقسیم و تسخیر سه عامل نقش تعیین کننده دارند:
    • تعداد زیرمسائلی که یک مسئله به آنها تقسیم شده تا بطور مجزا حل شوند. (a)
    • نسبت اندازه‌ی مسئله اصلی به اندازه زیرمسائل. (b)
    • تعداد مراحل مورد نیاز برای تقسیم مسئله اصلی و ترکیب نتایج حاصل از حل هر یک از زیرمسائل٬ که بصورت تابعی از n بیان شدنی است.

    از آنجا که جواب مسئله اصلی از ترکیب جوابهای مسائل کوچکتر حاصل می‌شود و زمان اجرای این فرآیند به نوع مسئله مربوط است، زمان اجرا را بصورت یک چند جمله‌ای بصورت <span dir=ltr>O(n^k)</span> فرض می‌کنیم که در آن k مقداری بزرگتر یا مساوی صفر دارد. با این فرض و همچنین در حالتی که a و b هر دو ثابت باشند (همانند مثالهایی که در بالا داشتیم)، می‌توان زمان اجرای یک الگوریتم تقسیم و تسخیر را بصورت زیر بیان کرد:

           O&#40;1&#41;	               n &lt;= n0
    T&#40;n&#41; =
    a . T&#40;n/b&#41; + O&#40;n^k&#41; n > n0

    با حل معادله بالا، زمان اجرای الگوریتم با تقریبی اندک (asymptotically) توسط فرمول زیر قابل محاسبه خواهد بود (*):

           O&#40;n^k&#41;                if  a &lt; b^k

    T&#40;n&#41; = O&#40;&#40;n^k&#41;.&#40;log&#91;b&#93;n&#41;&#4 1; if a = b^k

    O&#40;n^&#40;log&#91;b&#93;a&#41;&#41;&#41; if a > b^k


    اگر به چگونگی رسیدن به فرمول بالا علاقمندید، جزئیات آن در Running Time of Divide-and-Conquer Algorithms بیان شده است.

    ------------------
    * عبارت <span dir=ltr>log[x]y</span> به معنی لگاریتم y در مبنای x است.

  12. #12
    Kambiz عالی بود
    خیلی ممنون از زحمتتان

  13. #13

    تحليل پيچيدگي فيبوناچي

    با سلام
    مي‌دانيد كه الگوريتم فيبوناچي يك الگوريتم تقسيم و حل محسوب مي‌شود و پيچدگي آن 2 به توان n/2 مي‌باشد خيلي سعي كردم با روش‌هايي به اين پيچيدگي برسم اما به بن بست رسيدم لطفا بدون استفاده از روش استقراء اين كار را برايم انجام دهيد.
    با تشكر

  14. #14

    نقل قول: تکنیکهای طراحی الگوریتم - روش تقسیم و تسخیر

    سلام من سه تا سوال دارم اگه کسی جواب شو میدونه لطف کنه بگه عجله دارم
    1-چرا در جستجوی باینری آرایه رو به دو قسمت تقسیم میکنه در هر مرحله.چرا به سه قسمت تقسیم نمیکنه؟؟
    2-چرا جستجوی باینری روی لیست نیمه مرتب هم جواب می دهد؟؟
    3-چرا برای به دست آوردن خانه وسط آرایه وقتی شماره خانه ابتدا و انتها جمع میشود و بر 2 تقسیم میشود حد بالای عدد به دست آمده را در نظر گرفته و خانه وسط را پیدا میکنیم مثلا آرایه 5 عنصری
    2.5= 2/(1+5)
    و خانه 3 میشود خانه وسط چرا حد پایین را نمیگیریم یعنی 2 ؟؟؟

  15. #15
    کاربر دائمی آواتار FastCode
    تاریخ عضویت
    تیر 1388
    محل زندگی
    /dev/null
    پست
    3,486

    نقل قول: تکنیکهای طراحی الگوریتم - روش تقسیم و تسخیر

    1.برای اینکه دیگه اسمش باینری نمیشه.برای ۳ قسمت جست و جو کنید ternary search
    2.جواب نمیده.
    ۳.چون اونطوری خانه وسط از قلم میافته.

قوانین ایجاد تاپیک در تالار

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