تفاوت میان نسخه‌های «کارایی الگوریتمی»

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

ویرایش