ساختمان های داده در c (آرایه)

[shirin71]

تعريف رسمي نشانه گذاري 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) است.

[shirin71]

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

[shirin71]

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

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

نمايش

O(1)

O(logn)

O(n)

O(nlogn)

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

O(n!)

نام

ثابت

لگاريتمي

خطي

لگاريتمي

- خطي

مرتبه 2

مرتبه 3

تواني

فاكتوريل

[shirin71]

جدول زير نشان مي دهد كه وقتي 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!)