کارآیی الگوریتمی

اهمیت استفاده از الگوریتمهای کارا برای درک اهمیت الگوریتمهای کارا یا به بیان دیگر لزوم استفاده از الگوریتمهای کاراتر بهتر است دو الگوریتم خاص را برای جستجوی یک عدد در یک آرایه ی مرتب غیر نزولی با یکدیگر مقایسه کنیم. آن دو الگوریتم عبارتند از: جستجوی ترتیبی (sequential search) و جستجوی دودویی (binary search).

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

void seqsearch (int n,

           const keytype S[],
           keytype x,
           index& location)

{

    location = 1;
    While (location<=n  &&  S[location]!=x)
        location ++;
    if (location > n)
        location = 0;

}

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

یا x کوچکتر از عنصر میانی است که در چنین حالتی در صورت وجود باید در نیمه ی اول آرایه باشد. لذا با همین روال جستجو را برای نیمه ی اول انجام می دهیم. (اگر x با عنصر میانی نیمه ی اول برابر بود به جواب رسیده ایم و تا انتها همینطور ادامه می دهیم.) و یا x بزرگتر از عنصر میانی است که در این صورت در نیمه ی دوم آرایه جستجو را انجام می دهیم. به همین ترتیب جستجو را تا جایی ادامه می دهیم که به x برسیم و یا اگر تا انتها پیدا نشد عدد صفر را بعنوان خروجی آرایه معرفی می کنیم. یک الگوریتم جستجوی دودویی در زیر آمده است:

void binsearch (int n,

           const keytype S[],
           keytype x,
           index& location)

{

  index low, high, mid;
  low = 1; high = n;
  location = 0;
  while (low <= high && location = 0) {
     mid =[ (low + high)/2 ];
     if (x == S[mid])
       location = mid;
     else if (x < S[mid])
       high = mid – 1;
     else
       low = mid + 1;
  }

}

منابع

عنوان اصلی: Foundations of algorithms using C++pseudocode,c2004. Neapolitan,Richard E. Naimipour,kumarss عنوان ترجمه: طراحی الگوریتم ها با استفاده از شبه کد C++ با ترجمه کامل ضمایم. ترجمه ی حجت الله جلیلی انتشارات پارتیان.