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

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

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

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

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

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

• بوابة تحليل رياضي
• بوابة رياضيات
• بوابة علم الحاسوب