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

اهمیت الگوریتم های کارا
(ایجاد یک مقاله نو از طریق ایجادگر)
برچسب: منبع‌دهی نادرست (AF)
 
(اهمیت الگوریتم های کارا)
'''اهمیت استفاده از الگوریتمهای کارا '''
'''اهمیت استفاده از الگوریتمهای کارا ''' برای درک اهمیت الگوریتمهای کارا یا به بیان دیگر لزوم استفاده از الگوریتمهای کاراتر بهتر است دو الگوریتم خاص را برای جستجوی یک عدد در یک آرایه ی مرتب غیر نزولی با یکدیگر مقایسه کنیم. آن دو الگوریتم عبارتند از: جستجوی ترتیبی (sequential search) و جستجوی دودویی (binary search).
 
در الگوریتم جستجوی ترتیبی برای یافتن عنصر مشخص x در آرایه، از ابتدای آرایه آغاز کرده و به ترتیب یکی یکی عناصر را با آن مقایسه می کنیم. هرکدام که با عنصر x برابر بود، مکان همان عنصر را در آرایه بعنوان جواب معرفی کرده و در صورت عدم وجود عنصر x عدد صفر را بعنوان خروجی الگوریتم معرفی می کنیم.
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>.
 
 
۲۰

ویرایش