ساختمان های داده در C (آرایه) صفحه 3

Game Over · 12th January 2010

نشانه گذاري O بزرگ

عوامل متعددي در زمان اجراي الگوريتم موثر هستند،ولي آنچه كه به عنوان كارايي الگوريتم مطرح است،تعداد دفعات اجراي دستورات مي باشد. اين نوع تحليل، در توسعه نرم افزار كارآمد، مهم تر از اندازه گيري مدت زمان اجراي يك الگوريتم بر روي كامپيوتر خاص، برحسب واحدهاي زماني مثل"ثانيه" است.

دانشمندان كامپيوتر، نشانه گذاري ها و اصطلاحات زيادي را براي درك ارتباط بين اندازهوروديو زمان اجرا مطرح كردند. به عنوان مثال، اگر با دو برابر شدن اندازه ورودي (n)، زمان اجراي الگوريتم نيز دوبرابر شود،آن گاه زمان اجراي الگوريتم به طور خطي رشد مي كند. به اين ترتيب، مي گوييم نرخ رشد، مرتبه n است.

ازطرف ديگر، اگر با دو برابر شدن اندازه ورودي، زمان اجراي الگوريتم چهار برابر شود، آن گاه الگوريتم با نرخ توان دوم رشد مي كند. در اين مورد مي گوييم نرخ رشد آن، مرتبه است

Game Over · 12th January 2010

ساده ترين روش محاسبه ي O مربوط به الگوريتم يا برنامه، در نظرگرفتن حلقه هاي تكرار و تودرتو بودن آن ها است.اگر فرض كنيم بدنه حلقه فقط حاوي دستورات ساده است، يك حلقه از O(n)، حلقه تودرتو از o(n) به توان سه است

و غيره. علاوه براين، بايد تعداد دفعات تكرار اجراي حلقه را تعيين كنيد.

Game Over · 12th January 2010

حلقه زير را در نظربگيريد:

for(int i = 1; i < x_length; i*= 2)
{
process x[i];
}

بدنه حلقه k-1 بار اجرا مي شود كه i داراي مقادير 1، 2، 4، 8، 16، 32، ... و

است، به طوري كه 2 به توان k

كوچك تر از x_length مي باشد. لذا مي گوييم اين حلقه از Oلگاریتم n است

Game Over · 12th January 2010

تعريف رسمي نشانه گذاري O بزرگ

برنامه اي را در نظر بگيريد كه به صورت زير پياده سازي شده است:

for(i = 0; i < n; i++) {
for(j = 0; j < n; j++) {
Simple statement
}
}
for(k = 0; k < n; k++) {
Simple statement1
…
Simple statement5
}
Simple statement6
…
Simple statement30

فرض مي كنيم هر"Simple statement" يك واحد زماني را مصرف مي كند. حلقه داخلي، دستور Simple statement را n به توان 2

بار اجرا مي كند، سپس 5 دستور Simple statement

درحلقه اي با انديس kبه تعداد nبار اجرا مي شوند.سرانجام، 25دستور Simple statement اجرا مي گردند. بنابراين، داريم:

T(n)+n2+5n+25

اين عبارت، ارتباط بين زمان پردازش و n را نشان مي دهد. همان طور كه مشاهده مي كنيد، T(n) زمان پردازش را برحسب n بيان مي كند. اكنون رابطه زير را ببينيد:

T(n) = O(f(n))

اين رابطه به معناي اين است كه دو ثابت

n0و

c بزرگ تر از صفر، و تابع f(n) وجود دارند،

به طوري كه براي تمام n>n0

خواهيم داشت cf(n)<=T(n)

.به عبارت ديگر، وقتي n به

اندازه كافي بزرگ مي شود (بزرگ تر از n0

)، ثابتي مثل c وجود دارد كه براي آن، زمان

پردازش همواره كمتر يا مساوي cf(n) است.

Game Over · 12th January 2010

بنابراين cf(n) حد بالاي كارايي است. كارايي هرگز بدتر از cf(n) نخواهد شد و ممكن است بهتر باشد.

Game Over · 12th January 2010

v مقايسه كارايي ها

الگوريتم هاي متعددي در اين كتاب بررسي مي شوند كه كارايي آن ها متفاوت است. چند نرخ رشد متداول را در جدول زير مشاهده مي كنيد:

نمايش

O(1)

O(logn)

O(n)

O(nlogn)

䦋㌌㏒㧀좈໱琰茞ᓀ㵂Ü
䦋㌌㏒㧀좈໱琰茞ᓀ㵂Ü
䦋㌌㏒㧀좈໱琰茞ᓀ㵂Ü

O(n!)

نام

ثابت

لگاريتمي

خطي

لگاريتمي

- خطي

مرتبه 2

مرتبه 3

تواني

فاكتوريل

Game Over · 12th January 2010

جدول زير نشان مي دهد كه وقتي n دوبرابر مي شود (مثلاً از 50 به 100 تبديل مي گردد)، نرخ رشد چگونه تغيير مي يابد. ستون سوم نسبت زمان هاي پردازش را براي دو مقدار مختلف نشان مي دهد. به عنوان مثال، اين ستون نشان مي دهد كه براي الگوريتم O(nlogn)، زمان پردازش 100 عدد، 35/2 برابر زمان لازم براي پردازش 50 عدد است.

F(100)/f(50)

F(100)

F(50)

O(f(n))

1

1.18

2

2.35

4

8

1

6.64

100

664

10,000

100,000

1

5.64

50

283

2500

12,500

O(1)

O(logn)

O(n)

O(nlogn)

O(n!)


صفحه اصلی \| تلویزیون اینترنتی \| فال حافظ شیرازی \| پنل ارسال SMS از اینترنت \| سنجش تمرکز شما \| شهر بازی \| تبليغات \| تماس با مدیران انجمن ها

جدیدترین موضوعات انجمنها دانلود تولبار جی تاک