کارایی الگوریتم‌ ها

الگوریتم دستورالعملی برای حل مسائل مشخصی است که شامل مجموعه‌ای از دستورات است که به صورت گام به گام راه‌حل مسائل را دنبال می‌کند. الگوریتم باید با تعداد محدودی از مراحل معین به صورت دقیق و غیر مبهم خاتمه یابد. روش‌های رایج الگوریتم‌ها از فلوچارت‌ها و شبه‌ برنامه‌ها تشکیل شده‌اند.

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

در زیر پیشنهادات ساده‌ای که می‌توانند در طراحی الگوریتم‌های مؤثر و کارآمد سودمند باشند بیان شده‌اند.

محاسبات اضافی

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

x = 0;
for(i = 1; i <= n; ++i){
  x = x + 0.05;
  y = (a * a * a + c) * x * x + b * b * x;
 
  printf("%f, %f", x, y);
}

می‌توان توسط پیش‌پردازش بخش‌های ثابت عبارات، قبل از حلقه ‘for’، از برخی محاسبات اضافی جلوگیری کرد.

x   = 0;
a3c = a * a * a + c;
b2  = b * b;
 
for(i = 1; i <= n; ++i) {
  x = x + 0.05;
  y = a3c * x * x + b2 * x;
 
  printf("%f, %f", x, y);
}

ارجاع عنصر آرایه

اگر مراقب نباشید، ناکارآمدی همچنین می‌تواند باعث پردازش آهسته آرایه شود. دو روش زیر را برای پیدا کردن بزرگ‌ترین عنصر آرایه در نظر بگیرید:

v1. 
pos = 0;
 
for (i = 1; i < arraySize; ++i) { 
  if (array[i] > array[pos]) {
     pos = i;
  }
}
max = array[pos];
 
v2. 
pos = 0;
max = array[0];
 
for (i = 1; i < arraySize; ++i) {
  if (array[i] > max) {
    max = array[i];
    pos = i;
  }
}

به طور معمول روش v2 پرکاربردتر است، چرا که دستور (array[i] > max) نسبت به (array[i] > array[pos]) مقایسه مؤثرتری است.

‘array[pos]’ به دو ارجاع حافظه نیاز دارد، ابتدا مکانی برای شروع ‘array’ و سپس به دست آوردن مقدار ‘pos’. علاوه‌براین باید آرایه را برای به دست آوردن nامین موقعیت ‘pos’ در آرایه بپیماییم.

‘max’ فقط به یک ارجاع حافظه برای به دست آوردن مقدار ذخیره شده نیاز دارد.

ناکارآمدی به دلیل دیر خاتمه یافتن:

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

i = 0;
while(i < dictSize) {
  if (name != dict[i]) {
    i++;
  } else {
    printf("Found !!");
  }
}

مثال کارآمدتر با خروجی که سریع ایجاد می‌شود صورت می‌گیرد:

i = 0;
while( name <= dict[i] && i < dictSize) {
  if ( name == dict[i]) {
     printf("Found !!");
     break;
  }
  i++;
}

کیفیت الگوریتم را می‌توان توسط نکات ساده‌ای همچون موارد زیر تشخیص داد:

1. سادگی راه‌حل، مختصر بودن

2. تغییر آسان آن

3. مستقل از یک کامپیوتر خاص، زبان برنامه‌نویسی یا محیط توسعه

به غیر از این موارد، باید مقیاسی برای تحلیل و مقایسه عملکرد الگوریتم‌هایی که راه‌حل مشابهی را ارائه می‌دهند وجود داشته باشد. علامت‌های رایج مربوط به ریاضیات که برای نشان دادن زمان محاسبات الگوریتم استفاده می‌شوند عبارتند از:

علامت O (Oh بزرگ)

محاسبه اولین اعضای ‘n’ سری فیبوناچی (n≥ 2)، همراه با تناوب هر دستورالعمل را در نظر بگیرید.

a = 1;                            ---> frequency 1
b = 1;                            ---> frequency 1
printf("%d %d", a, b);            ---> frequency 1
 
for (i = 1; i <= (n - 2); ++i) {  ---> frequency n-1
  c = a + b;                      ---> frequency n-2
  printf("%d", c);                ---> frequency n-2
  a = b;                          ---> frequency n-2
  b = c;                          ---> frequency n-2
}

بنابراین، تناوب کل f(n) = 5n — 6 است.

این مورد می‌تواند با O(n) نشان داده شود. از آنجا که چند جمله ‌ای ‘n’ است، پیچیدگی زمانی خطی نیز نامیده می‌شود. این دستگاه مستقلی است و به صورت خطی یا به طور مستقیم نسبت به تعداد ‘n’ عدد فیبوناچی محاسبه می‌شود.

الگوریتمی که حتی از مجموعه داده نیز مستقل باشد، گفته می‌شود که در زمان ثابت و با علامت‌گذاری توسط O(1) اجرا می‌شود. مثلا، اضافه کردن دو عدد.

علامت Ω (Omega بزرگ)

علامت O برای نشان دادن کران بالای (بدترین حالت) زمان اجرای الگوریتم استفاده می‌شود در حالی که Ω برای نشان دادن کران پایین یا بهترین حالت سناریو استفاده می‌شود.

برای مثال اعداد فیبوناچی n، اگر n = 2 باشد، تابع ما در یک زمان ثابت اجرا می‌شود که بهترین حالتی است که به صورت f(n) = Ω(1) نشان داده می‌شود.

علامت ϴ (Theta بزرگ)

زمانی که کران بالا و کران پایین یک الگوریتم برابر هستند، یعنی سناریوی بهترین حالت و بدترین حالت زمان یکسانی را با یک فاکتور ثابت در بر می‌گیرند، پیچیدگی آن الگوریتم با علامت ϴ نشان داده می‌شود.

مثلا:

max = array[0];
for (i = 1; i < n; ++i){
  if(array[i] > max) {
     max = array[i];
  }
}

محاسبه زمان برای الگوریتم بالا O(n) و Ω(n) است زیرا حلقه ‘for’ همیشه (n-1) بار از زمان اجرا می‌شود. بنابراین ما می‌گوییم پیچیدگی زمانی آن ϴ(n) است.

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