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

برای درک اهمیت الگوریتمهای کارا یا به بیان دیگر لزوم استفاده از الگوریتمهای کاراتر بهتر است دو الگوریتم خاص را برای جستجوی یک عدد در یک آرایهٔ مرتب غیر نزولی با یکدیگر مقایسه کنیم. آن دو الگوریتم عبارتند از: جستجوی ترتیبی (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;
 }

}

حال برای مقایسهٔ کارایی این دو لازم است که تعداد مقایسه‌های انجام شده توسط هر یک از این دو الگوریتم را به‌طور مثال به ازای ورودی‌های خاص و مشترک برای این دو به‌دست آوریم. برای این کار مثلاً فرض می‌کنیم که تعداد عناصر آرایهٔ S برابر ۱۶ بوده و عدد x در آرایه نباشد. در این صورت الگوریتم جستجوی ترتیبی ۱۶ مقایسه انجام داده و سپس اعلام می‌کند که x در آرایه موجود نیست و در حالت کلی نیز همواره در بدترین حالت (زمانی که x در آرایه موجود نباشد) تعداد مقایسات در این الگوریتم برابر n (تعداد عناصر آرایه) خواهد بود. (در صورت وجود x در آرایه تعداد مقایسه‌ها کمتر خواهد بود).

و در الگوریتم جستجوی دودویی در حالتی که x در آرایه موجود نباشد، در هر حلقهٔ while دو بار عدد x با $S[mid]$ مقایسه می‌شود. اما در واقع اگر اجرایی کارا از الگوریتم توسط اسمبلر صورت گیرد در هر بار اجرای حلقهٔ while تنها یک بار x با $S[mid]$ مقایسه می‌شود. در نتیجهٔ این مقایسه حالت مناسب بر اساس مقدار کد شرط تعیین می‌شود. با فرض اینکه الگوریتم جستجوی دودویی از این روش استفاده می‌کند، برای جستجوی عدد x در همان آرایهٔ ۱۶ عنصری که x از همهٔ عناصر آرایه بزرگتر است، این الگوریتم فقط ۵ مقایسه انجام می‌دهد که $log16+1=5$ است (منظور، لگاریتم در مبنای 2 می‌باشد). و البته این بیشترین تعداد مقایسه هاست که با این روش صورت می‌گیرد. (در صورتی که x در آرایه موجود باشد تعداد مقایسه‌ها بیشتر نخواهد بود). حال اگر تعداد عناصر آرایه دو برابر شود یعنی 32 عنصر داشته باشیم، تعداد مقایسات در الگوریتم جستجوی دودویی فقط ۱ مرتبه از حالت قبل بیشتر خواهد بود، یعنی زمانی که اولین مقایسه صورت می‌گیرد و آرایه به دو زیر آرایه تقسیم می‌شود. لذا باز هم در بدترین حالت که x در آرایه موجود نیست، این الگوریتم 6 مقایسه انجام می‌دهد ($log32+1=6$). در حالت کلی هر بار تعداد عناصر آرایه دو برابر شود، یک مرتبه به تعداد مقایسه‌ها افزوده خواهد شد. بر این اساس اگر n یکی از توان‌های 2 و x از همهٔ عناصر یک آرایهٔ n عنصری یزرگتر باشد، در جستجوی دودویی تعداد کل مقایسه‌ها از این رابطه حاصل می‌شود: $logn+1$. در نتیجه زمانی که x از همهٔ عناصر آرایه بزرگتر باشد تعداد مقایسه‌ها در الگوریتم جستجوی دودویی نسبت به الگوریتم جستجوی ترتیبی به ویژه برای مقادیر بزرگ n به مقدار قابل توجهی کمتر خواهد بود. برای نمونه برای n=128 تعداد مقایسه‌ها در جستجوی ترتیبی برابر 128 بوده و در جستجوی دودویی 8 می‌باشد. و برای n=1024 در جستجوی ترتیبی تعداد مقایسه‌ها برابر 1024 بوده و در جستجوی دودویی تنها 9 مقایسه انجام می‌شود. و برای مقادیر بزرگتر n این اختلاف به مراتب بیشتر و چشمگیرتر خواهد بود.

منابع

عنوان اصلی: Foundations of algorithms using C++pseudocode,c2004. Neapolitan,Richard E. Naimipour,kumarss

عنوان ترجمه: طراحی الگوریتم‌ها با استفاده از شبه کد C++ با ترجمه کامل ضمایم. ترجمهٔ سید حجت الله جلیلی انتشارات پارتیان.