تمثيل O الكبرى

يتطرق الرمز O الكبير لمجموعة من الدوال التي تتعلق فيما بينها بالتسارع بالنسبة للاعداد الطبيعية، وبشكل عام توجد عدة رموز كل منها له مفهومه الخاص وقد نشط استخدام هذا الرمز في تحليل سرعة الخوارزميات وذلك لأن حساب عدد العمليات التي تنفذها خوارزمية ما قد يكون مستحيلاً في بعض الأحيان مع وجود كثير من الأمور التي تؤثر على عدد العمليات لذا فإن إعطاء تقريب لعدد العمليات التي تقوم بها الخوارزمية أكثر راحةً لنا والرمز O الكبير يتيح هذا الامر بسهولة.[1][2][3]

مثال على رمز O الكبير: ((f(x) ∈ O(g(x بما أنه يوجد c > 0 (كما في المثال، c = 1) وx₀ (كما في المثال، x₀ = 5) حيث (f(x) < cg(x عندما يكون x > x₀.

تعريف

رمز O كبير: نقول أَنَّ $g(n)\in O(f(n))$ أو $g(n)=O(f(n))$ إذا كان هنالك ثابت $c$ بحيث انه يوجد $n_{0}\in N$ ولكل $n>n_{0}$ يحدث التالي: $g(n)\leq c\cdot f(n)$ أي انه إذا تخيلنا رسم الدالتين f و- g حينها نرى ان الدالة f اعلى من الدالة g ابتداء من مكان معين.

على غرار رمز O الكبير يمكن تعريف الرموز التالية:

رمز Ω : نقول أَنَّ $g(n)\in \Omega (f(n))$ أو $g(n)=\Omega (f(n))$ إذا كان هنالك ثابت $c$ بحيث انه يوجد $n_{0}\in N$ ولكل $n>n_{0}$ يحدث التالي: $g(n)\geq c\cdot f(n)$ أي انه إذا تخيلنا رسم الدالتين f و- g حينها نرى ان الدالة f تحت الدالة g ابتداء من مكان معين.
رمز Θ : نقول أَنَّ $g(n)\in \Theta (f(n))$ أو $g(n)=\Theta (f(n))$ إذا كان هنالك ثابت $c_{1},c_{2}$ بحيث انه يوجد $n_{0}\in N$ ولكل $n>n_{0}$ يحدث التالي: $c_{1}\cdot f(n)\leq g(n)\leq c_{2}\cdot f(n)$ أي انه $g(n)=\Theta (f(n))$ إذا $g(n)=O(f(n))$ وأيضا $g(n)=\Omega (f(n))$ أي انَّ الرسم البياني للدالة g محصور بين $c_{1}\cdot f$ وبين $c_{2}\cdot f$ .

تحليل الخوارزميات

عند تحليل خوارزمية ما، نريد حساب عدد الحسابات أو سرعة الخوارزمية أو تعقيدها الحسابي، ونستطيع كتابة التعقيد الحسابي اما عن طريق معادلة عودية واما بطريقة مباشرة، في كلا الحالتين نرمز للتعقيد ب- $T(n)$ عندما n هو طول المُدخل للخوارزمية، مثال لخوارزمية هي خوارزمية البحث الخطي من المفهوم ضمنا ان عدد حساباتها هو: $T(n)=O(n)$ وذلك لانها تقارن كل عدد في القائمة مرة واحدة مع العدد المُدخل وبما ان طول القائمة هو فرضا n عندها عدد حسابات الخوارزمية هو (قيمة المقارنة الواحدة) $\cdot n$ وفيمة المقارنة الواحدة تعتمد على نموذج الحساب (computational model) لذا قد يكون من الصعب اعطاء تقريب لهذه القيمة لذا فانه من المفيد ان نفترض ان قيمة كل مقارنة هو عدد ثابت من الحسابات أي انه: يوجد ثابت c بحيث ان كل مقارنة عدد حساباتها اقل من c ، لذا فاننا نحصل على $T(n)\leq c\cdot n$ وحسب تعريف رمز O الكبير نحصل على انه $T(n)=O(n)$ .

خواص رمز O كبير والرموز الأخرى

الصورة توضح انه باختيار الثابت الصحيح في رمز O الكبير يمكن اهمال احادية الحدود التي أُسها صغير وكذلك يمكن اهمال المعاملات المضروبة باحادية الحدود

اهمال الثوابت والدوال ذات الدرجة الصغيرة

بما ان رمز O الكبير يفترض وجود ثابت c بحيث انه يُحقق امر مُعين (حسب التعريف) لذا فانه يمكن اهمال الثوابت، مثال $T(n)=2\cdot n^{5}+n^{4}+n^{3}$ يمكن اهمال العدد 2 المضروب ب- $n^{5}$ وكذلك يمكن اهمال $n^{4}+n^{3}$ وذلك لانه إذا اخذنا ثابت كبير كفاية يمكن حينها ان نهمل الثوابت واحادية الحدود التي اسها صغير وكذلك المعاملات (انظر إلى الصورة) لذا فانه، $T(n)=O(n^{5})$ وبشكل عام إذا كان تعقيد الخوارزمية متعدد الحدود فاذا كان الاس الأكبر هو k حينها: $T(n)=O(n^{k})$ .

خاصية التعدي

$f(n)=\Theta (g(n))$ وكذلك $g(n)=\Theta (h(n))$ حينئذ يتحقق $f(n)=\Theta (h(n))$

$f(n)=O(g(n))$ وكذلك $g(n)=O(h(n))$ حينئذ يتحقق $f(n)=O(h(n))$

$f(n)=\Omega (g(n))$ وكذلك $g(n)=\Omega (h(n))$ حينئذ يتحقق $f(n)=\Omega (h(n))$

خاصية الانعكاسية

$f(n)=\Theta (f(n))$

$f(n)=O(g(n))$

$f(n)=\Omega (g(n))$

خاصية التماثل

$f(n)=\Theta (g(n))$ إذا وفقط إذا $g(n)=\Theta (f(n))$

جدول دوال

ترميز	تعقيد	مثال لخوارزمية
${\mbox{O(1)}}$	ثابت	مقارنة عددين
${\mbox{O(log(n))}}$	لوغاريثمي	بحث ثنائي
${\mbox{O(n log(n))}}$	لوغاريثمي-خطي	تصنيف اعداد
$O(({\mbox{log}}^{\mbox{c}}{\mbox{(n)))}}$	لوغاريثمي-متعدد	فحص الاولية اي باعطائنا عدد افحص إذا ما هو عدد اولي.
${\mbox{O(n)}}$	خطي	بحث خطي
${\mbox{O(n}}^{2})$	رباعي	ضرب عددين
${\mbox{O(n}}^{\mbox{c}})$	حدودي	ضرب مصفوفتين
${\mbox{O(c}}^{\mbox{n}})$	أسي	تلوين مخطط بثلاثة الوان
${\mbox{O(n!)}}$	عاملي	حل مسـالة البائع المتجول

انظر أيضا

نظرية التعقيد الحسابي

مراجع

"معلومات عن رمز O الكبير على موقع brilliant.org"، brilliant.org، مؤرشف من الأصل في 20 يوليو 2019.
"معلومات عن رمز O الكبير على موقع xlinux.nist.gov"، xlinux.nist.gov، مؤرشف من الأصل في 20 مايو 2019.
"معلومات عن رمز O الكبير على موقع universalis.fr"، universalis.fr، مؤرشف من الأصل في 25 يوليو 2019.

بوابة تحليل رياضي

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] "معلومات عن رمز O الكبير على موقع brilliant.org"، brilliant.org، مؤرشف من الأصل في 20 يوليو 2019.

[2] "معلومات عن رمز O الكبير على موقع xlinux.nist.gov"، xlinux.nist.gov، مؤرشف من الأصل في 20 مايو 2019.

[3] "معلومات عن رمز O الكبير على موقع universalis.fr"، universalis.fr، مؤرشف من الأصل في 25 يوليو 2019.

خوارزميات الترتيب
Theory	نظرية التعقيد الحسابي تمثيل O الكبرى ترتيب كلي قائمة (نوع بيانات مجرد) خوازمية موضعية خوارزمية ترتيب Comparison sort Adaptive sort Sorting network Integer sorting X + Y sorting Transdichotomous model Quantum sort
Exchange sorts	ترتيب الفقاعات Cocktail shaker sort Odd–even sort ترتيب المشط Gnome sort ترتيب سريع Slowsort Stooge sort ترتيب غبي
خوارزمية الاختيار	ترتيب انتقائي تصنيف الكومة Smoothsort Cartesian tree sort Tournament sort Cycle sort Weak-heap sort
Insertion sorts	ترتيب بالإدراج Shellsort Splaysort Tree sort Library sort Patience sorting
Merge sorts	تصنيف دمجي Cascade merge sort Oscillating merge sort Polyphase merge sort
Distribution sorts	American flag sort Bead sort Bucket sort Burstsort Counting sort Interpolation sort Pigeonhole sort Proxmap sort Radix sort Flashsort
Concurrent sorts	Bitonic sorter Batcher odd–even mergesort Pairwise sorting network Samplesort
Hybrid sorts	Block merge sort Kirkpatrick-Reisch sort Timsort Introsort Spreadsort Merge-insertion sort
Other	Topological sorting Pre-topological order Pancake sorting Spaghetti sort