عکس پیش‌فرض نوشته

همواره در برنامه نویسی برنامه های کاربردی، انتخاب الگوریتم های کارا و موثر یکی از نکات کلیدی است.

با وجود پیشرفت تکنولوژی سرعت پردازشی کامپیوتر ها افزایش یافته و قیمت حافظه نیز کاهش می باید ولی هنوز هم کارایی الگوریتم های مورد استفاده در برنامه، در عملکرد آن تاثیر به سزایی خواهد گذاشت.

برای درک بهتر این موضوع، در ادامه دو الگوریتم جستجوی مختلف را بررسی خواهیم کرد تا اهمیت مسئله واضح تر باشد.

جستجوی ترتیبی و جستجوی دودویی

 

همانطور که میدانید در جستجوی ترتیبی (Sequential Search) به ترتیب تمام عناصر موجود را با عنصر مورد جستجو مقایسه میکنیم؛ به این صورت که عنصر مورد جستجو را ابتدا با اولین عنصر لیست مقایسه کرده، اگر یکسان نبودند به سراغ عنصر بعدی میرویم.

واضح است که اگر به انتهای لیست برسیم و هیچ یک از عناصر آن با عنصر ما برابر نباشد بدان معناست که عنصر مورد نظر در لیست وجود ندارد.

الگوریتم کلی جستجوی ترتیبی در یک آرایه (هر نوع لیستی از عناصر) به صورت شبه کد (Pseudocode) زیر می باشد.

Algorithm Sequential_Search(KeyType[] L, KeyType x){
    foreach (y in L){
        if (y matches x) return y;     //or return true
    }
    return no match;
}

 

رویه جستجو در جستجوی دودویی متفاوت تر است.

جستجوی دودویی (Binary Search) در یک آرایه مرتب غیر نزولی چیزی مشابه جستجوی یک فرد در دفترچه تلفن است.

فرض کنید که به دنبال x در یک لیست مرتب میگردیم. در ابتدا عنصر را با عنصر میانی لیست مقایسه میکنیم، اگر این مقایسه درست بود (دو عنصر با هم یکسان بودند) یعنی جستجو نتیجه داده و الگوریتم به پایان میرسد.

ولی اگر مقایسه نادرست بود، چک میکنیم که اگر x کوچکتر از عنصر میانی بود، جستجویی مشابه را در نیمه اول لیست انجام دهد و اگر x بزرگتر از عنصر میانی بود، در نیمه دوم لیست به دنبال x بگردد.

وقتی برای جستجو به یکی از نیمه ها رفتیم، همین الگوریتم دوباره اجرا میشود، یعنی x با عنصر میانی آن نیمه از لیست مقایسه شده و …

اگر به مرحله ای رسیدیم که زیر لیست داده شده به ما هیچ عضوی نداشت، بدان معناست که x در لیست اصلی وجود ندارد.

 

الگوریتم کلی جستجوی دودویی در یک لیست مشابه شبه کد (Pseudocode) زیر است.

Algorithm Binary_Search(KeyType[] L, KeyType x){
    n = length of L, i = n/2;
    if (n == 0) return no match;
    else if (L[i] matches x) return L[i];          //or return true
    else if (L[i] > x) Binary_Search(L[1...i-1], x);
    else Binary_Search(L[i+1...n], x);
}

 

اکنون کار انجام شده توسط جستجوی دودویی و جستجوی ترتیبی را مقایسه میکنیم. برای این منظور، تعداد مقایسه های انجام شده توسط هر دو الگوریتم را تعیین میکنیم.

اگر لیستی حاوی 64 عنصر داشته باشیم و x که عنصر مورد جستجوی ماست در این لیست وجود نداشته باشد، نتایج جستجو به صورت زیر خواهد بود.

در جستجوی ترتیبی، x با تمام عناصر لیست مقایسه شده و مشخص میشود که در لیست وجود ندارد؛ یعنی ما 64 مقایسه انجام داده ایم.

در جستجوی دودویی که در دسته بندی الگوریتم های تقسیم و حل (Divide and Conquer) قرار میگیرد، x با عنصر میانی (در این مثال عنصر شماره 32) مقایسه میشود؛ فرض کنیم که x از عنصر سی و دوم بزرگتر باشد، در اینصورت عملیات مقایسه با عنصر شماره 48 انجام میشود و به همین منوال (اگر فرض کنیم x از تمام عناصر لیست بزرگتر است) عملیات مقایسه به ترتیب با عناصر 56 و 60 و 62 و 63 و 64 انجام شده و در نهایت مشخص میشود که جستجو بی نتیجه است.

دیدید که در جستجوی دودویی با انجام تنها 7 مقایسه توانستیم به نتیجه برسیم.

در آنالیز الگوریتم جستجوی دودویی مشخص میشود که مرتبه زمانی آن به صورت ln(n)+1 است. (منظور از ln لگاریتم در مبنای 2 می باشد.)

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

 

اگر اندازه لیست را دو برابر کنیم (یعنی لیست دارای 128 عنصر باشد) تعداد مقایسه های انجام شده با الگوریتم جستجوی ترتیبی برابر 128 خواهد بود در حالی که این مقدار در الگوریتم جستجوی باینری 8 میشود.

 

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

البته باید در نظر داشت که الگوریتم می بایست با توجه به برنامه و نوع کاربرد ما انتخاب شود؛ در هنگام جستجو اگر لیست عناصر ما مرتب شده نباشند، نمیتوان از جستجوی دودویی استفاده کرد و یا باید ابتدا لیست را مرتب کنیم.

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

این آموزش بیش از ۳ سال قبل ارسال شده و اکنون در لیست به‌روزرسانی‌های سایت قرار دارد. اگر پیشنهاد یا انتقادی برای بهبود آموزش دارید، خوشحال می‌شیم به ما اطلاع بدهید.