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

جز
جایگزینی با اشتباه‌یاب: بطور⟸به‌طور
جز (جایگزینی با اشتباه‌یاب: بطور⟸به‌طور)
low = mid + 1;
}
}{{پایان}}حال برای مقایسهٔ کارایی این دو لازم است که تعداد مقایسه‌های انجام شده توسط هر یک از این دو الگوریتم را بطوربه‌طور مثال به ازای ورودی‌های خاص و مشترک برای این دو بدست آوریم. برای این کار مثلاً فرض می‌کنیم که تعداد عناصر آرایهٔ S برابر ۱۶ بوده و عدد x در آرایه نباشد. در این صورت الگوریتم جستجوی ترتیبی ۱۶ مقایسه انجام داده و سپس اعلام می‌کند که x در آرایه موجود نیست و در حالت کلی نیز همواره در بدترین حالت (زمانی که x در آرایه موجود نباشد) تعداد مقایسات در این الگوریتم برابر n (تعداد عناصر آرایه) خواهد بود. (در صورت وجود x در آرایه تعداد مقایسه‌ها کمتر خواهد بود).
و در الگوریتم جستجوی دودویی در حالتی که 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>.