آموزش برنامه نویسی و طراحی وب


طراحی سایت لابدان
طراحی نرم افزار با جاوا


این مقاله جز آموزش های برنامه نویسی نمی باشد و فهرستی برای آن موجود نیست

اهمیت ساخت الگوریتم های کارامد

it3du  
2019-05-21 12:48:24  
75  
algorithm  

تحلیل الگوریتم ها و پیچیدگی زمانی آن

قبل از هر چیزی تعریف کوچکی از الگوریتم ارائه می دهیم. تعاریف مختلفی را می توان برای الگوریتم عنوان کرد. ما به توضیح زیر اکتفا می کنیم

به کار بردن یک تکنیک در حل مسئله منجر به روشی گام به گام در حل آن مسئله می شود. این روش گام به گام را الگوریتم گویند.

در واقع الگوریتم یک روش گام به گام برای حل مسئله است.

برای حل یک مسئله اولین چیز توانایی حل آن با استفاده از یک روش گام به گام (الگوریتم) می باشد. همچنین دو فاکتور زمان و حافظه برای الگوریتم مهم می باشد. زیرا حل یک مسئله با چندین الگوریتم امکان پذیر است اما در بیشتر اوقات فقط یک الگوریتم از سرعت و کارایی بالاتری برخوردار است.

هنگام اجرای الگوریتم روی یک کامپیوتر، منظور از زمان، تعداد چرخه های (cycles) پردازنده است. در حالی که کامپیوتر ها سریع تر و حافظه ها ارزان تر می شود هنوز هم کارایی یک فاکتور مهم برای الگوریتم و نرم افزار ها محسوب می شود. با این حال برای تحلیل الگوریتم چرخه های cpu بررسی نخواهد شد. زیرا قدرت cpu ها با هم متفاوت هستند.

 

چرا ساخت الگوریتم های کارامد اهمیت دارد؟

با افزایش سرعت کامپیوتر ها و کاهش قیمت حافظه، همچنان ساخت یک الگوریتم کارامد از اهمیت بالایی برخوردار است.

بدون هیچ توضیحی با ذکر یک مثال اهمیت کارایی الگوریتم را نشان می دهیم.

فرض کنید لیستی از شماره تلفن افراد، نام و نام خانوادگی آن ها در اختیار شما قرار دارد و این لیست بر اساس حروف الفبا مرتب سازی شده است. یک نام خانوادگی به شما داده می شود و شما باید شماره تلفن این شخص را پیدا کنید.

 

پیدا کردن شماره تلفن با استفاده از جستجوی ترتیبی

به این صورت که شما نام خانوادگی شخص مورد نظر را سطر به سطر با عناصر موجود در لیست مقایسه خواهید کرد. این الگوریتم به درستی کار می کند ولی اگر سطر های شماره تلفن زیاد باشد، این الگوریتم از نظر کارایی بهینه نمی باشد. یعنی اگر در لیست n عنصر وجود داشته باشد، می باست n مقاسه انجام گیرد.

 

پیدا کردن شماره تلفن با استفاده از جستجوی دودویی (Binary search)

فرض می کنیم در هردو حالت لیست افراد بر اساس نام خانوادگی مرتب است و ما به دنبال شماره تلفن فردی به نام رضایی هستیم. مدل جستجوی دودویی به این صورت می باشد که  ابتدا به عنصر وسط لیست نگاه می اندازد. یعنی اگر یک لیست با 32 عنصر داشته باشیم، الگوریتم جستجوی دودویی به عنصر 16 نگاه می اندازد. اگر نام خانوادگی که در عنصر 16 با حرف کوچکتر از ر (که حرف اول کلمه رضایی است) شروع شود، جستجو باید از عناصر 16 به بعد مورد جستجو قرار گیرد. برای درک بهتر، مثال عددی زیر را در نظر بگیرید.

لیست پایین دارای 16 عنصر می باشد که به صورت صعودی مرتب سازی شده است. ما برای پیدا کردن مقدار 50 در لیست بالا به صورت شبه کد زیر عمل می کنیم.

 

54 53 52 50 45 38 35 33 30 28 26 25 20 16 15 12

 

x = 50;
n = [12, 15, 16, 20, 25, 26, 28, 30, 33, 35, 38, 45, 50, 52, 53, 54];
n_size = 16;
low = 1;
hight = n_size;
location = 0;
while (low <= high && location == 0) {

    mid = round( (low + hight) / 2 );

    if (x == n[mid]) {
        location = mid;
    } else if (x < n[mid]) {
        hight = mid - 1;
    } else {
        low = mid + 1;
    }

} // end of while

 

 در کد بالا x عددی است که به دنبالش هستیم.

n آرایه ای است که عناصر در آن به صورت صعودی مرتب سازی شده است.

n_size تعداد عناصر آرایه n می باشد که در مثال ما برابر با مقدار 16 خواهد بود.

حلقه while تا زمانی ادامه می دهد که x پیدا نشده است یا هنوز می توانیم به جستجو ادامه دهیم.

 متغییر location ایندکس عنصر مورد نظر را در خود قرار می دهد. (در صورت پیدا شدن)

 متغییر low محدوده پایین جستجو است که در ابتدای کار به اول آرایه اشاره می کند.

متغییر high محدوده بالا جستجو را مشخص می کند که در ابتدا به آخر آرایه n اشاره می کند.

متغییر mid وسط محدوده low و high است.

متغییری که در خانه با ایندکس mid وجود دارد باید با x مورد سنجش قرار گیرد. در هر گام ما low و high را جمع، حاصل را بر 2 تقسیم می کنیم. این مقدار را رو به پایین گرد می کنیم. مقدار mid ایندکس مکانی از آرایه است که ما می خواهیم ببینیم با x برابر است یا خیر.

این الگوریتم تا جایی ادامه پیدا می کتد که low کوچکتر یا مساوی high باشد. در هر گام اگر x پیدا نشد، کنترل می کنیم اگر n[mid] از x بزرگتر بود یعنی باید high را به عقب تر بیاوریم. در واقع high باید به یک عنصر کمتر از mid انتقال پیدا کند. در غیر اینصورت low به یک عنصر بعد از mid انتقال پیدا خواهد کرد.

اگر x در آرایه موجود باشد، ایندکس (شماره خانه) آن در متغییر location قرار خواهد گرفت.

با توجه به توضیحات بالا، برای یک آرایه با 32 عنصر، تعداد مقایسه های آن برای جستجوی دودویی برابر با لگاریتم 32 به اضافه 1 خواهد بود

 

log32 + 1 = 6

 

یعنی 6 مقایسه انجام خواهد گرفت که در مقایسه با الگوریتم جستجوی ترتیبی بهینه تر است.

بنابر این فرمول به دست آوردن تعداد مقایسه های یک آرایه با X عنصر در جستجوی دودویی به صورت زیر است (لگاریتم در مبنای 2 می باشد)

 

log X + 1

 

تمامی توضیحات در نظر گرفته شده اینطور فرض شده است که X (عددی که به دنبال آن هستیم) از تمامی عناصر موجود در آرایه بزرگتر باشد. یعنی در زمان اجرای الگوریتم تمامی مقایسه ها انجام می شود.

در جدول زیر تعداد مقایسه های انجام شده توسط جستجوی ترتیبی و دودویی، هنگامی که X بزرگتر از همه عناصر آرایه باشد

 

اندازه آرایه تعداد مقایسه های انجام شده در جستجوی ترتیبی تعداد مقایسه های انجام شده در جستجوی دودویی
128 128 8
1024 1024 11
1048576 1048576 21
4294967294 4294967294 33

 

 این مثال همان میزان که جالب است، مطلقا جذاب نیست. زیرا جست و جوی ترتیبی هنوز هم در مقیاس های زمانی قابل تحمل برای انسان، کار ها را سر و سامان می دهد. بنابراین اگر الگوریتم دنباله فیبوناچی را مورد بررسی قرار دهید خواهید دید که برای محاسبه فیبوناچی 5 نیاز به محاسبه فیبوناچی 4، 3، 2 و 1 دارید.

 

دنباله فیبوناچی (Fibonacci Sequence)

دنباله فیبوناچی کاربرد های گوناگونی در علم کامپیوتر و ریاضیات دارد. ما در این مقاله قصد توضیح دنباله فیبوناچی را نداریم. بلکه می خواهیم از بررسی آن به ارزش طراحی یک الگوریتم کارامد پی ببریم.

الگوریتم فیبوناچی که جمله n اُم را از طریق بازگشتی محاسبه می کند به شکل زیر است

 

f(0) = 0
f(1) = 1
f(n) = f(n-1) + f(n-2)    n >= 2 برای

 

با محاسبه این جملات داریم

 

f(2) = f(1) + f(0) = 1 + 0 = 1
f(3) = f(2) + f(1) = 1 + 1 = 2
f(4) = f(3) + f(2) = 2 + 1 = 3
f(5) = f(4) + f(3) = 2 + 3 = 5

 

این الگوریتم فیبوناچی که به صورت بازگشتی (recursive) عمل می کند، جمله nاُم یک عدد صحیح غیر منفی را بدست می آورد (منظور از عدد صحیح غیر منفی، یک عدد ضحیح اکیدا بزرگ تر از صفر است)

 

int fib (int n) {
    
    if (n <= 1) {
        return n;
    } else {
        return fib(n-1) + fib(n-2);
    }

}

 

با اینکه الگوریتم بالا فیبوناچی جمله nاُم را محاسبه می کند اما از نظر کارایی ضعیف است. برای مثال در محاسبه فیبوناچی جمله پنجم fib(5)، به fib(4) و fib(3) نیاز داریم. برای فیبوناچی جمله 3 به fib(2) و fib(1) و همین ترتیب الی آخر. این تابع کارایی ندارد زیرا مقادیر بارها و بارها محاسبه می شوند. برای مثال fib(2) سه بار محاسبه خواهد شد.

جدول زیر تعداد جملات محاسبه شده برای جمله nاُم را نشان می دهد

 

تعداد جملات محاسبه شده n
1 0
1 1
3 2
5 3
9 4
15 5
25 6

 

 شش مقدار نخست را می توان با شمردن گره ها در زیر درختی که ریشه آن fib(n) است، به ازای n بزرگتر مساوی 0 و کوچکتر مساوی 5 بدست آورد، حال آنکه تعداد جملات fib(6) حاصل جمع گره ها در درخت هایی است که ریشه آن fib(5) و fib(4) به علاوه یک گره در ریشه است.

این اعداد عبارت ساده ای همانند آنچه که برای جست و جوی دودویی داشتیم را بدست نمی آورد. با این حال، در هفت مقدار اول که در جدول بالا مشخص است، با هر بار افزایش n به میزان 2 واحد، تعداد جملات در درخت به بیش از دو برابر افزایش می یابد.

برای مثال در n = 4 تعداد جملات درخت برابر با 9 و برای n = 6 تعداد جملات درخت برابر با 25 است.

 

اثبات این قضیه خارج از موضوع مقاله می باشد و ما فقط به این نتیجه گیری اکتفا می کنیم و تعداد جملات محاسبه شده برای تعیین جمله nاُم nn/2 در الگوریتم ذکر شده است. حالا جمله nاُم فیبوناچی (به روش تکراری یا Iterative) را بررسی می کنیم

در الگوریتم بازگشتی با این مشکل رو به رو بودیم که یک مقدار معین بار ها و بار ها محاسبه می شد. بنابراین در روش تکراری اگر پس از محاسبه یک مقدار، آن را در آرایه ای ذخیره کنیم، هرگاه در آینده به آن نیاز بود، لازم نیست دوباره محاسبه شود. الگوریتم با روش تکراری از همین راهبرد استفاده می کند.

 

الگوریتم بالا برای تعیین fib(n) هر یک از n+1 جمله نخست را فقط یک بار محاسبه می کند. بنابراین برای تعیین جمله nاُم تعداد n+1 جمله را محاسبه می کند. با نتایج به وجود آمده از الگوریتم با روش بازگشتی و تکرار، می توان گفت الگوریتم تکراری بهینه تر است. در جدول زیر این دو نتیجه به ازای مقادیر گوناگون مقایسه شده است.

هنگامی که n برابر با 80 باشد، الگوریتم بازگشتی حداقل 18 دقیقه و هنگامی که n برابر با 120 باشد، 36 سال زمان نیاز است!!! بنابراین الگوریتم بازگشتی برای حل این مسئله بهینه نمی باشد مگر آنکه n کوچک باشد. از طرف دیگر الگوریتم فیبوناچی با روش تکراری جمله nاُم را تقریبا بی درنگ محاسبه می کند.

این مقایسه و نتیجه گیری، نشان می دهد که چرا کارایی یک الگوریتم، هرچقدر هم کامپیوتر ها سریع باشند، اهمیت خود را از دست نمی دهند.

 

الگوریتم بازگشتی یک الگوریتم "تقسیم و حل" یا Divide and conquer می باشد. این روش برای مسئله جست و جو در آرایه مرتب شده مناسب بوده. با این حال برای این مسئله کارایی ندارد.

الگوریتم ارائه شده به روش تکراری (Iterative) مثالی از روش برنامه ریزی پویا Dynamic programming می باشد.

 

یادگیری اصول و طراحی الگوریتم، تحلیل الگوریتم، یادگیری روش های طراحی الگوریتم و تمرین کردن برای حل مسئله می تواند به کیفیت برنامه نویسی و طراحی اپلیکیشن ها کمک کند. با مثال های بالا به این نتیجه می رسیم که با وجود پیشرفت کامپیوتر ها و سخت افزار ها همچنان نیاز به طراحی الگوریتم های بهینه و کارامد احساس می شود و از اهمیت بالایی برخوردار است.

شناخت روش ها برای طراحی الگوریتم، بکارگیری صحیح از آن ها برای حل مسئله مهمترین نکته در طراحی یک الگوریتم کارامد است. ما با تمرین و تکرار مسائل از پیش حل شده و استفاده از تجربه های بدست آمده قبلی، علت طراحی یک الگوریتم کارامد را درک کردیم.

هرچه تمرین و تکرار ها بیشتر باشد، ذهن ما برای طراحی الگوریتم های بهتر و مناسب تر آماده تر خواهد بود.

 

منبع: it3du.ir 



طراحی نرم افزار جاوا





به اشتراک بگذارید

فیس نما   فیس نما   فیس نما   فیس نما   فیس نما   فیس نما   فیس نما   کلوب   فیس نما  

مطالب مرتبط


دیدگاه کاربران

دیدگاهی وجود ندارد


دیدگاهی ارسال کنید

  نظر شما پس از تایید نویسنده نمایش داده می شود

  نظرات به صورت فینگلیش تایید و جواب داده نمی شوند

  برای وارد کردن کد برنامه نویسی متن بالای تکست باکس را مطالعه فرمایید

  گزینه captcha برای تشخیص انسان از ربات را حتما قبل از ارسال انتخاب کنید

  ایمیل شما در سایت منتشر نمی شود

  پر کردن فیلد های ستاره دار الزامی می باشد

نام *
ایمیل *
وب سایت

استفاده از کد HTML مجاز نمی باشد

متن های انتخاب شده را می توانید با دکمه p به پاراگراف تبدیل کنید

برای وارد کردن کد برنامه نویسی ابتدا متن مورد نظرتان را انتخاب کنید و سپس زبان مورد نظر خودتان را از طریق دکمه ها انتخاب کنید

محتوای دیدگاه *

خروجی کامنت