شبكة بحوث وتقارير ومعلومات ®
اليوم: الجمعة 2 يونيو 2023 , الساعة: 8:55 ص


اخر المشاهدات
موضوعات مختارة
موضوعات مميزة


اعلانات
محرك البحث


- سعيد بن مكتوم آل مكتوم حياته # اخر تحديث اليوم 2023-06-02
- اهمية اضافة نخالة القمح لعلائق الدواجن ودوره في تحسين الانتاج # اخر تحديث اليوم 2023-06-02
- [ رقم هاتف ] صيدلية توصيل ادوية في اللولو هايبر ماركت. خدمة 24 ساعة # اخر تحديث اليوم 2023-06-02
- تعرٌف على ... ابراهيم العرجاني | مشاهير # اخر تحديث اليوم 2023-06-02
- نتائج الصف السادس الابتدائي في العراق 2021 جميع المحافظات برقم المقعد بضغطة زر # اخر تحديث اليوم 2023-06-02
- محاذير تركيب اللولب لمن سبق لها الحمل خارج الرحم # اخر تحديث اليوم 2023-06-02
- [رقم هاتف] الطبيب عمير محمود عبداللطيف محمود .. بالاردن # اخر تحديث اليوم 2023-06-02
- نايف بن فواز الشعلان حياته ودراسته # اخر تحديث اليوم 2023-06-02
- نوفالدول أقراص مسكن وخافض للحرارة Novaldol Tablet # اخر تحديث اليوم 2023-06-02
- [ رقم تلفون و لوكيشن ] المحامي محمد سالم محمد العفيفة المري - قطر # اخر تحديث اليوم 2023-06-02
عزيزي زائر شبكة بحوث وتقارير ومعلومات.. تم إعداد وإختيار هذا الموضوع رمز O الكبير تعريف # اخر تحديث اليوم 2023-06-02 فإن كان لديك ملاحظة او توجيه يمكنك مراسلتنا من خلال الخيارات الموجودة بالموضوع.. وكذلك يمكنك زيارة القسم , وهنا نبذه عنها وتصفح المواضيع المتنوعه... آخر تحديث للمعلومات بتاريخ اليوم 13/04/2023

اعلانات

رمز O الكبير تعريف # اخر تحديث اليوم 2023-06-02

آخر تحديث منذ 1 شهر و 20 يوم
4 مشاهدة

تعريف


  • رمز 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 الكبير يمكن تعريف الرموز التالية





    • رمز &Omega نقول أَنَّ 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 ابتداء من مكان معين.

    • رمز &Theta نقول أَنَّ 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_2cdot 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 كبير والرموز الاخرى



    Function growth 2900 nail الصورة توضح انه باختيار الثابت الصحيح في رمز 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!) عاملي حل مسـالة البائع المتجول





    Big-O-notation.png 400 مثال على رمز O الكبير ((f(x) ∈ O(g(x بما أنه يوجد c  >  0 (كما في المثال، c    1) و x0 (كما في المثال، x0    5) حيث (f(x)    x0.

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





    شاركنا رأيك

     
    اعلانات
    التعليقات

    لم يعلق احد حتى الآن .. كن اول من يعلق بالضغط هنا

    أقسام شبكة بحوث وتقارير ومعلومات عملت لخدمة الزائر ليسهل عليه تصفح الموقع بسلاسة وأخذ المعلومات تصفح هذا الموضوع رمز O الكبير تعريف # اخر تحديث اليوم 2023-06-02 ويمكنك مراسلتنا في حال الملاحظات او التعديل او الإضافة او طلب حذف الموضوع ...آخر تعديل اليوم 13/04/2023





    عقارات السعودية
    دليل السعودية
    دليل الكويت
    دليل الامارات
    دليل البحرين
    دليل قطر
    غسيل سجاد الكويت
    المجلس
    سفارات
    4uuo usa guide
    الأكثر قراءة
    موضوعات جديدة
    الاكثر بحثا