رمز O الكبير

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

رمز O كبير يتطرق لمجموعة من الدوال التي تتعلق فيما بينها بالتسارع بالنسبة للاعداد الطبيعية , وبشكل عام يوجد عدة رموز لاندو كل منها له مفهومه الخاص وقد نشط استخدام هذا الرمز في تحليل سرعة الخوارزميات وذلك لانه في بعض الاحيان حساب عدد الحسابات التي تنفذها خوارزمية قد يكون مستحيلا مع وجود كثير من الامور التي تؤثر على عدد الحسابات وبالتالي فإنه اكثر راحة لنا ان نعطي تقريبا لعدد الحسابات التي تقوم بها الخوارزمية ورمز O كبير يتيح هذا الامر بسهولة .

تعريف[عدل]

  • رمز O كبير: نقول أَنَّ  g(n) \in O(f(n)) او  g(n) = O(f(n)) اذا كان هنالك ثابت c بحيث انه يوجد  n_0 \in N ولكل  n>n_0 يحدث التالي : g(n)\le 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)\ge 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) \le g(n)\le 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) \le 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!)} عاملي حل مسـالة البائع المتجول

انظر أيضا[عدل]

مراجع[عدل]

وصلات خاجية[عدل]