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

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

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

           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 برسیم یا اگر تا انتها پیدا نشد عدد صفر را بعنوان خروجی آرایه معرفی می‌کنیم. یک الگوریتم جستجوی دودویی در زیر آمده‌است:

           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 با ${\displaystyle S[mid]}$