ما هو التفسير الإنجليزي البسيط لتدوين "Big O"؟

Question

أفضّل أقل قدر ممكن من التعريف الرسمي والرياضيات البسيطة.

Answer 1

ملاحظة سريعة ، هذا بالتأكيد محير تدوين كبير (وهو الحد الأعلى) مع تدوين theta "θ" (وهو حدود ثنائية). في تجربتي ، هذا هو في الواقع مناقشات في البيئات غير الأكاديمية. نعتذر عن التسبب في أي أرتباك.

---

يمكن تصور التعقيد الكبير مع هذا الرسم البياني:

أبسط تعريف يمكنني تقديمه للتدوين الكبير هو:

التدوين الكبير O هو تمثيل نسبي لتعقيد الخوارزمية.

هناك بعض الكلمات المهمة والاختيار عمدا في تلك الجملة:

• نسبيا: يمكنك فقط مقارنة التفاح بالتفاح. لا يمكنك مقارنة خوارزمية للقيام بالضرب الحسابي لخوارزمية ترسل قائمة من الأعداد الصحيحة. لكن مقارنة خوارزميتين للقيام بعمليات حسابية (مضاعفة واحدة ، إضافة واحدة) ستخبرك بشيء ذي معنى ؛
• التمثيل: Big-O (في أبسط أشكاله) يقلل من المقارنة بين الخوارزميات إلى متغير واحد. يتم اختيار هذا المتغير بناءً على الملاحظات أو الافتراضات. على سبيل المثال ، تتم مقارنة خوارزميات الفرز عادةً بناءً على عمليات المقارنة (مقارنة العقدتين لتحديد ترتيبها النسبي). هذا يفترض أن المقارنة باهظة الثمن. ولكن ماذا لو كانت المقارنة رخيصة ولكن التبديل باهظ الثمن؟ يغير المقارنة. و
• تعقيد: إذا كان الأمر يتطلب مني ثانية واحدة لفرز 10،000 عنصر ، فكم من الوقت سيستغرق مني فرز مليون؟ التعقيد في هذه الحالة هو مقياس نسبي لشيء آخر.

عد وأعد قراءة ما سبق عندما تقرأ الباقي.

أفضل مثال على Big-O يمكنني التفكير فيه هو القيام بحساب. خذ رقمين (123456 و 789012). وكانت العمليات الحسابية الأساسية التي تعلمناها في المدرسة:

• إضافة؛
• الطرح
• عمليه الضرب؛ و
• قطاع.

كل من هذه عملية أو مشكلة. وتسمى طريقة حل هذه خوارزمية.

الإضافة هي أبسط. يمكنك ربط الأرقام (إلى اليمين) وأضف الأرقام في عمود يكتب الرقم الأخير من تلك الإضافة في النتيجة. يتم نقل جزء "TENS" من هذا الرقم إلى العمود التالي.

لنفترض أن إضافة هذه الأرقام هي أغلى عملية في هذه الخوارزمية. من المنطقي أن نضيف هذين الرقمين معًا ، يتعين علينا إضافة 6 أرقام (وربما تحمل 7). إذا أضفنا رقمين 100 رقم معا ، علينا أن نفعل 100 إضافة. إذا أضفنا اثنين 10،000 أرقام أرقام علينا أن نفعل 10،000 إضافة.

ترى النمط؟ ال تعقيد (كونه عدد العمليات) يتناسب بشكل مباشر مع عدد الأرقام ن في العدد الأكبر. نسمي هذا على) أو التعقيد الخطي.

الطرح مشابه (باستثناء أنك قد تحتاج إلى الاقتراض بدلاً من حمل).

الضرب مختلف. تقوم بتصنيع الأرقام ، واتخذ الرقم الأول في الرقم السفلي وضربه بدوره مقابل كل رقم في الرقم العلوي وما إلى ذلك من خلال كل رقم. لذلك لضرب أرقامنا المكونة من 6 أرقام ، يجب أن نفعل 36 مضاعفة. قد نحتاج إلى القيام بما يصل إلى 10 أو 11 عمودًا يضيف للحصول على النتيجة النهائية أيضًا.

إذا كان لدينا رقمين مكون من 100 رقم ، فنحن بحاجة إلى القيام بنسبة 10000 مضاعف و 200 إضافة. بالنسبة إلى رقم مليون رقم ، نحتاج إلى القيام بتريليون واحد (10¹²) مضاعفات ومليون يضيف.

كما تحيط الخوارزمية مع n-مربعة, ، هذا هو على²) أو التعقيد التربيعي. هذا هو الوقت المناسب لتقديم مفهوم مهم آخر:

نحن نهتم فقط بجزء أهم من التعقيد.

ربما أدرك الذكاء أنه يمكننا التعبير عن عدد العمليات على النحو التالي: ن² + 2n. ولكن كما رأيت من مثالنا برقمين من مليون رقم لكل منهما ، يصبح المدة الثانية (2N) ضئيلة (تمثل 0.0002 ٪ من إجمالي العمليات بحلول تلك المرحلة).

يمكن للمرء أن يلاحظ أننا افترضنا أسوأ سيناريو الحالات هنا. على الرغم من مضاعفة الأرقام 6 أرقام إذا كان أحدها 4 أرقام والآخر هو 6 أرقام ، فإن لدينا فقط 24 مضاعفة. ما زلنا نحسب أسوأ سيناريو للحالة لذلك "n" ، أي عندما يكون كلاهما 6 أرقام. وبالتالي فإن الترميز الكبير O هو أسوأ سيناريو لحالات الخوارزمية

دفتر الهاتف

أفضل مثال يمكن أن أفكر فيه هو دفتر الهاتف ، الذي يُطلق عليه عادة الصفحات البيضاء أو ما شابه ذلك ، لكنه سيختلف من بلد إلى آخر. لكنني أتحدث عن الشخص الذي يسرد الأشخاص حسب اللقب ثم الأحرف الأولى أو الاسم الأول ، وربما العنوان ثم أرقام الهواتف.

الآن إذا كنت تقوم بتوجيه جهاز كمبيوتر للبحث عن رقم الهاتف لـ "John Smith" في دفتر هاتفي يحتوي على 1،000،000 اسم ، ماذا ستفعل؟ تجاهل حقيقة أنه يمكنك تخمين إلى أي مدى بدأت في S (دعنا نفترض أنك لا تستطيع) ، ماذا ستفعل؟

قد يكون التنفيذ النموذجي هو الانفتاح على الوسط ، خذ 500000^العاشر وقارنها بـ "سميث". إذا حدث أن يكون "سميث ، جون" ، فقد حظينا محظوظين. على الأرجح هو أن "جون سميث" سيكون قبل أو بعد هذا الاسم. إذا كان بعد ذلك ، نقسم النصف الأخير من دفتر الهاتف إلى النصف وكرر. إذا كان ذلك قبل ذلك ، فسنقسم النصف الأول من دفتر الهاتف إلى النصف ونتكرر. وهلم جرا.

وهذا ما يسمى أ بحث ثنائي ويستخدم كل يوم في البرمجة سواء أدركت ذلك أم لا.

لذا ، إذا كنت ترغب في العثور على اسم في دفتر هاتف يضم مليون اسم ، فيمكنك بالفعل العثور على أي اسم عن طريق القيام بذلك على الأقل 20 مرة. عند مقارنة خوارزميات البحث ، نقرر أن هذه المقارنة هي "N".

• للحصول على دفتر هاتف مكون من 3 أسماء ، يستغرق الأمر مقارنتين (على الأكثر).
• لمدة 7 يستغرق الأمر 3 على الأكثر.
• لمدة 15 يستغرق 4.
• …
• مقابل 1،000،000 يستغرق 20.

هذا جيد بشكل مذهل أليس كذلك؟

من حيث الشروط الكبيرة هذا س (سجل ن) أو التعقيد اللوغاريتمي. الآن يمكن أن يكون اللوغاريتم المعني ln (base e) ، سجل₁₀, ، سجل₂ أو بعض قاعدة أخرى. لا يهم أنه لا يزال O (log n) تمامًا مثل O (2n²) و o (100n²) لا يزال كلاهما o (n²).

من المفيد في هذه المرحلة أن نوضح أنه يمكن استخدام Big O لتحديد ثلاث حالات مع خوارزمية:

• أفضل حالة: في البحث عن دفتر الهاتف ، فإن أفضل حالة هي أن نجد الاسم في مقارنة واحدة. هذا هو س (1) أو التعقيد المستمر;
• الحالة المتوقعة: كما تمت مناقشته أعلاه هو o (log n) ؛ و
• الحالة الأسوأ: هذا هو أيضا o (log n).

عادة لا نهتم بأفضل حالة. نحن مهتمون بالحالات المتوقعة والأسوأ. في بعض الأحيان سيكون واحد أو آخر من هذه أكثر أهمية.

العودة إلى دفتر الهاتف.

ماذا لو كان لديك رقم هاتف وترغب في العثور على اسم؟ لدى الشرطة دفتر هاتف عكسي ، لكن هذه عمليات البحث يتم رفضها للجمهور العام. او انهم؟ من الناحية الفنية ، يمكنك عكس البحث عن رقم في دفتر هاتف عادي. كيف؟

تبدأ من الاسم الأول ومقارنة الرقم. إذا كانت مباراة رائعة ، إن لم يكن ، فأنت تنتقل إلى التالي. عليك أن تفعل ذلك بهذه الطريقة لأن دفتر الهاتف هو غير مرتبة (عن طريق رقم الهاتف على أي حال).

حتى تجد اسمًا يُعطى رقم الهاتف (البحث العكسي):

• أفضل حالة: س (1) ؛
• الحالة المتوقعة: س (ن) (مقابل 500000) ؛ و
• الحالة الأسوأ: س (ن) (مقابل 1،000،000).

بائع السفر

هذه مشكلة شهيرة في علوم الكمبيوتر وتستحق ذكرها. في هذه المشكلة لديك مدن ن. ترتبط كل من هذه البلدات بمدينتين أو أكثر من طريق مسافة معينة. مشكلة البائع المتجول هي العثور على أقصر جولة تزور كل بلدة.

تبدو بسيطة؟ فكر مرة اخرى.

إذا كان لديك 3 مدن A و B و C مع طرق بين جميع الأزواج ، فيمكنك الذهاب:

• A → B → C
• A → C → B
• ب → ج → أ
• ب → أ → ج
• ج → أ → ب
• ج → ب → أ

حسنًا ، هناك في الواقع أقل من ذلك لأن بعضها متكافئ (A → B → C و C → B → A متكافئ ، على سبيل المثال ، لأنهم يستخدمون نفس الطرق ، في الاتجاه المعاكس).

في الواقع هناك 3 احتمالات.

• خذ هذا إلى 4 مدن ولديك (IIRC) 12 إمكانيات.
• مع 5 هو 60.
• 6 يصبح 360.

هذه وظيفة لعملية رياضية تسمى أ العامل. أساسًا:

• 5! = 5 × 4 × 3 × 2 × 1 = 120
• 6! = 6 × 5 × 4 × 3 × 2 × 1 = 720
• 7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5040
• …
• 25! = 25 × 24 × … × 2 × 1 = 15,511,210,043,330,985,984,000,000
• …
• 50! = 50 × 49 × … × 2 × 1 = 3.04140932 × 10⁶⁴

لذا فإن مشكلة البائع الكبير من O على!) أو التعقيد العليا أو التوافقي.

بحلول الوقت الذي تصل فيه إلى 200 مدينة ، لم يتبق وقت كافٍ في الكون لحل المشكلة مع أجهزة الكمبيوتر التقليدية.

شيء لتفكر به.

وقت البولينمال

نقطة أخرى أردت أن أذكرها بسرعة هي أن أي خوارزمية لها تعقيد على^أ) يقال أن لديه التعقيد متعدد الحدود أو قابلة للحل في وقت البولينمال.

o (n) ، o (n²) إلخ. كلها وقت متعدد الحدود. لا يمكن حل بعض المشكلات في الوقت متعدد الحدود. تستخدم بعض الأشياء في العالم بسبب هذا. تشفير المفتاح العام هو مثال رئيسي. من الصعب حسابيًا إيجاد عاملين رئيسيين لعدد كبير جدًا. إذا لم يكن الأمر كذلك ، فلن نتمكن من استخدام أنظمة المفاتيح العامة التي نستخدمها.

على أي حال ، هذا كل شيء لتوضيح (نأمل أن تكون اللغة الإنجليزية البسيطة) لـ Big O (المنقحة).

Answer 2

إنه يوضح كيف تتراوح خوارزمية.

على²): معروف ك التعقيد التربيعي

• 1 البند: 1 ثانية
• 10 عناصر: 100 ثانية
• 100 عنصر: 10000 ثانية

لاحظ أن عدد العناصر يزداد بعامل 10 ، لكن الوقت يزداد بعامل 10². في الأساس ، ن = 10 وهكذا يا (ن²) يعطينا عامل التحجيم ن² وهو 10².

على): معروف ك التعقيد الخطي

• 1 البند: 1 ثانية
• 10 عناصر: 10 ثوانٍ
• 100 عنصر: 100 ثانية

هذه المرة يزداد عدد العناصر بعامل 10 ، وكذلك الوقت. ن = 10 وهكذا عامل التحجيم هو 10.

س (1): معروف ك التعقيد المستمر

• 1 البند: 1 ثانية
• 10 عناصر: 1 ثانية
• 100 عنصر: 1 ثانية

لا يزال عدد العناصر يزداد بعامل 10 ، لكن عامل التحجيم لـ O (1) هو دائمًا 1.

س (سجل ن): معروف ك التعقيد اللوغاريتمي

• 1 البند: 1 ثانية
• 10 عناصر: 2 ثانية
• 100 عنصر: 3 ثوان
• 1000 عنصر: 4 ثوان
• 10000 عنصر: 5 ثوان

يتم زيادة عدد الحسابات فقط عن طريق سجل قيمة الإدخال. لذلك في هذه الحالة ، على افتراض أن كل حساب يستغرق ثانية واحدة ، سجل الإدخال n هو الوقت المطلوب ، وبالتالي log n.

هذا هو جوهره. أنها تقلل من الرياضيات لأسفل حتى لا تكون بالضبط n² أو أيا كان ما يقولونه ، لكن هذا سيكون العامل المهيمن في التحجيم.

Answer 3

تدوين Big-O (يُسمى أيضًا تدوين "النمو المقارب") هو كيف تبدو الوظائف عندما تتجاهل العوامل الثابتة والأشياء القريبة من الأصل.نستخدمها للحديث عنها كيف مقياس الشيء.

---

الأساسيات

لمدخلات كبيرة "بما فيه الكفاية" ...

• f(x) ∈ O(upperbound) وسائل f "لا ينمو بشكل أسرع من" upperbound
• f(x) ∈ Ɵ(justlikethis) يقصد f "ينمو تماما مثل" justlikethis
• f(x) ∈ Ω(lowerbound) وسائل f "لا ينمو بشكل أبطأ من" lowerbound

لا يهتم تدوين big-O بالعوامل الثابتة:الوظيفة 9x² يقال أنه "ينمو تمامًا مثل" 10x².ولا الكبير O مقارب رعاية التدوين غير مقارب stuff ("أشياء قريبة من الأصل" أو "ماذا يحدث عندما يكون حجم المشكلة صغيرًا"):الوظيفة 10x² يقال أنه "ينمو تمامًا مثل" 10x² - x + 2.

لماذا تريد تجاهل الأجزاء الأصغر من المعادلة؟لأنها تتضاءل تمامًا أمام الأجزاء الكبيرة من المعادلة عندما تفكر في المقاييس الأكبر فأكبر؛تصبح مساهمتهم ضئيلة وغير ذات صلة.(انظر قسم المثال.)

وبعبارة أخرى، الأمر كله يتعلق بـ نسبة كما تذهب إلى ما لا نهاية. إذا قمت بتقسيم الوقت الفعلي الذي يستغرقه على O(...), ، سوف تحصل على عامل ثابت في حد المدخلات الكبيرة. حدسيًا هذا منطقي:الوظائف "تشبه" بعضها البعض إذا كان بإمكانك مضاعفة واحدة للحصول على الأخرى.يعني عندما نقول...

actualAlgorithmTime(N) ∈ O(bound(N))
                                       e.g. "time to mergesort N elements 
                                             is O(N log(N))"

...هذا يعني ذاك لأحجام المشاكل "الكبيرة بما فيه الكفاية" N (إذا تجاهلنا الأشياء القريبة من الأصل)، فهناك بعض الثوابت (على سبيل المثال:2.5، مكونة بالكامل) بحيث:

actualAlgorithmTime(N)                 e.g. "mergesort_duration(N)       "
────────────────────── < constant            ───────────────────── < 2.5 
       bound(N)                                    N log(N)         

هناك العديد من الخيارات الثابتة؛غالبًا ما يُعرف الاختيار "الأفضل" باسم "العامل الثابت" للخوارزمية ...لكننا غالبًا ما نتجاهلها كما نتجاهل المصطلحات غير الأكبر (راجع قسم العوامل الثابتة لمعرفة سبب عدم أهميتها عادةً).يمكنك أيضًا التفكير في المعادلة أعلاه باعتبارها حدًا، قائلًا "في أسوأ السيناريوهات، لن يكون الوقت الذي يستغرقه الأمر أسوأ من الوقت التقريبي N*log(N), ، ضمن عامل 2.5 (عامل ثابت لا نهتم به كثيرًا)".

على العموم، O(...) هو الأكثر فائدة لأننا غالبًا ما نهتم بالسلوك الأسوأ.لو f(x) يمثل شيئًا "سيئًا" مثل استخدام المعالج أو الذاكرة، ثم "f(x) ∈ O(upperbound)" وسائل "upperbound هو السيناريو الأسوأ لاستخدام المعالج/الذاكرة".

---

التطبيقات

باعتبارها بنية رياضية بحتة، لا يقتصر تدوين Big-O على الحديث عن وقت المعالجة والذاكرة.يمكنك استخدامه لمناقشة الخطوط المقاربة لأي شيء يكون فيه القياس ذا معنى، مثل:

• عدد المصافحات المحتملة بين N الناس في الحفلة (Ɵ(N²), ، خاصة N(N-1)/2, ولكن المهم أن يكون "مثل" N²)
• العدد المتوقع الاحتمالي من الأشخاص الذين رأوا بعض التسويق الفيروسي كدالة للوقت
• كيفية قياس زمن استجابة موقع الويب مع عدد وحدات المعالجة في وحدة المعالجة المركزية أو وحدة معالجة الرسومات أو مجموعة الكمبيوتر
• كيف تموت مقاييس خرج الحرارة على وحدة المعالجة المركزية كدالة لعدد الترانزستور والجهد وما إلى ذلك.
• مقدار الوقت الذي تحتاجه الخوارزمية للتشغيل، كدالة لحجم الإدخال
• مقدار المساحة التي تحتاجها الخوارزمية للتشغيل، كدالة لحجم الإدخال

---

مثال

بالنسبة لمثال المصافحة أعلاه، كل شخص في الغرفة يصافح الجميع.في هذا المثال، #handshakes ∈ Ɵ(N²).لماذا؟

احتياطيا قليلا:عدد المصافحات هو بالضبط n-choose-2 أو N*(N-1)/2 (كل شخص من الأشخاص N يصافح الأشخاص الآخرين N-1، ولكن هذا يحسب المصافحة مرتين لذا يقسم على 2):

ومع ذلك، بالنسبة لأعداد كبيرة جدًا من الأشخاص، المصطلح خطي N يتضاءل ويساهم بشكل فعال بـ 0 في النسبة (في الرسم البياني:يصبح جزء المربعات الفارغة على القطر مقارنة بالمربعات الإجمالية أصغر كلما زاد عدد المشاركين).وبالتالي فإن سلوك التحجيم هو order N², أو أن عدد المصافحات "ينمو مثل N²".

#handshakes(N)
────────────── ≈ 1/2
     N²

يبدو الأمر كما لو أن المربعات الفارغة الموجودة على قطر المخطط (علامتي الاختيار N*(N-1)/2) لم تكن موجودة أصلاً (N² علامات الاختيار مقارب).

(استطراد مؤقت من "الإنجليزية البسيطة") إذا أردت إثبات ذلك لنفسك، فيمكنك إجراء بعض الجبر البسيط على النسبة لتقسيمها إلى مصطلحات متعددة (lim يعني "يعتبر في حدود"، فقط تجاهله إذا لم تكن قد رأيته، إنه مجرد تدوين لـ "و N كبير حقًا"):

    N²/2 - N/2         (N²)/2   N/2         1/2
lim ────────── = lim ( ────── - ─── ) = lim ─── = 1/2
N→∞     N²       N→∞     N²     N²      N→∞  1
                               ┕━━━┙
             this is 0 in the limit of N→∞:
             graph it, or plug in a really large number for N

ليرة تركية؛دكتور:عدد المصافحات "يشبه" x² كثيرًا بالنسبة للقيم الكبيرة، لدرجة أنه إذا أردنا كتابة النسبة #handshakes/x²، فالحقيقة أننا لسنا بحاجة إليها بالضبط لن تظهر المصافحات x² حتى في العلامة العشرية لفترة كبيرة بشكل تعسفي.

على سبيل المثاللـ x=1مليون، نسبة #المصافحة/x²:0.499999...

---

بناء الحدس

هذا يتيح لنا الإدلاء بعبارات مثل ...

"بالنسبة إلى حجم الإدخال الكبير بدرجة كافية = N، بغض النظر عن العامل الثابت، إذا كان I مزدوج حجم الإدخال...

• ...أقوم بمضاعفة الوقت الذي تستغرقه خوارزمية O(N) ("الوقت الخطي")."

  ن → (2ن) = 2(ن)

• ...لقد قمت بتربيع (رباعي) الوقت الذي تستغرقه خوارزمية O(N²) ("الوقت التربيعي")." (على سبيل المثالمشكلة 100x كبيرة تستغرق 100²=10000x المدة...ربما غير مستدامة)

  ن² → (2ن)² = 4(ن²)

• ...لقد قمت بمضاعفة التكعيب (الثماني) للوقت الذي تستغرقه خوارزمية O(N³) ("الوقت المكعب")." (على سبيل المثالمشكلة 100x كبيرة تستغرق 100³=1000000x المدة...غير مستدام للغاية)

  ج ن³ → ج(2N)³ = 8(ج ن³)

• ...أقوم بإضافة مبلغ ثابت إلى الوقت الذي تستغرقه خوارزمية O(log(N)) ("الوقت اللوغاريتمي")." (رخيص!)

  سجل ج (ن) → سجل ج(2N) = (سجل ج(2))+(سجل ج (ن)) = (مبلغ ثابت)+(سجل ج (ن))

• ...لا أغير الوقت الذي تستغرقه خوارزمية O(1) ("الوقت الثابت")." (الأرخص!)

  ج*1 → ج*1

• ...أنا "(بشكل أساسي) أضاعف" الوقت الذي تستغرقه خوارزمية O(N log(N))." (شائع إلى حد ما)

  إنه أقل من O(N^1.000001)، والتي قد ترغب في تسميتها خطية بشكل أساسي

• ...أقوم بزيادة الوقت بشكل يبعث على السخرية O(2^ن) ("الوقت الأسي") تستغرقه الخوارزمية." (يمكنك مضاعفة (أو ثلاثة أضعاف، وما إلى ذلك) الوقت فقط عن طريق زيادة المشكلة بوحدة واحدة)

  2^ن → 2^{2 ن} = (4^ن)............ضع طريقا اخر...... 2^ن → 2^ن+1 = 2^ن2¹ = 2 2^ن

[بالنسبة لأولئك الذين يميلون إلى الرياضيات، يمكنك تمرير الماوس فوق المفسدين للحواشي الجانبية البسيطة]

(مع الائتمان ل https://stackoverflow.com/a/487292/711085 )

(من الناحية الفنية قد يكون العامل الثابت مهمًا في بعض الأمثلة الباطنية، لكنني قمت بصياغة الأشياء أعلاه (على سبيل المثال:في السجل (N)) بحيث لا يحدث ذلك)

هذه هي أوامر النمو الأساسية التي يستخدمها المبرمجون وعلماء الكمبيوتر التطبيقيون كنقاط مرجعية.يرون هذه في كل وقت.(لذلك بينما يمكنك التفكير تقنيًا أن "مضاعفة المدخلات تجعل خوارزمية O(√N) أبطأ بمقدار 1.414 مرة،" فمن الأفضل أن تفكر في الأمر على أنه "هذا أسوأ من اللوغاريتمي ولكنه أفضل من الخطي".)

---

العوامل الثابتة

عادة لا نهتم بالعوامل الثابتة المحددة، لأنها لا تؤثر على طريقة نمو الدالة.على سبيل المثال، قد يستغرق الأمر خوارزميتين O(N) الوقت اللازم للاكتمال، ولكن قد يكون أحدهما أبطأ مرتين من الآخر.نحن عادةً لا نهتم كثيرًا إلا إذا كان العامل كبيرًا جدًا، نظرًا لأن التحسين عمل صعب ( متى يكون التحسين سابق لأوانه؟ );كما أن مجرد اختيار خوارزمية ذات علامة كبيرة أفضل غالبًا ما يؤدي إلى تحسين الأداء من خلال أوامر من حيث الحجم.

بعض الخوارزميات المتفوقة بشكل مقارب (على سبيل المثال.عدم المقارنة O(N log(log(N))) فرز) يمكن أن يكون لها عامل ثابت كبير جدًا (على سبيل المثال 100000*N log(log(N))) ، أو النفقات العامة الكبيرة نسبيًا مثل O(N log(log(N))) مع مخفي + 100*N, ، والتي نادرًا ما تستحق استخدامها حتى في "البيانات الضخمة".

---

لماذا O(N) هو في بعض الأحيان أفضل ما يمكنك القيام به، أي.لماذا نحتاج إلى هياكل البيانات

O(N) تعد الخوارزميات إلى حد ما الخوارزميات "الأفضل" إذا كنت بحاجة إلى قراءة جميع بياناتك.ال فعل القراءة جدا مجموعة من البيانات هي O(N) عملية.تحميله في الذاكرة عادة O(N) (أو بشكل أسرع إذا كان لديك دعم للأجهزة، أو لا يوجد وقت على الإطلاق إذا كنت قد قرأت البيانات بالفعل).ولكن إذا لمست أو حتى ينظر في كل جزء من البيانات (أو حتى كل جزء آخر من البيانات)، ستتعامل الخوارزمية الخاصة بك O(N) الوقت لأداء هذا المظهر.بغض النظر عن المدة التي تستغرقها الخوارزمية الفعلية، فستكون على الأقل O(N) لأنه قضى ذلك الوقت في النظر إلى كافة البيانات.

ويمكن قول الشيء نفسه بالنسبة ل فعل الكتابة جدا.جميع الخوارزميات التي تطبع أشياء N ستستغرق N وقتًا، لأن الإخراج طويل على الأقل (على سبيل المثال.طباعة جميع التباديل (طرق إعادة الترتيب) مجموعة أوراق اللعب N هي مضروب: O(N!)).

هذا يحفز استخدام هياكل البيانات:تتطلب بنية البيانات قراءة البيانات مرة واحدة فقط (عادة O(N) الوقت)، بالإضافة إلى قدر تعسفي من المعالجة المسبقة (على سبيل المثال. O(N) أو O(N log(N)) أو O(N²)) والتي نحاول أن نبقيها صغيرة.بعد ذلك، فإن تعديل بنية البيانات (عمليات الإدراج/الحذف/الخ) وإجراء الاستعلامات على البيانات يستغرق وقتًا قليلًا جدًا، مثل O(1) أو O(log(N)).ثم تشرع في إجراء عدد كبير من الاستفسارات!بشكل عام، كلما زاد العمل الذي ترغب في القيام به في وقت مبكر، قل العمل الذي يتعين عليك القيام به لاحقًا.

على سبيل المثال، لنفترض أن لديك إحداثيات خطوط الطول والعرض لملايين أجزاء الطرق، وأردت العثور على جميع تقاطعات الشوارع.

• الطريقة الساذجة:إذا كان لديك إحداثيات تقاطع شارع، وأردت فحص الشوارع المجاورة، فسيتعين عليك المرور عبر ملايين الأجزاء في كل مرة، والتحقق من مجاورة كل منها.
• إذا كنت بحاجة إلى القيام بذلك مرة واحدة فقط، فلن تكون هناك مشكلة في القيام بهذه الطريقة الساذجة O(N) اعمل مرة واحدة فقط، ولكن إذا كنت تريد القيام بذلك عدة مرات (في هذه الحالة، N مرات، مرة واحدة لكل جزء)، علينا أن نفعل O(N²) العمل، أو 1000000²=1000000000000 عملية.ليس جيدًا (يمكن للكمبيوتر الحديث إجراء حوالي مليار عملية في الثانية).
• إذا استخدمنا بنية بسيطة تسمى جدول التجزئة (جدول بحث فوري سريع، يُعرف أيضًا باسم خريطة التجزئة أو القاموس)، فإننا ندفع تكلفة بسيطة عن طريق المعالجة المسبقة لكل شيء في O(N) وقت.بعد ذلك، يستغرق الأمر وقتًا ثابتًا فقط في المتوسط ​​للبحث عن شيء ما باستخدام مفتاحه (في هذه الحالة، مفتاحنا هو إحداثيات خطوط الطول والعرض، مقربة إلى شبكة؛نحن نبحث في مساحات الشبكة المجاورة التي يوجد منها 9 فقط، وهو ثابت).
• لقد تحولت مهمتنا إلى أمر مستحيل O(N²) إلى يمكن التحكم فيها O(N), ، وكل ما كان علينا فعله هو دفع تكلفة بسيطة لإنشاء جدول التجزئة.
• تشبيه:القياس في هذه الحالة بالذات هو أحجية الصور المقطوعة:لقد أنشأنا بنية بيانات تستغل بعض خصائص البيانات.إذا كانت أجزاء الطريق لدينا تشبه قطع الألغاز، فإننا نقوم بتجميعها حسب مطابقة اللون والنمط.ثم نستغل هذا لتجنب القيام بعمل إضافي لاحقًا (مقارنة قطع اللغز ذات الألوان المتشابهة مع بعضها البعض، وليس مع كل قطعة لغز أخرى).

العظة من القصة:تتيح لنا بنية البيانات تسريع العمليات.حتى هياكل البيانات الأكثر تقدمًا يمكن أن تتيح لك دمج العمليات أو تأخيرها أو حتى تجاهلها بطرق ذكية بشكل لا يصدق.قد يكون للمشاكل المختلفة أوجه تشابه مختلفة، ولكنها جميعًا تتضمن تنظيم البيانات بطريقة تستغل بعض الهياكل التي نهتم بها، أو التي فرضناها عليها بشكل مصطنع من أجل مسك الدفاتر.نحن نعمل في وقت مبكر (التخطيط والتنظيم بشكل أساسي)، والآن أصبحت المهام المتكررة أسهل بكثير!

---

مثال عملي:تصور أوامر النمو أثناء البرمجة

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

أساسيات:عندما نتفاعل مع كل عنصر في مجموعة بالحجم A (مثل مصفوفة، أو مجموعة، أو جميع مفاتيح الخريطة، وما إلى ذلك)، أو نقوم بإجراء تكرارات للحلقة، فهذا عامل مضاعف للحجم A.لماذا أقول "عامل مضاعف"؟ - لأن الحلقات والوظائف (بحكم التعريف تقريبًا) لها وقت تشغيل مضاعف:عدد التكرارات، مرات العمل المنجز في الحلقة (أو للوظائف:عدد المرات التي تستدعي فيها الوظيفة، وعدد مرات العمل المنجز في الوظيفة).(هذا ينطبق إذا لم نفعل أي شيء خيالي، مثل تخطي الحلقات أو الخروج من الحلقة مبكرًا، أو تغيير تدفق التحكم في الوظيفة بناءً على الوسائط، وهو أمر شائع جدًا.) فيما يلي بعض الأمثلة على تقنيات التصور، مع الكود الكاذب المصاحب.

(هنا، xتمثل وحدات العمل في الوقت الثابت، وتعليمات المعالج، وأكواد تشغيل المترجم الفوري، وأي شيء آخر)

for(i=0; i<A; i++)        // A * ...
    some O(1) operation     // 1

--> A*1 --> O(A) time

visualization:

|<------ A ------->|
1 2 3 4 5 x x ... x

other languages, multiplying orders of growth:
  javascript, O(A) time and space
    someListOfSizeA.map((x,i) => [x,i])               
  python, O(rows*cols) time and space
    [[r*c for c in range(cols)] for r in range(rows)]

مثال 2:

for every x in listOfSizeA:   // A * (...
    some O(1) operation         // 1
    some O(B) operation         // B
    for every y in listOfSizeC: // C * (...
        some O(1) operation       // 1))

--> O(A*(1 + B + C))
    O(A*(B+C))        (1 is dwarfed)

visualization:

|<------ A ------->|
1 x x x x x x ... x

2 x x x x x x ... x ^
3 x x x x x x ... x |
4 x x x x x x ... x |
5 x x x x x x ... x B  <-- A*B
x x x x x x x ... x |
................... |
x x x x x x x ... x v

x x x x x x x ... x ^
x x x x x x x ... x |
x x x x x x x ... x |
x x x x x x x ... x C  <-- A*C
x x x x x x x ... x |
................... |
x x x x x x x ... x v

مثال 3:

function nSquaredFunction(n) {
    total = 0
    for i in 1..n:        // N *
        for j in 1..n:      // N *
            total += i*k      // 1
    return total
}
// O(n^2)

function nCubedFunction(a) {
    for i in 1..n:                // A *
        print(nSquaredFunction(a))  // A^2
}
// O(a^3)

إذا قمنا بشيء معقد بعض الشيء، فقد تظل قادرًا على تخيل ما يحدث بصريًا:

for x in range(A):
    for y in range(1..x):
        simpleOperation(x*y)

x x x x x x x x x x |
x x x x x x x x x   |
x x x x x x x x     |
x x x x x x x       |
x x x x x x         |
x x x x x           |
x x x x             |
x x x               |
x x                 |
x___________________|

هنا، أصغر مخطط يمكن التعرف عليه يمكنك رسمه هو ما يهم؛المثلث هو شكل ثنائي الأبعاد (0.5 A^2)، تمامًا مثل المربع وهو شكل ثنائي الأبعاد (A^2)؛فالعامل الثابت اثنين هنا يبقى في النسبة التقاربية بين الاثنين، لكننا نتجاهله مثل كل العوامل...(هناك بعض الفروق الدقيقة المؤسفة في هذه التقنية، ولن أخوض فيها هنا؛يمكن أن يضللك.)

بالطبع هذا لا يعني أن الحلقات والوظائف سيئة؛بل على العكس من ذلك، فهي اللبنات الأساسية للغات البرمجة الحديثة، ونحن نحبها.ومع ذلك، يمكننا أن نرى أن الطريقة التي ننسج بها الحلقات والوظائف والشروط مع بياناتنا (تدفق التحكم، وما إلى ذلك) تحاكي استخدام الوقت والمساحة لبرنامجنا!إذا أصبح استخدام الوقت والمكان مشكلة، فهذا عندما نلجأ إلى الذكاء، ونجد خوارزمية سهلة أو بنية بيانات لم نأخذها في الاعتبار، لتقليل ترتيب النمو بطريقة أو بأخرى.ومع ذلك، فإن تقنيات التصور هذه (على الرغم من أنها لا تعمل دائمًا) يمكن أن تمنحك تخمينًا ساذجًا في أسوأ وقت للتشغيل.

وهنا شيء آخر يمكننا التعرف عليه بصريا:

<----------------------------- N ----------------------------->
x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x
x x x x x x x x x x x x x x x x
x x x x x x x x
x x x x
x x
x

يمكننا فقط إعادة ترتيب هذا ورؤيته O(N):

<----------------------------- N ----------------------------->
x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x
x x x x x x x x x x x x x x x x|x x x x x x x x|x x x x|x x|x

أو ربما تقوم بتسجيل (N) تمرير البيانات، لإجمالي الوقت O(N*log(N)):

   <----------------------------- N ----------------------------->
 ^  x x x x x x x x x x x x x x x x|x x x x x x x x x x x x x x x x
 |  x x x x x x x x|x x x x x x x x|x x x x x x x x|x x x x x x x x
lgN x x x x|x x x x|x x x x|x x x x|x x x x|x x x x|x x x x|x x x x
 |  x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x
 v  x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x

لا علاقة لها ولكن تجدر الإشارة مرة أخرى:إذا قمنا بإجراء التجزئة (على سبيل المثال.قاموس/بحث قابل للتجزئة)، وهو عامل O(1).هذا سريع جدًا.

[myDictionary.has(x) for x in listOfSizeA]
 \----- O(1) ------/    

--> A*1 --> O(A)

إذا قمنا بشيء معقد جدًا، مثل دالة متكررة أو خوارزمية فرق تسد، يمكنك استخدام ال نظرية الماجستير (تنجح عادةً)، أو في الحالات السخيفة نظرية أكرا-بازي (تنجح دائمًا تقريبًا) يمكنك البحث عن وقت تشغيل الخوارزمية الخاصة بك على ويكيبيديا.

لكن المبرمجين لا يفكرون بهذه الطريقة لأنه في نهاية المطاف، يصبح حدس الخوارزمية مجرد طبيعة ثانية.ستبدأ في برمجة شيء غير فعال، وستفكر على الفور "هل أفعل شيئًا ما؟ غير فعالة بشكل صارخ؟".إذا كانت الإجابة "نعم" وتتوقع أن الأمر مهم بالفعل، فيمكنك الرجوع خطوة إلى الوراء والتفكير في حيل مختلفة لجعل الأمور تسير بشكل أسرع (الإجابة دائمًا تقريبًا هي "استخدام جدول التجزئة"، ونادرًا ما "استخدام شجرة"، ونادرًا ما يكون الأمر أكثر تعقيدًا).

---

التعقيد المطفأ ومتوسط ​​الحالة

هناك أيضًا مفهوم "المطفأ" و/أو "الحالة المتوسطة" (لاحظ أنهما مختلفان).

متوسط ​​الحالة:هذا ليس أكثر من استخدام تدوين كبير O للقيمة المتوقعة للدالة، بدلاً من الوظيفة نفسها.في الحالة المعتادة التي تعتبر فيها جميع المدخلات متساوية في احتمالية حدوثها، يكون متوسط ​​الحالة هو مجرد متوسط ​​وقت التشغيل.على سبيل المثال مع الفرز السريع، على الرغم من أن أسوأ الحالات هي O(N^2) بالنسبة لبعض المدخلات السيئة حقًا، تكون الحالة المتوسطة هي المعتادة O(N log(N)) (المدخلات السيئة حقًا صغيرة جدًا من حيث العدد، وهي قليلة جدًا لدرجة أننا لا نلاحظها في الحالة المتوسطة).

المطفأة في أسوأ الأحوال:قد تحتوي بعض هياكل البيانات على تعقيد كبير في أسوأ الحالات، ولكن تأكد من أنه إذا قمت بالعديد من هذه العمليات، فإن متوسط ​​مقدار العمل الذي تقوم به سيكون أفضل من أسوأ الحالات.على سبيل المثال، قد يكون لديك بنية بيانات عادة ما تكون ثابتة O(1) وقت.ومع ذلك، في بعض الأحيان سوف "يصاب بالفواق" ويستغرق O(N) حان الوقت لإجراء عملية عشوائية واحدة، لأنها ربما تحتاج إلى القيام ببعض مسك الدفاتر أو جمع البيانات المهملة أو شيء من هذا القبيل...ولكنه يعدك بأنه إذا حدث خلل، فلن يحدث خلل مرة أخرى لمدة N عمليات أخرى.التكلفة الأسوأ لا تزال قائمة O(N) لكل عملية، ولكن التكلفة المطفأة على مدى العديد من أشواط يكون O(N)/N = O(1) لكل عملية.نظرًا لأن العمليات الكبيرة نادرة بما فيه الكفاية، يمكن اعتبار الكم الهائل من العمل العرضي مندمجًا مع بقية العمل كعامل ثابت.نقول أن العمل "يتم إطفاؤه" على عدد كبير بما فيه الكفاية من المكالمات بحيث يختفي بشكل مقارب.

تشبيه التحليل المطفأ:

أنت تقود سيارة.من حين لآخر ، تحتاج إلى قضاء 10 دقائق في الذهاب إلى محطة الوقود ثم قضاء 1 دقيقة إعادة تعبئة الخزان بالغاز.إذا كنت تفعل هذا في كل مرة تذهب فيها إلى أي مكان بسيارتك (أنفق 10 دقائق بالسيارة إلى محطة الوقود ، وقضاء بضع ثوان في ملء جزء من جالون) ، سيكون غير فعال للغاية.ولكن إذا ملأت حتى الخزان مرة كل بضعة أيام ، تقضي 11 دقيقة في القيادة إلى يتم "إطفاء" محطة الوقود على عدد كبير بما فيه الكفاية من الرحلات ، أنه يمكنك تجاهلها والتظاهر بأن جميع رحلاتك ربما كانت أطول بنسبة 5٪.

مقارنة بين الحالة المتوسطة والحالة الأسوأ المطفأة:

• متوسط ​​الحالة:نحن نضع بعض الافتراضات حول مدخلاتنا؛أي.إذا كانت مدخلاتنا لها احتمالات مختلفة، فإن مخرجاتنا/أوقات التشغيل لدينا سيكون لها احتمالات مختلفة (والتي نأخذ متوسطها).عادة نفترض أن جميع مدخلاتنا متساوية في الاحتمال (احتمال موحد)، ولكن إذا كانت مدخلات العالم الحقيقي لا تتناسب مع افتراضاتنا حول "متوسط ​​المدخلات"، فقد تكون حسابات متوسط ​​المخرجات/وقت التشغيل بلا معنى.إذا كنت تتوقع مدخلات عشوائية بشكل موحد، فمن المفيد التفكير في هذا الأمر!
• إطفاء أسوأ الحالات:إذا كنت تستخدم بنية بيانات أسوأ الحالات المطفأة، فسيتم ضمان أن يكون الأداء ضمن أسوأ الحالات المطفأة...في النهاية (حتى لو تم اختيار المدخلات بواسطة شيطان شرير يعرف كل شيء ويحاول إفسادك).عادةً ما نستخدم هذا لتحليل الخوارزميات التي قد تكون "متقلبة" للغاية في الأداء مع وجود عوائق كبيرة غير متوقعة، ولكن مع مرور الوقت يكون أداؤها مماثلاً للخوارزميات الأخرى.(ومع ذلك، ما لم يكن لدى بنية البيانات الخاصة بك حدود عليا لكثير من العمل المتميز الذي تكون على استعداد للمماطلة فيه، فقد يجبرك مهاجم شرير على اللحاق بأقصى قدر من العمل المماطلة مرة واحدة.

بالرغم من ذلك، إذا كنت كذلك قلق إلى حد معقول فيما يتعلق بالمهاجم، هناك العديد من نواقل الهجوم الخوارزمية الأخرى التي يجب القلق بشأنها إلى جانب الاستهلاك والحالة المتوسطة.)

يعد كل من الحالة المتوسطة والإطفاء أدوات مفيدة بشكل لا يصدق للتفكير والتصميم مع وضع القياس في الاعتبار.

(يرى الفرق بين متوسط ​​الحالة والتحليل المطفأ إذا كنت مهتمًا بهذا الموضوع الفرعي.)

---

متعدد الأبعاد كبير-O

في معظم الأحيان، لا يدرك الناس أن هناك أكثر من متغير واحد في العمل.على سبيل المثال، في خوارزمية البحث عن السلسلة، قد تستغرق الخوارزمية بعض الوقت O([length of text] + [length of query]), ، أي.إنه خطي في متغيرين مثل O(N+M).قد تكون خوارزميات أخرى أكثر سذاجة O([length of text]*[length of query]) أو O(N*M).يعد تجاهل المتغيرات المتعددة أحد الأخطاء الأكثر شيوعًا التي أراها في تحليل الخوارزمية، ويمكن أن يعيقك عند تصميم الخوارزمية.

---

القصة الكاملة

ضع في اعتبارك أن Big-O ليست القصة بأكملها.يمكنك تسريع بعض الخوارزميات بشكل كبير عن طريق استخدام التخزين المؤقت، أو جعلها غافلة عن ذاكرة التخزين المؤقت، أو تجنب الاختناقات من خلال العمل مع ذاكرة الوصول العشوائي (RAM) بدلاً من القرص، أو استخدام الموازاة، أو القيام بالعمل في وقت مبكر - غالبًا ما يتم استخدام هذه التقنيات مستقل من تدوين ترتيب النمو "big-O"، على الرغم من أنك ستشاهد غالبًا عدد النوى في تدوين big-O للخوارزميات المتوازية.

ضع في اعتبارك أيضًا أنه نظرًا للقيود الخفية لبرنامجك، فقد لا تهتم حقًا بالسلوك المقارب.من الممكن أنك تعمل مع عدد محدود من القيم، على سبيل المثال:

• إذا كنت تقوم بفرز شيء ما مثل 5 عناصر، فلن ترغب في استخدام الخيار السريع O(N log(N)) فرز سريع؛تريد استخدام فرز الإدراج، والذي يحدث بشكل جيد على المدخلات الصغيرة.غالبًا ما تظهر هذه المواقف في خوارزميات فرق تسد، حيث تقوم بتقسيم المشكلة إلى مسائل فرعية أصغر فأصغر، مثل الفرز العودي، أو تحويلات فورييه السريعة، أو ضرب المصفوفات.
• إذا كانت بعض القيم محددة بشكل فعال بسبب بعض الحقائق المخفية (على سبيل المثال.إن متوسط ​​اسم الإنسان محدد بهدوء ربما بـ 40 حرفًا، وعمر الإنسان محدد بهدوء بحوالي 150 حرفًا).يمكنك أيضًا فرض حدود على مدخلاتك لجعل الشروط ثابتة بشكل فعال.

من الناحية العملية، حتى بين الخوارزميات التي لها نفس الأداء المقارب أو ما شابه ذلك، فإن جدارتها النسبية قد تكون مدفوعة في الواقع بأشياء أخرى، مثل:عوامل الأداء الأخرى (الفرز السريع والفرز المدمج كلاهما O(N log(N)), ، لكن الفرز السريع يستفيد من ذاكرة التخزين المؤقت لوحدة المعالجة المركزية)؛اعتبارات عدم الأداء، مثل سهولة التنفيذ؛ما إذا كانت المكتبة متاحة، ومدى سمعة المكتبة وصيانتها.

سيتم أيضًا تشغيل البرامج بشكل أبطأ على جهاز كمبيوتر بسرعة 500 ميجا هرتز مقابل كمبيوتر بسرعة 2 جيجا هرتز.نحن لا نعتبر هذا حقًا جزءًا من حدود الموارد، لأننا نفكر في التوسع من حيث موارد الآلة (على سبيل المثال.لكل دورة ساعة)، وليس لكل ثانية حقيقية.ومع ذلك، هناك أشياء مماثلة يمكن أن تؤثر "سرًا" على الأداء، مثل ما إذا كنت تعمل تحت المحاكاة، أو ما إذا كان المترجم قد قام بتحسين التعليمات البرمجية أم لا.وقد يؤدي ذلك إلى جعل بعض العمليات الأساسية تستغرق وقتًا أطول (حتى بالنسبة لبعضها البعض)، أو حتى تسريع أو إبطاء بعض العمليات بشكل غير مقارب (حتى بالنسبة لبعضها البعض).قد يكون التأثير صغيرًا أو كبيرًا بين التنفيذ و/أو البيئة المختلفة.هل تقوم بتبديل اللغات أو الأجهزة للحصول على هذا العمل الإضافي القليل؟يعتمد ذلك على مائة سبب آخر (الضرورة، المهارات، زملاء العمل، إنتاجية المبرمج، القيمة المالية لوقتك، المعرفة، الحلول البديلة، لماذا لا التجميع أو وحدة معالجة الرسومات، وما إلى ذلك)، والتي قد تكون أكثر أهمية من الأداء.

القضايا المذكورة أعلاه، مثل لغة البرمجة، لا تعتبر أبدًا جزءًا من العامل الثابت (ولا ينبغي أن تكون كذلك)؛ومع ذلك ينبغي للمرء أن يكون على علم بها، لأن أحيانا (وإن كان نادرًا) قد تؤثر على الأشياء.على سبيل المثال في cpython، يعد تنفيذ قائمة انتظار الأولوية الأصلية غير مقارب (O(log(N)) بدلا من O(1) لاختيارك للإدراج أو البحث عن دقيقة)؛هل تستخدم تنفيذ آخر؟ربما لا، نظرًا لأن تنفيذ لغة C ربما يكون أسرع، ومن المحتمل أن تكون هناك مشكلات أخرى مماثلة في مكان آخر.هناك مقايضات.في بعض الأحيان يهمون وأحيانا لا يهمون.

---

(يحرر:ينتهي شرح "الإنجليزية البسيطة" هنا.)

إضافات الرياضيات

من أجل الاكتمال، التعريف الدقيق لتدوين Big-O هو كما يلي: f(x) ∈ O(g(x)) يعني أن "f محدد بشكل غير مقارب بـ const*g":بتجاهل كل شيء أقل من قيمة محددة لـ x، يوجد ثابت من هذا القبيل |f(x)| ≤ const * |g(x)|.(الرموز الأخرى هي كما يلي:تماما مثل O يعني ≥، Ω يعني ≥.هناك متغيرات صغيرة: o يعني <، و ω يعني > .) f(x) ∈ Ɵ(g(x)) يعني على حد سواء f(x) ∈ O(g(x)) و f(x) ∈ Ω(g(x)) (يحدها العلوي والسفلي g):توجد بعض الثوابت بحيث يكون f دائمًا في "النطاق" بينهما const1*g(x) و const2*g(x).إنه أقوى عبارة مقاربة يمكنك الإدلاء بها ويعادلها تقريبًا ==.(عذرًا، اخترت تأخير ذكر رموز القيمة المطلقة حتى الآن، من أجل الوضوح؛خاصةً لأنني لم أر قط قيمًا سلبية تظهر في سياق علوم الكمبيوتر.)

سوف يستخدم الناس في كثير من الأحيان = O(...), ، والذي ربما يكون تدوين "comp-sci" الأكثر صحة، وهو مشروع تمامًا للاستخدام؛تتم قراءة "f = O(...)" "f هو الترتيب .../ f يحدها xxx بـ ..." ويعتقد أن "f هو بعض التعبيرات التي تكون تقارباتها ...".لقد تعلمت استخدام أكثر صرامة ∈ O(...). ∈ يعني "عنصر من" (لا يزال يُقرأ كما كان من قبل). O(N²) هو في الواقع فئة التكافؤ, أي أنها مجموعة من الأشياء التي نعتبرها متماثلة.في هذه الحالة بالذات، O(N²) يحتوي على عناصر مثل {2 N², 3 N², 1/2 N², 2 N² + log(N), - N² + N^1.9, ، ...} وهو كبير بلا حدود، لكنه لا يزال مجموعة.ال = قد يكون التدوين هو الأكثر شيوعًا، ويتم استخدامه حتى في الأبحاث من قبل علماء الكمبيوتر المشهورين عالميًا.بالإضافة إلى ذلك، غالبًا ما يحدث ذلك في بيئة غير رسمية، كما يقول الناس O(...) عندما يقصدون Ɵ(...);هذا صحيح من الناحية الفنية منذ مجموعة الأشياء Ɵ(exactlyThis) هي مجموعة فرعية من O(noGreaterThanThis)...ومن الأسهل الكتابة.؛-)

Answer 4

يحرر:ملاحظة سريعة، يكاد يكون من المؤكد أن هذا مربكًا تدوين O الكبير (وهو الحد الأعلى) مع تدوين ثيتا (وهو الحد العلوي والسفلي).في تجربتي، يعد هذا أمرًا نموذجيًا للمناقشات في البيئات غير الأكاديمية.نعتذر عن التسبب في أي أرتباك.

في جملة واحدة:مع زيادة حجم عملك، ما الوقت الذي يستغرقه إكماله؟

من الواضح أن هذا يستخدم فقط "الحجم" كمدخل و"الوقت المستغرق" كمخرج - تنطبق نفس الفكرة إذا كنت تريد التحدث عن استخدام الذاكرة وما إلى ذلك.

إليك مثال حيث لدينا قمصان N ونريد تجفيفها.حسنًا يفترض إنه سريع بشكل لا يصدق لوضعهم في وضع التجفيف (أي.التفاعل البشري لا يكاد يذكر).وهذا ليس هو الحال في الحياة الحقيقية بالطبع..

• استخدام حبل الغسيل بالخارج:بافتراض أن لديك ساحة خلفية كبيرة بشكل لا نهائي، فإن الغسيل يجف في زمن O(1).مهما كانت الكمية المتوفرة لديك، فإنها ستحصل على نفس الشمس والهواء النقي، وبالتالي لا يؤثر الحجم على وقت التجفيف.

• استخدام المجفف:تضع 10 قمصان في كل حمولة، ثم يتم الانتهاء منها بعد ساعة.(تجاهل الأرقام الفعلية هنا - فهي غير ذات صلة). لذا فإن تجفيف 50 قميصًا يستغرق وقتًا عن 5 مرات أطول من تجفيف 10 قمصان.

• وضع كل شيء في خزانة تهوية:إذا وضعنا كل شيء في كومة واحدة كبيرة وتركنا الدفء العام يقوم بذلك، فسوف يستغرق الأمر وقتًا طويلاً حتى تجف القمصان الوسطى.لا أود أن أخمن التفاصيل، ولكني أظن أن هذا على الأقل O(N^2) - فكلما قمت بزيادة حمل الغسيل، زاد وقت التجفيف بشكل أسرع.

أحد الجوانب المهمة لتدوين "big O" هو أنه لا قل أي خوارزمية ستكون أسرع بالنسبة لحجم معين.خذ جدول تجزئة (مفتاح سلسلة، قيمة عددية) مقابل مجموعة من الأزواج (سلسلة، عدد صحيح).هل من الأسرع العثور على مفتاح في جدول التجزئة أو عنصر في المصفوفة بناءً على سلسلة؟(أي.بالنسبة للمصفوفة، "ابحث عن العنصر الأول حيث يتطابق جزء السلسلة مع المفتاح المحدد.") يتم إطفاء جداول التجزئة بشكل عام (~= "في المتوسط") O(1) - بمجرد إعدادها، يجب أن يستغرق الأمر نفس الوقت تقريبًا حان الوقت للعثور على إدخال في جدول إدخال 100 كما هو الحال في جدول إدخال 1,000,000.البحث عن عنصر في مصفوفة (استنادا إلى المحتوى بدلا من الفهرس) هو أمر خطي، أي.O(N) — في المتوسط، سيتعين عليك إلقاء نظرة على نصف الإدخالات.

هل هذا يجعل جدول التجزئة أسرع من مصفوفة عمليات البحث؟ليس بالضرورة.إذا كان لديك مجموعة صغيرة جدًا من الإدخالات، فقد تكون المصفوفة أسرع - وقد تتمكن من التحقق من جميع السلاسل في الوقت الذي يستغرقه حساب رمز التجزئة الخاص بالمصفوفة التي تبحث عنها فقط.ومع ذلك، مع نمو مجموعة البيانات بشكل أكبر، سيتفوق جدول التجزئة في النهاية على المصفوفة.

Answer 5

يصف Big O الحد الأعلى لسلوك نمو الوظيفة ، على سبيل المثال وقت تشغيل البرنامج ، عندما تصبح المدخلات كبيرة.

أمثلة:

• س (ن): إذا كنت مضاعفة حجم الإدخال يتضاعف وقت التشغيل

• على²): إذا كان حجم الإدخال يضاعف من أرباع وقت التشغيل

• o (log n): إذا كان حجم الإدخال يضاعف وقت التشغيل

• س (2^ن): إذا زاد حجم الإدخال بوقت واحد ، يتضاعف وقت التشغيل

حجم الإدخال هو عادة المساحة في البتات اللازمة لتمثيل المدخلات.

Answer 6

يتم استخدام المبرمجين بشكل شائع بشكل شائع من قبل المبرمجين كمقياس تقريبي لمدى استقبال الحساب (الخوارزمية) لإكماله كدالة لحجم مجموعة الإدخال.

يعد Big O مفيدًا لمقارنة مدى توسيع نطاق خوارزميتين مع زيادة عدد المدخلات.

أكثر دقة تدوين كبير يستخدم للتعبير عن السلوك المقارب للوظيفة. هذا يعني كيف تتصرف الوظيفة مع اقترابها من اللانهاية.

في كثير من الحالات ، ستسقط "O" للخوارزمية في إحدى الحالات التالية:

• س (1) - الوقت لإكمال هو نفسه بغض النظر عن حجم مجموعة الإدخال. مثال على ذلك هو الوصول إلى عنصر صفيف حسب الفهرس.
• س (سجل ن) - حان الوقت لإكمال الزيادات تقريبًا بما يتماشى تقريبًا مع log2 (n). على سبيل المثال ، يستغرق 1024 عناصر ما يصل إلى 32 عنصرًا تقريبًا ، لأن log2 (1024) = 10 و log2 (32) = 5. مثال على ذلك شجرة البحث الثنائية (BST).
• على) - حان الوقت لإكمال ذلك بشكل خطي مع حجم مجموعة الإدخال. بمعنى آخر ، إذا كنت تضاعف عدد العناصر الموجودة في مجموعة الإدخال ، فإن الخوارزمية تستغرق مرتين تقريبًا. مثال على ذلك هو حساب عدد العناصر في قائمة مرتبطة.
• o (n log n) - حان الوقت لإكمال الزيادات من خلال عدد العناصر أوقات نتيجة log2 (n). مثال على ذلك نوع كومة و نوع سريع.
• س (ن^2) - الوقت لإكمال يساوي تقريبًا مربع عدد العناصر. مثال على ذلك فقاعة الفرز.
• على!) - الوقت لإكمال هو عامل مجموعة الإدخال. مثال على ذلك هو حل مشكلة البائع المتجول في القوة الغاشمة.

يتجاهل Big o العوامل التي لا تسهم بطريقة ذات مغزى في منحنى النمو للوظيفة مع زيادة حجم الإدخال نحو اللانهاية. هذا يعني أنه يتم ببساطة تجاهل الثوابت التي تمت إضافتها إلى الوظيفة أو مضروبتها.

Answer 7

Big O هي مجرد وسيلة "للتعبير" عن نفسك بطريقة مشتركة ، "كم من الوقت / المساحة يستغرق تشغيل الكود الخاص بي؟".

قد ترى في كثير من الأحيان o (n) ، o (n²) ، o (nlogn) وهكذا دواليك ، كل هذه هي طرق للعرض ؛ كيف تتغير الخوارزمية؟

س (ن) تعني Big o هي n ، والآن قد تفكر ، "ما هو n!؟" حسنا "N" هو مقدار العناصر. التصوير تريد البحث عن عنصر في صفيف. يجب أن تنظر إلى كل عنصر وكما "هل أنت العنصر/العنصر الصحيح؟" في أسوأ الحالات ، يكون العنصر في الفهرس الأخير ، مما يعني أن الأمر استغرق وقتًا طويلاً مثل وجود عناصر في القائمة ، حتى تكون عامًا ، نقول "أوه ، n هو قدر عادل من القيم!" .

إذن قد تفهم ما "n²"يعني ، ولكن لكي تكون أكثر تحديداً ، تلعب مع الفكر لديك بسيطة ، وأبسط خوارزميات الفرز ؛ Bubblesort. هذه الخوارزمية تحتاج إلى النظر من خلال القائمة بأكملها ، لكل عنصر.

قائمتي

1. 1
2. 6
3. 3

سيكون التدفق هنا:

• قارن 1 و 6 ، ما هو الأكبر؟ موافق 6 في الوضع الصحيح ، والمضي قدمًا!
• قارن 6 و 3 ، أوه ، 3 أقل! دعنا ننقل ذلك ، حسنًا ، تم تغيير القائمة ، نحتاج إلى البدء من البداية الآن!

هذا يا ن² لأنك تحتاج إلى إلقاء نظرة على جميع العناصر في القائمة هناك عناصر "N". لكل عنصر ، تنظر إلى جميع العناصر مرة أخرى ، للمقارنة ، هذا هو أيضًا "n" ، لذلك لكل عنصر ، تبدو "n" تعني n*n = n²

آمل أن يكون هذا بسيطًا كما تريد.

لكن تذكر أن Big O هي مجرد وسيلة لإنهاء نفسك بطريقة الزمان والمكان.

Answer 8

يصف Big O الطبيعة الأساسية للتوسع للخوارزمية.

هناك الكثير من المعلومات التي لا تخبرك بها Big O عن خوارزمية معينة. إنه يقطع العظم ويعطي فقط معلومات حول طبيعة تحجيم الخوارزمية ، وتحديداً كيف يستخدم استخدام الموارد (فكر في الوقت أو الذاكرة) في موازين الخوارزمية استجابةً لـ "حجم الإدخال".

النظر في الفرق بين محرك البخار وصاروخ. إنها ليست مجرد أنواع مختلفة من نفس الشيء (على سبيل المثال ، محرك Prius مقابل محرك Lamborghini) ولكنها أنواع مختلفة بشكل كبير من أنظمة الدفع ، في صميمها. قد يكون محرك البخار أسرع من صاروخ لعبة ، ولكن لن يتمكن أي محرك مكبس البخار من تحقيق سرعات مركبة الإطلاق المدارية. وذلك لأن هذه الأنظمة لها خصائص تحجيم مختلفة فيما يتعلق بعلاقة الوقود المطلوبة ("استخدام الموارد") للوصول إلى سرعة معينة ("حجم الإدخال").

لماذا هذا بغاية الأهمية؟ لأن البرمجيات يتعامل مع المشكلات التي قد تختلف في الحجم حسب العوامل التي تصل إلى تريليون. النظر في ذلك لحظة. النسبة بين السرعة اللازمة للسفر إلى القمر وسرعة المشي البشرية أقل من 10000: 1 ، وهذا صغير للغاية مقارنة بالنطاق في برنامج أحجام الإدخال قد يواجهه. ونظرًا لأن البرامج قد تواجه نطاقًا فلكيًا في أحجام المدخلات ، فهناك احتمال تعقيد كبير في الخوارزمية ، إنها طبيعة تحجيم أساسية ، لتفاصيل أي تفاصيل تنفيذ.

النظر في مثال الفرز الكنسي. الفقاعة Sort هي (ن²) بينما دمج sort هو o (n log n). دعنا نقول أن لديك اثنين من تطبيقات الفرز ، التطبيق A الذي يستخدم الفقاعة والتطبيق B الذي يستخدم دمج sort ، ودعنا نقول أنه بالنسبة لأحجام الإدخال من حوالي 30 عنصر التطبيق A هو 1000x أسرع من التطبيق B في الفرز. إذا لم تضطر أبدًا إلى فرز أكثر من 30 عنصرًا ، فمن الواضح أنه يجب أن تفضل التطبيق A ، لأنه أسرع بكثير في أحجام الإدخال هذه. ومع ذلك ، إذا وجدت أنه قد تضطر إلى فرز عشرة ملايين عنصر ، فإن ما تتوقعه هو أن التطبيق B ينتهي فعليًا بآلاف المرات بشكل أسرع من التطبيق A في هذه الحالة ، ويرجع ذلك بالكامل إلى الطريقة التي يتم بها كل خوارزمية.

Answer 9

إليكم ما يميل إلى استخدام اللغة الإنجليزية البسيطة عند شرح الأصناف المشتركة لـ Big-O

في جميع الحالات ، تفضل الخوارزميات أعلى في القائمة لتلك المنخفضة في القائمة. ومع ذلك ، فإن تكلفة الانتقال إلى فئة تعقيد أكثر تكلفة تختلف اختلافا كبيرا.

س (1):

لا نمو. بغض النظر عن حجم المشكلة ، يمكنك حلها في نفس الوقت. هذا مشابه إلى حد ما للبث حيث يتطلب نفس كمية الطاقة للبث على مسافة معينة ، بغض النظر عن عدد الأشخاص الذين يكمنون في نطاق البث.

س (سجل ن):

هذا التعقيد هو نفسه س (1) إلا أن الأمر أسوأ قليلاً. لجميع الأغراض العملية ، يمكنك النظر في هذا بمثابة تحجيم ثابت كبير للغاية. الفرق في العمل بين معالجة 1 ألف و 1 مليار عنصر هو مجرد عامل ستة.

س (ن):

تكلفة حل المشكلة تتناسب مع حجم المشكلة. إذا كانت مشكلتك تتضاعف في الحجم ، فإن تكلفة الحل تتضاعف. نظرًا لأنه يجب مسح معظم المشكلات في الكمبيوتر بطريقة ما ، حيث يتم إدخال البيانات أو قرص القرص أو حركة مرور الشبكة ، فهذا عام عامل تحجيم بأسعار معقولة.

س (ن سجل ن):

هذا التعقيد يشبه إلى حد كبير س (ن). لجميع الأغراض العملية ، الاثنين معادلة. هذا المستوى من التعقيد لا يزال يعتبر قابلاً للتطوير بشكل عام. من خلال تغيير الافتراضات بعض س (ن سجل ن) يمكن تحويل الخوارزميات إلى س (ن) الخوارزميات. على سبيل المثال ، يقلل حجم المفاتيح من الفرز من س (ن سجل ن) إلى س (ن).

س (ن²):

ينمو كمربع ، حيث ن هو طول جانب مربع. هذا هو نفس معدل النمو مثل "تأثير الشبكة" ، حيث قد يعرف الجميع في الشبكة أي شخص آخر في الشبكة. النمو مكلف. لا يمكن أن تستخدم معظم الحلول القابلة للتطوير خوارزميات مع هذا المستوى من التعقيد دون القيام بجمباز كبير. ينطبق هذا بشكل عام على جميع التعقيدات الحية الأخرى - س (ن^ك) - كذلك.

س (2^ن):

لا يتوسع. ليس لديك أمل في حل أي مشكلة غير محددة. مفيد لمعرفة ما يجب تجنب س (ن^ك).

Answer 10

Big O هو مقياس لمقدار الوقت/المساحة التي تستخدمها الخوارزمية بالنسبة لحجم مدخلاتها.

إذا كانت الخوارزمية O (N) ، فستزيد الوقت/المساحة بنفس معدل مدخلاتها.

إذا كانت الخوارزمية O (ن²) ثم زيادة الوقت/المساحة بمعدل مدخلاتها مربعة.

وهلم جرا.

Answer 11

من الصعب للغاية قياس سرعة البرامج ، وعندما نحاول ، يمكن أن تكون الإجابات معقدة للغاية ومليئة باستثناءات وحالات خاصة. هذه مشكلة كبيرة ، لأن كل هذه الاستثناءات والحالات الخاصة تشتت انتباهها وغير مفيدة عندما نريد مقارنة برنامجين مختلفين مع بعضهما البعض لمعرفة ما هو "الأسرع".

نتيجة لكل هذا التعقيد غير المفيد ، يحاول الناس وصف سرعة البرامج باستخدام أصغر وأقل تعقيد تعبيرات (رياضية) ممكنة. هذه التعبيرات هي تقريبية خام للغاية: على الرغم من أنها ، مع قليل من الحظ ، سوف يلتقطون "جوهر" ما إذا كان جزء من البرنامج سريعًا أم بطيئًا.

نظرًا لأنها تقريبية ، فإننا نستخدم الحرف "O" (Big OH) في التعبير ، كاتفاقية للإشارة إلى القارئ أننا نقوم بإفراط في التبسيط الجسيم. (والتأكد من أن لا أحد يعتقد عن طريق الخطأ أن التعبير دقيق بأي شكل من الأشكال).

إذا قرأت "OH" كمعنى "بترتيب" أو "تقريبًا" ، فلن تخطئ كثيرًا. (أعتقد أن اختيار Big-Oh قد يكون محاولة للفكاهة).

الشيء الوحيد الذي تحاول التعبيرات "Big-OH" هو وصف مقدار إبطاء البرنامج حيث نزيد من كمية البيانات التي يتعين على البرنامج معالجتها. إذا مضاعفة كمية البيانات التي يجب معالجتها ، فهل يحتاج البرنامج إلى ضعف طوله لإنهاء عمله؟ عشر مرات طالما؟ في الممارسة العملية ، هناك عدد محدود للغاية من التعبيرات الكبيرة التي ستواجهها وتحتاج إلى القلق بشأن:

الخير:

• O(1) مستمر: يستغرق البرنامج نفس الوقت لتشغيله بغض النظر عن حجم الإدخال.
• O(log n) لوغاريتمي: يزداد وقت تشغيل البرنامج ببطء فقط ، حتى مع زيادات كبيرة في حجم المدخلات.

السيء:

• O(n) خطي: يزداد وقت تشغيل البرنامج بشكل متناسب مع حجم المدخلات.
• O(n^k) متعدد الحدود: - تنمو وقت المعالجة بشكل أسرع وأسرع - كدالة متعددة الحدود - مع زيادة حجم المدخلات.

... والقبيح:

• O(k^n) متسارع يزداد وقت تشغيل البرنامج بسرعة كبيرة مع الزيادات المعتدلة في حجم المشكلة - من العملي فقط معالجة مجموعات البيانات الصغيرة ذات الخوارزميات الأسية.
• O(n!) العامل سيكون وقت تشغيل البرنامج أطول مما يمكنك الانتظار لأي شيء سوى أصغر مجموعات البيانات وأكثرها تافها.

Answer 12

ما هو التفسير الإنجليزي البسيط لـ Big O؟ مع القليل من التعريف الرسمي قدر الإمكان والرياضيات البسيطة.

شرح إنجليزي عادي لـ بحاجة إلى للتدوين الكبير:

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

شرح إنجليزي عادي لـ ماذا او ما التدوين الكبير هو:

لا يتم تشغيل جميع الخوارزميات في نفس مقدار الوقت ، ويمكن أن تختلف بناءً على عدد العناصر الموجودة في الإدخال ، والتي سنسميها ن. بناءً على ذلك ، نعتبر تحليل الحالة الأسوأ ، أو الحدود العلوية في وقت التشغيل ن تصبح أكبر وأكبر. يجب أن ندرك ماذا ن هو ، لأن العديد من الرموز الكبيرة تشير إلى ذلك.

Answer 13

يمكن أن تكون الإجابة البسيطة المباشرة:

يمثل Big O أسوأ وقت/مساحة ممكنة لهذه الخوارزمية. لن تأخذ الخوارزمية أبدًا مساحة/وقت أعلى من هذا الحد. يمثل Big O تعقيد الوقت/الفضاء في الحالة القصوى.

Answer 14

حسنًا ، 2 سنتي.

Big-O ، هو معدل الزيادة من الموارد التي يستهلكها البرنامج ، حجم المشكلات في الحجم

المورد: يمكن أن يكون وقت CPU الكلي ، يمكن أن يكون الحد الأقصى للمساحة ذاكرة الوصول العشوائي. بشكل افتراضي يشير إلى وقت وحدة المعالجة المركزية.

قل أن المشكلة هي "العثور على المبلغ" ،

int Sum(int*arr,int size){
      int sum=0;
      while(size-->0) 
         sum+=arr[size]; 

      return sum;
}

problem-instance = {5،10،15} ==> حجم المشكلة = 3 ، التكرار في الحلقة = 3

instance المشكلة = {5،10،15،20،25} ==> حجم المشكل

للحصول على مدخلات الحجم "n" ، ينمو البرنامج بسرعة التكرارات "n" في الصفيف. وبالتالي يتم التعبير عن Big-O كـ O (N)

قل أن المشكلة هي "العثور على المزيج" ،

    void Combination(int*arr,int size)
    { int outer=size,inner=size;
      while(outer -->0) {
        inner=size;
        while(inner -->0)
          cout<<arr[outer]<<"-"<<arr[inner]<<endl;
      }
    }

problem-instance = {5،10،15} ==> حجم المشكل

problem-instance = {5،10،15،20،25} ==> حجم المشكل

للحصول على مدخلات الحجم "n" ، ينمو البرنامج بسرعة التكرارات "n*n" في الصفيف. وبالتالي Big-O هو n² أعرب عن O (ن²)

Answer 15

التدوين الكبير O هو وسيلة لوصف الحد الأعلى للخوارزمية من حيث المساحة أو وقت التشغيل. N هو عدد العناصر في المشكلة (أي حجم صفيف ، وعدد العقد في شجرة ، وما إلى ذلك) نحن مهتمون بوصف وقت التشغيل مع زيادة حجم N.

عندما نقول أن بعض الخوارزمية هي O (f (n)) ، نقول أن وقت التشغيل (أو المساحة المطلوبة) من خلال تلك الخوارزمية أقل دائمًا من بعض الأوقات الثابتة F (n).

إن القول بأن البحث الثنائي لديه وقت تشغيل لـ O (logn) هو القول إن هناك بعض C الثابت والتي يمكنك مضاعفة السجل (n) والتي ستكون دائمًا أكبر من وقت تشغيل البحث الثنائي. في هذه الحالة ، سيكون لديك دائمًا بعض العوامل الثابتة لمقارنات السجل (N).

بمعنى آخر ، حيث يكون G (n) وقت تشغيل الخوارزمية الخاصة بك ، نقول أن g (n) = o (f (n)) عندما يكون g (n) <= c*f (n) عند n> k ، حيث C و K هي بعض الثوابت.

Answer 16

"ما هو التفسير الإنجليزي البسيط لـ Big O؟مع القليل من الرسمية تعريف ممكن والرياضيات البسيطة."

يبدو أن مثل هذا السؤال البسيط والقصير يستحق على الأقل إجابة قصيرة بنفس القدر، مثل تلك التي قد يتلقاها الطالب أثناء التدريس.

يخبر تدوين Big O ببساطة مقدار الوقت * الذي يمكن أن تعمل فيه الخوارزمية ، من حيث فقط كمية البيانات المدخلة**.

(* في رائعة، خالية من الوحدة الإحساس بالوقت!)
(** وهو ما يهم، لأن الناس سوف دائماً تريد المزيد, سواء كانوا يعيشون اليوم أو غدا)

حسنًا، ما هو الشيء الرائع في تدوين Big O إذا كان هذا ما يفعله؟

• من الناحية العملية، تحليل Big O هو كذلك مفيدة جدا ومهمة لأن Big O يضع التركيز بشكل مباشر على الخوارزميات ملك التعقيد وبشكل كامل يتجاهل أي شيء يعد مجرد ثابت تناسب، مثل محرك JavaScript، وسرعة وحدة المعالجة المركزية (CPU)، واتصالك بالإنترنت، وكل تلك الأشياء التي سرعان ما تصبح قديمة بشكل مثير للضحك مثل النموذج ت.تركز Big O على الأداء فقط بالطريقة التي تهم الأشخاص الذين يعيشون في الحاضر أو ​​المستقبل بنفس القدر.

• تسلط علامة Big O أيضًا الضوء بشكل مباشر على أهم مبدأ في برمجة/هندسة الكمبيوتر، وهي الحقيقة التي تلهم جميع المبرمجين الجيدين لمواصلة التفكير والحلم:الطريقة الوحيدة لتحقيق نتائج تتجاوز التقدم البطيء للتكنولوجيا هي أن تفعل ذلك ابتكار خوارزمية أفضل.

Answer 17

مثال خوارزمية (جافا):

// given a list of integers L, and an integer K
public boolean simple_search(List<Integer> L, Integer K)
{
    // for each integer i in list L
    for (Integer i : L)
    {
        // if i is equal to K
        if (i == K)
        {
            return true;
        }
    }

    return false;
}

وصف الخوارزمية:

• تبحث هذه الخوارزمية في قائمة ، عنصر حسب العنصر ، تبحث عن مفتاح ،

• التكرار على كل عنصر في القائمة ، إذا كان المفتاح ثم ارجع صحيحًا ،

• إذا كانت الحلقة قد انتهت دون العثور على المفتاح ، فأعد خطأ.

يمثل الترميز الكبير O-Bound في التعقيد (الوقت ، الفضاء ، ..)

للعثور على Big-O في الوقت المناسب:

• احسب مقدار الوقت (فيما يتعلق بحجم الإدخال) الذي يستغرقه أسوأ حالة:

• أسوأ حالة: المفتاح غير موجود في القائمة.

• الوقت (أسوأ حالة) = 4n+1

• الوقت: O (4n+1) = o (n) | في Big-O ، يتم إهمال الثوابت

• س (ن) ~ خطي

هناك أيضًا أوميغا الكبيرة ، التي تمثل تعقيدًا لأفضل حالة:

• أفضل حالة: المفتاح هو العنصر الأول.

• الوقت (أفضل حالة) = 4

• الوقت: ω (4) = o (1) ~ فورية ثابت

Answer 18

كبير س

F(x) = o (ز(x)) عندما يذهب x إلى (على سبيل المثال ، a = +∞) يعني أن هناك وظيفة ك مثل ذلك:

1. F(x) = ك(س)ز(س)

2. يحد K في بعض حي A (إذا A = +∞ ، وهذا يعني أن هناك أرقام N و M بحيث لكل x> n ، |ك(x) | <م).

بمعنى آخر ، باللغة الإنجليزية البسيطة: F(x) = o (ز(x)) ، x → a ، يعني أنه في حي أ ، F يتحلل إلى نتاج ز وبعض الوظيفة المحددة.

صغيرة س

بالمناسبة ، هنا للمقارنة مع تعريف صغير o.

F(x) = o (ز(x)) عندما يذهب x إلى وسيلة أن هناك وظيفة k بحيث:

1. F(x) = ك(س)ز(س)

2. ك(x) يذهب إلى 0 عندما يذهب x إلى.

أمثلة

• sin x = o (x) عندما x → 0.

• sin x = o (1) عندما x → +∞ ،

• x² + x = o (x) عندما x → 0 ،

• x² + x = o (x²) عندما x → +∞ ،

• ln (x) = o (x) = o (x) عندما x → +∞.

انتباه! يستخدم الترميز مع العلامة المتساوية "=" "مساواة مزيفة": صحيح أن O (g (x)) = o (g (x)) ، ولكن خطأ في ذلك o (g (x)) = o (g (س)). وبالمثل ، لا بأس في كتابة "ln (x) = o (x) عندما تكون x → +∞" ، لكن الصيغة "o (x) = ln (x)" لن تكون لها معنى.

مزيد من الأمثلة

• o (1) = o (n) = o (n²) عندما تكون n → +∞ (ولكن ليس العكس ، فإن المساواة "مزيفة") ،

• o (n) + o (n²) = س (ن²) عندما n → +∞

• س (س (ن²)) = س (ن²) عندما n → +∞

• على²)على³) = س (ن⁵) عندما n → +∞

---

هنا مقال ويكيبيديا: https://en.wikipedia.org/wiki/big_o_notation

Answer 19

يعد التدوين الكبير O وسيلة لوصف مدى سرعة تشغيل الخوارزمية نظرًا لعدد تعسفي من معلمات الإدخال ، والتي سنسميها "N". إنه مفيد في علوم الكمبيوتر لأن الأجهزة المختلفة تعمل بسرعات مختلفة ، وتقول ببساطة أن الخوارزمية تستغرق 5 ثوانٍ لا تخبرك كثيرًا لأنه على الرغم من أنك قد تقوم بتشغيل نظام مع معالج OCTO 4.5 جيجا هرتز ، فقد أقوم بتشغيل نظام يبلغ من العمر 15 عامًا ، 800 ميجاهرتز ، والذي قد يستغرق وقتًا أطول بغض النظر عن الخوارزمية. لذا ، بدلاً من تحديد مدى سرعة تشغيل الخوارزمية من حيث الوقت ، نقول مدى سرعة تشغيلها من حيث عدد معلمات الإدخال ، أو "N". من خلال وصف الخوارزميات بهذه الطريقة ، يمكننا مقارنة سرعات الخوارزميات دون الحاجة إلى مراعاة سرعة الكمبيوتر نفسه.

Answer 20

لست متأكدًا من أنني أساهم في هذا الموضوع ، لكنني ما زلت أعتقد أنني سأشاركه: لقد وجدت ذات مرة منشور المدونة هذا للحصول على بعض التفسيرات والأمثلة المفيدة (وإن كانت أساسية للغاية) على Big O:

من خلال أمثلة ، ساعد ذلك في الحصول على الأساسيات العارية في جمجمتي التي تشبه السلحفاة ، لذلك أعتقد أنها قراءة جميلة لمدة 10 دقائق لتتجول في الاتجاه الصحيح.

Answer 21

تريد أن تعرف كل شيء هناك لمعرفة Big O؟ اذا يمكنني.

لذلك للحديث عن Big O ، سأستخدم الكلمات التي تحتوي على واحد فقط. صوت واحد لكل كلمة. الكلمات الصغيرة سريعة. أنت تعرف هذه الكلمات ، وكذلك نحن. سنستخدم الكلمات بصوت واحد. هم صغيرون. أنا متأكد من أنك ستعرف كل الكلمات التي سنستخدمها!

الآن ، دعنا نتحدث عن العمل. معظم الوقت ، أنا لا أحب العمل. هل تحب العمل؟ قد يكون الأمر كذلك ، لكنني متأكد من أنني لا أفعل ذلك.

لا أحب الذهاب إلى العمل. لا أحب قضاء بعض الوقت في العمل. إذا كان لدي طريقي ، أود فقط أن ألعب ، وأفعل أشياء ممتعة. هل تشعر بنفسك كما أفعل؟

الآن في بعض الأحيان ، لا بد لي من الذهاب إلى العمل. ذلك محزن ولكنه الحقيقة. لذا ، عندما أكون في العمل ، لدي قاعدة: أحاول القيام بعمل أقل. بالقرب من عدم وجود عمل قدر الإمكان. ثم أذهب للعب!

لذا ، ها هي الأخبار الكبيرة: يمكن أن تساعدني Big O في عدم القيام بالعمل! يمكنني أن ألعب أكثر من الوقت ، إذا كنت أعرف Big O. أقل عمل ، المزيد من اللعب! هذا ما يساعدني الكبيرة على القيام به.

الآن لدي بعض العمل. لدي هذه القائمة: واحد ، اثنان ، ثلاثة ، أربعة ، خمسة ، ستة. يجب أن أضيف كل الأشياء في هذه القائمة.

واو ، أنا أكره العمل. لكن حسنًا ، يجب أن أفعل هذا. حتى هنا أذهب.

زائد اثنان هو ثلاثة ... بالإضافة إلى ثلاثة هو ستة ... وأربعة ... لا أعرف. انا تهت. من الصعب للغاية بالنسبة لي أن أفعل في رأسي. لا يهمني هذا النوع من العمل.

لذلك دعونا لا نفعل العمل. دعكم وأنا فقط أفكر في مدى صعوبة ذلك. ما مقدار العمل الذي يجب علي فعله ، لإضافة ستة أرقام؟

حسنا دعنا نري. يجب أن أضيف واحد واثنين ، ثم أضف ذلك إلى ثلاثة ، ثم أضف ذلك إلى أربعة ... الكل في الكل ، أحسب ستة يضيف. لا بد لي من القيام ستة يضاف لحل هذا.

هنا يأتي كبير يا ، ليخبرنا مدى صعوبة هذه الرياضيات.

يقول Big o: يجب أن نفعل ستة يضاف لحل هذا. إضافة واحد ، لكل شيء من واحد إلى ستة. ستة أجزاء صغيرة من العمل ... كل جزء من العمل هو إضافة واحد.

حسنًا ، لن أقوم بالعمل لإضافتها الآن. لكني أعرف مدى صعوبة ذلك. سيكون ستة إضافات.

أوه لا ، الآن لدي المزيد من العمل. شيش. من يصنع هذا النوع من الأشياء؟!

الآن يطلبون مني أن أضيف من واحد إلى عشرة! لماذا قد اقعل ذالك؟ لم أرغب في إضافة واحد إلى ستة. للإضافة من واحد إلى عشرة ... حسنا ... سيكون ذلك أكثر صعوبة!

كم سيكون أكثر صعوبة؟ ما مقدار العمل الذي يجب أن أفعله؟ هل أحتاج إلى خطوات أكثر أو أقل؟

حسنًا ، أعتقد أنني سأضطر إلى القيام بعشرة إضافات ... واحدة لكل شيء من واحد إلى عشرة. عشرة أكثر من ستة. سأضطر إلى العمل أكثر من ذلك بكثير لإضافة من واحد إلى عشرة ، من واحد إلى ستة!

لا أريد أن أضيف الآن. أريد فقط أن أفكر في مدى صعوبة إضافة ذلك كثيرًا. وآمل أن ألعب بأسرع ما يمكن.

لإضافة من واحد إلى ستة ، هذا هو بعض العمل. ولكن هل ترى ، لإضافة من واحد إلى عشرة ، هذا هو المزيد من العمل؟

Big o هو صديقك وألبي. يساعدنا Big O في التفكير في مقدار العمل الذي يتعين علينا القيام به ، حتى نتمكن من التخطيط. وإذا كنا أصدقاء مع Big O ، فيمكنه مساعدتنا في اختيار العمل الذي ليس صعبًا!

الآن يجب علينا القيام بعمل جديد. أوه ، لا. أنا لا أحب هذا العمل على الإطلاق.

العمل الجديد هو: أضف كل الأشياء من واحد إلى ن.

انتظر! ما هو N؟ هل فاتني ذلك؟ كيف يمكنني الإضافة من واحد إلى N إذا لم تخبرني ما هو N؟

حسنًا ، لا أعرف ما هو N. لم يتم إخباري. هل أنت؟ رقم؟ اوه حسناً. لذلك لا يمكننا القيام بالعمل. يا للعجب.

ولكن على الرغم من أننا لن نقوم بالعمل الآن ، يمكننا تخمين مدى صعوبة ذلك ، إذا عرفنا n. سيتعين علينا إضافة الأشياء ، أليس كذلك؟ بالطبع!

الآن هنا يأتي Big O ، وسيخبرنا مدى صعوبة هذا العمل. يقول: لإضافة كل الأشياء من واحد إلى ن ، واحد تلو الآخر ، هو o (n). لإضافة كل هذه الأشياء ، [أعلم أنني يجب أن أضيف N Times.] [1] هذا كبير O! يخبرنا مدى صعوبة القيام بنوع من العمل.

بالنسبة لي ، أفكر في Big o مثل رجل كبير وبطيء. إنه يفكر في العمل ، لكنه لا يفعل ذلك. قد يقول ، "هذا العمل سريع". أو قد يقول ، "هذا العمل بطيء للغاية وصعب!" لكنه لا يفعل العمل. إنه ينظر فقط إلى العمل ، ثم يخبرنا كم من الوقت قد يستغرق.

أنا أهتم بالكثير من أجل Big O. لماذا؟ لا أحب العمل! لا أحد يحب العمل. لهذا السبب نحن جميعا نحب كبيرة يا! يخبرنا مدى السرعة التي يمكننا بها العمل. إنه يساعدنا على التفكير في مدى العمل الشاق.

اه أوه ، المزيد من العمل. الآن ، دعونا لا نفعل العمل. ولكن ، دعنا نضع خطة للقيام بذلك ، خطوة بخطوة.

أعطونا مجموعة من عشر بطاقات. يتم خلطها جميعًا: سبعة ، أربعة ، اثنان ، ستة ... ليست مستقيمة على الإطلاق. والآن ... مهمتنا هي فرزها.

إرغ. هذا يبدو وكأنه الكثير من العمل!

كيف يمكننا فرز هذا السطح؟ لدي خطة.

سوف أنظر إلى كل زوج من البطاقات ، زوجًا من الزوج ، عبر سطح السفينة ، من الأول إلى الأخير. إذا كانت البطاقة الأولى في زوج واحد كبيرًا وكانت البطاقة التالية في هذا الزوج صغيرًا ، فأنا أقوم بتبديلها. وإلا ، أذهب إلى الزوج التالي ، وهكذا على ... وقريباً ، تم الانتهاء من سطح السفينة.

عندما يتم الانتهاء من سطح السفينة ، أسأل: هل قمت بتبديل البطاقات في هذا الممر؟ إذا كان الأمر كذلك ، يجب أن أفعل كل شيء مرة أخرى ، من الأعلى.

في مرحلة ما ، في وقت ما ، لن يكون هناك أي مقايضات ، وسيتم تنفيذ نوعنا من سطح السفينة. الكثير من العمل!

حسنًا ، ما مقدار العمل ، لفرز البطاقات بهذه القواعد؟

لدي عشر بطاقات. وفي معظم الأوقات - أي إذا لم يكن لدي الكثير من الحظ - يجب أن أذهب عبر سطح السفينة بأكمله حتى عشر مرات ، مع ما يصل إلى عشرة مقايضات في كل مرة عبر سطح السفينة.

كبير يا ، ساعدني!

يأتي Big o ويقول: بالنسبة إلى مجموعة من البطاقات n ، سيتم فرزها بهذه الطريقة في وقت o (n squared).

لماذا يقول n مربع؟

حسنًا ، أنت تعرف أن N squared هو n times n. الآن ، أحصل عليها: N Cards فحص ، حتى ما قد يكون في الأوقات من خلال سطح السفينة. هذه حلقتين ، لكل منهما خطوات ن. هذا هو عدد كبير من العمل الذي يتعين القيام به. الكثير من العمل ، بالتأكيد!

الآن عندما يقول Big O أن الأمر سيستغرق عملًا (n squared) ، فإنه لا يعني إضافة N squared ، على الأنف. قد يكون بعض الشيء أقل قليلاً ، لبعض الحالات. ولكن في أسوأ الحالات ، سيكون بالقرب من خطوات العمل المربعة لفرز سطح السفينة.

الآن هنا هو المكان الذي يكون فيه Big O صديقنا.

يشير Big O إلى هذا: نظرًا لأن N يصبح كبيرًا ، عندما نفرز البطاقات ، تصبح الوظيفة أكثر صعوبة من الوظيفة القديمة التي كانت موجودة. كيف لنا أن نعرف هذا؟

حسنًا ، إذا أصبح N كبيرًا حقيقيًا ، فنحن لا نهتم بما قد نضيفه إلى N أو N مربعة.

بالنسبة إلى Big n ، n squared أكبر من n.

يخبرنا Big O أن فرز الأشياء أمر صعب من إضافة الأشياء. o (n squared) هو أكثر من o (n) ل big n. هذا يعني: إذا أصبح N كبيرًا ، فإن فرز سطح السفينة المختلط من الأشياء يجب أن يستغرق وقتًا أكثر من مجرد إضافة أشياء مختلطة.

Big o لا يحل العمل بالنسبة لنا. يخبرنا Big O بمدى صعوبة العمل.

لدي سطح من البطاقات. لقد قمت بفرزهم. ساعدت. شكرًا.

هل هناك طريقة سريعة لفرز البطاقات؟ هل يمكن أن تساعدنا الكبيرة؟

نعم ، هناك طريقة أكثر سريعة! يستغرق الأمر بعض الوقت للتعلم ، لكنه يعمل ... ويعمل بسرعة كبيرة. يمكنك تجربته أيضًا ، لكن خذ وقتك مع كل خطوة ولا تفقد مكانك.

في هذه الطريقة الجديدة لفرز سطح السفينة ، لا نتحقق من أزواج البطاقات بالطريقة التي فعلناها منذ فترة. فيما يلي قواعدك الجديدة لفرز هذا السطح:

واحد: اخترت بطاقة واحدة في جزء من المجموعة التي نعمل عليها الآن. يمكنك اختيار واحد لي إذا أردت. (في المرة الأولى التي نفعل فيها هذا ، "جزء من سطح السفينة الذي نعمل عليه الآن" هو سطح السفينة بأكمله ، بالطبع).

الثاني: أقوم بتشويش سطح السفينة على تلك البطاقة التي اخترتها. ما هو هذا الرشق. كيف أتجول؟ حسنًا ، أذهب من بطاقة البدء لأسفل ، واحدًا تلو الآخر ، وأبحث عن بطاقة أعلى من بطاقة الرشاش.

ثالثًا: أذهب من بطاقة النهاية إلى أعلى ، وأبحث عن بطاقة منخفضة أكثر من بطاقة الرشاش.

بمجرد أن أجد هاتين البطاقتين ، أقوم بتبديلهما ، وأستمر في البحث عن المزيد من البطاقات للتبديل. وهذا هو ، أعود إلى الخطوة الثانية ، واشتغط على البطاقة التي اخترتها أكثر من ذلك.

في مرحلة ما ، ستنتهي هذه الحلقة (من اثنين إلى ثلاثة). ينتهي عندما يجتمع كل من نصفي هذا البحث على بطاقة splay. بعد ذلك ، قمنا للتو بتجميع سطح السفينة مع البطاقة التي اخترتها في الخطوة الأولى. الآن ، جميع البطاقات القريبة من البداية منخفضة من بطاقة splay ؛ والبطاقات القريبة من النهاية أعلى من بطاقة الرشاش. خدعة باردة!

أربعة (وهذا هو الجزء الممتع): لديّ طابقين صغيرين الآن ، واحد أقل من بطاقة الرشاش ، وواحدة أخرى مرتفعة. الآن أذهب إلى الخطوة الأولى ، على كل سطح صغير! وهذا يعني أنني أبدأ من الخطوة الأولى على سطح السفينة الصغيرة الأولى ، وعندما يتم هذا العمل ، أبدأ من الخطوة الأولى على سطح السفينة الصغير التالي.

أقوم بتفكيك سطح السفينة في أجزاء ، وفرز كل جزء ، وأكثر صغرًا وأكثر صغرًا ، وفي وقت ما لم يعد لدي عمل. الآن قد يبدو هذا بطيئًا ، مع كل القواعد. لكن ثق بي ، إنه ليس بطيئًا على الإطلاق. إنه عمل أقل بكثير من الطريقة الأولى لفرز الأشياء!

ماذا يسمى هذا النوع؟ يطلق عليه Quick Sort! تم صنع هذا النوع من قبل رجل يسمى سيارة هوار ودعاها بسرعة. الآن ، يتم استخدام الفرز السريع طوال الوقت!

فرز سريع يكسر الطوابق الكبيرة في الطوابق الصغيرة. وهذا يعني أنه يكسر المهام الكبيرة في تلك الصغيرة.

أمم. قد يكون هناك قاعدة هناك ، على ما أعتقد. لجعل المهام الكبيرة صغيرة ، كسرها.

هذا النوع سريع جدا. كيف السرعة؟ يخبرنا Big O: يحتاج هذا النوع من العمل إلى العمل ، في الحالة المتوسطة.

هل هو أكثر أو أقل بسرعة من النوع الأول؟ كبير يا ، الرجاء المساعدة!

كان النوع الأول o (n مربع). ولكن الفرز السريع هو o (n log n). أنت تعلم أن N log n أقل من n مربع ، بالنسبة إلى Big n ، أليس كذلك؟ حسنًا ، هكذا نعرف أن النوع السريع سريع!

إذا كان عليك فرز سطح السفينة ، فما هي أفضل طريقة؟ حسنًا ، يمكنك أن تفعل ما تريد ، لكنني سأختار نوعًا سريعًا.

لماذا أختار الفرز السريع؟ أنا لا أحب العمل ، بالطبع! أريد أن يتم العمل بمجرد أن أتمكن من إنجازه.

كيف أعرف أن النوع السريع أقل عمل؟ أعلم أن O (n log n) أقل من O (n مربع). O's أكثر صغيرة ، لذا فإن النوع السريع هو عمل أقل!

الآن أنت تعرف صديقي ، Big O. إنه يساعدنا على عمل أقل. وإذا كنت تعرف Big O ، يمكنك القيام بعمل أقل أيضًا!

لقد تعلمت كل ذلك معي! انت ذكي جدا! شكراً جزيلاً!

الآن تم الانتهاء من العمل ، دعنا نذهب للعب!

---

1]: هناك طريقة للغش وإضافة كل الأشياء من واحد إلى ن ، كل ذلك في وقت واحد. وجد بعض الأطفال المسمى غاوس هذا عندما كان في الثامنة من عمره. أنا لست ذكيًا رغم ذلك لا تسألني كيف فعل ذلك.

Answer 22

افترض أننا نتحدث عن خوارزمية أ, ، والتي يجب أن تفعل شيئًا مع مجموعة بيانات من الحجم ن.

ثم O( <some expression X involving n> ) يعني ، باللغة الإنجليزية البسيطة:

إذا كنت محظوظًا عند تنفيذ A ، فقد يستغرق إكمال عمليات X (n).

كما يحدث ، هناك وظائف معينة (فكر فيها التطبيقات من x (n)) التي تميل إلى الحدوث في كثير من الأحيان. هذه معروفة ومقارنة بسهولة (أمثلة: 1, Log N, N, N^2, N!, ، إلخ..)

بمقارنة هذه عند الحديث عنها أ وغيرها من الخوارزميات ، من السهل تصنيف الخوارزميات وفقًا لعدد العمليات مايو (أسوأ حالة) تتطلب إكمال.

بشكل عام ، سيكون هدفنا هو العثور على خوارزمية أو هيكلها أ وبهذه الطريقة التي سيكون بها وظيفة X(n) هذا يعود إلى عدد منخفض قدر الإمكان.

Answer 23

لدي طريقة أكثر بساطة لفهم التعقيد الزمني الذي يتراوح هو الأكثر شيوعًا لحساب تعقيد الوقت هو تدوين كبير. هذا يزيل جميع العوامل الثابتة بحيث يمكن تقدير وقت التشغيل فيما يتعلق بـ N كما يقترب N. بشكل عام يمكنك التفكير في الأمر مثل هذا:

statement;

ثابت. لن يتغير وقت تشغيل البيان فيما يتعلق بـ n

for ( i = 0; i < N; i++ )
  statement;

خطي. يتناسب وقت تشغيل الحلقة بشكل مباشر مع N. عندما يتضاعف n ، وكذلك وقت التشغيل.

for ( i = 0; i < N; i++ ) 
{
for ( j = 0; j < N; j++ )
  statement;
}

هو التربيعية. يتناسب وقت تشغيل الحلقتين مع مربع N. عندما يتضاعف n ، يزداد وقت التشغيل بمقدار n * n.

while ( low <= high ) 
{
 mid = ( low + high ) / 2;
 if ( target < list[mid] )
 high = mid - 1;
 else if ( target > list[mid] )
  low = mid + 1;
else break;
}

لوغاريتمي. يتناسب وقت تشغيل الخوارزمية مع عدد المرات التي يمكن تقسيمها على 2. لأن الخوارزمية تقسم منطقة العمل إلى نصفين مع كل تكرار.

void quicksort ( int list[], int left, int right )
{
  int pivot = partition ( list, left, right );
  quicksort ( list, left, pivot - 1 );
  quicksort ( list, pivot + 1, right );
}

هو n * log (n). يتكون وقت التشغيل من حلقات N (التكرارية أو العودية) التي هي اللوغاريتمية ، وبالتالي فإن الخوارزمية هي مزيج من الخطية واللوغاريتمي.

بشكل عام ، يكون القيام بشيء ما مع كل عنصر في بُعد واحد خطيًا ، والقيام بشيء ما مع كل عنصر بعدين هو التربيعية ، وتقسيم منطقة العمل إلى النصف هو لوغاريتمي. هناك تدابير كبيرة أخرى مثل الجذر المكعب ، الأسي ، ومربعة ، لكنها ليست شائعة تقريبًا. يوصف تدوين كبير O على أنه O () أين هو التدبير. سيتم وصف خوارزمية Quicksort على أنها O (n * log (n)).

ملاحظة: لم يأخذ أي من هذا في الاعتبار أفضل تدابير الحالة والأسوأ. سيكون لكل منها تدوين كبير O. لاحظ أيضًا أن هذا تفسير مبسط للغاية. Big O هو الأكثر شيوعًا ، لكنه أيضًا أكثر تعقيدًا أظهرته. هناك أيضًا رموز أخرى مثل Big Omega و Little O و Big Theta. ربما لن تصادفهم خارج دورة تحليل الخوارزمية.

• انظر أكثر في: هنا

Answer 24

قل أنت تطلب Harry Potter: مجموعة كاملة من 8 أفلام [Blu-ray] من Amazon وقم بتنزيل نفس مجموعة الأفلام عبر الإنترنت في نفس الوقت. تريد اختبار الطريقة أسرع. يستغرق التسليم ما يقرب من يوم للوصول وإكمال التنزيل قبل حوالي 30 دقيقة. رائعة! لذلك فهو سباق ضيق.

ماذا لو طلبت العديد من أفلام Blu-ray مثل Lord of the Rings و Twilight و The Dark Knight Trilogy ، وما إلى ذلك وتنزيل جميع الأفلام عبر الإنترنت في نفس الوقت؟ هذه المرة ، لا يزال التسليم يستغرق يومًا واحدًا لإكماله ، لكن التنزيل عبر الإنترنت يستغرق 3 أيام حتى النهاية. للتسوق عبر الإنترنت ، لا يؤثر عدد العناصر المشتراة (الإدخال) على وقت التسليم. الإخراج ثابت. نسمي هذا س (1).

للتنزيل عبر الإنترنت ، يتناسب وقت التنزيل بشكل مباشر مع أحجام ملفات الفيلم (إدخال). نسمي هذا على).

من التجارب ، نعلم أن مقاييس التسوق عبر الإنترنت أفضل من التنزيل عبر الإنترنت. من المهم جدًا فهم التدوين الكبير لأنه يساعدك على تحليل قابلية التوسع و نجاعة من الخوارزميات.

ملحوظة: يمثل التدوين الكبير O السيناريو الأسوأ من خوارزمية. لنفترض ذلك س (1) و على) هي أسوأ سيناريوهات الحالة أعلاه.

المرجعي : http://carlcheo.com/compsci

Answer 25

إذا كان لديك فكرة مناسبة عن اللانهاية في رأسك ، فهناك وصف موجز للغاية:

يخبرك Big O Concation تكلفة حل مشكلة كبيرة بلا حدود.

وعلاوة على ذلك

العوامل الثابتة ضئيلة

إذا قمت بالترقية إلى جهاز كمبيوتر يمكنه تشغيل الخوارزمية مرتين بالسرعة ، فلن يلاحظ Big O Todation ذلك. التحسينات المستمرة في العوامل صغيرة جدًا بحيث لا يمكن ملاحظتها في المقياس الذي يعمل معه التدوين الكبير. لاحظ أن هذا جزء مقصود من تصميم تدوين كبير O.

على الرغم من أنه يمكن اكتشاف أي شيء "أكبر" من عامل ثابت.

عند الاهتمام بإجراء الحسابات التي يكون حجمها "كبيرًا" بدرجة كافية ليتم اعتبارها ما لا نهاية تقريبًا ، فإن التدوين الكبير هو تكلفة حل مشكلتك تقريبًا.

---

إذا لم يكن ما سبق منطقيًا ، فليس لديك فكرة بديهية متوافقة عن اللانهاية في رأسك ، وربما يجب أن تتجاهل كل ما سبق ؛ الطريقة الوحيدة التي أعرفها لجعل هذه الأفكار صارمة ، أو شرحها إذا لم تكن مفيدة بالفعل ، هي أن تعلمك أولاً تدوينًا كبيرًا أو شيء مشابه. (على الرغم من أنك بمجرد فهم تدوين كبير في المستقبل ، قد يكون من المفيد إعادة النظر في هذه الأفكار)

Answer 26

ما هو التفسير الإنجليزي البسيط لتدوين "Big O"؟

ملاحظة سريعة جدا:

يشير O في "Big O" إلى "ترتيب" (أو "بالتحديد"
لذلك يمكنك الحصول على فكرتها حرفيًا أنها تستخدم لطلب شيء لمقارنته.

• "Big O" يفعل شيئين:

  1. يقدر عدد خطوات الطريقة التي ينطبق بها جهاز الكمبيوتر الخاص بك لإنجاز المهمة.
  2. تسهيل العملية للمقارنة مع الآخرين من أجل تحديد ما إذا كانت جيدة أم لا؟
  3. "Big O 'يحقق اثنين أعلاه مع موحدة Notations.

• هناك سبعة مموزات أكثر استخدامًا

  1. س (1) ، يعني أن جهاز الكمبيوتر الخاص بك ينجز مهمة 1 الخطوة ، إنها ممتازة ، مرتبة رقم 1
  2. o (logn) ، يعني جهاز الكمبيوتر الخاص بك إكمال مهمة logN خطوات ، جيدة ، مرتبة رقم 2
  3. س (ن) ، أنهى مهمة مع N الخطوات ، عادل ، الأمر رقم 3
  4. o (nlogn) ، ينهي المهمة مع O(NlogN) الخطوات ، ليست جيدة ، الطلب رقم 4
  5. o (n^2) ، احصل على مهمة N^2 الخطوات ، إنها سيئة ، الطلب رقم 5
  6. o (2^n) ، احصل على مهمة 2^N الخطوات ، إنه أمر فظيع ، الأمر رقم 6
  7. o (n!) ، قم بإنجاز مهمة N! الخطوات ، إنه أمر فظيع ، الطلب رقم 7

افترض أنك تحصل على تدوين O(N^2), ، ليس فقط أنت واضح ، فإن الطريقة تتخذ خطوات n*n لإنجاز مهمة ، كما ترى أنها ليست جيدة O(NlogN) من ترتيبها.

يرجى ملاحظة الطلب في نهاية السطر ، فقط لفهمك الأفضل. هناك أكثر من 7 رموز إذا تم النظر في جميع الاحتمالات.

في CS ، تسمى مجموعة الخطوات لإنجاز المهمة الخوارزميات.
في المصطلحات ، يتم استخدام تدوين كبير O لوصف أداء أو تعقيد الخوارزمية.

بالإضافة إلى ذلك ، يحدد Big O أسوأ حالة أو قياس الخطوات العلوية.
يمكنك الرجوع إلى Big-ω (Big-Omega) للحصول على أفضل حالة.

تدوين Big-ω (Big-Omega) (مقال) | أكاديمية خان

• ملخص
  يصف "Big O" أداء الخوارزمية ويقيمه.

  أو معالجةها رسميًا ، يصنف "Big O" الخوارزميات وتوحيد عملية المقارنة.

Answer 27

أبسط طريقة للنظر إليها (باللغة الإنجليزية البسيطة)

نحن نحاول أن نرى كيف يؤثر عدد معلمات الإدخال على وقت تشغيل الخوارزمية.إذا كان وقت تشغيل تطبيقك يتناسب مع عدد معلمات الإدخال، فيُقال أنه موجود في Big O لـ n.

البيان أعلاه هو بداية جيدة ولكنه ليس صحيحا تماما.

تفسير أكثر دقة (رياضي)

يفترض

ن = عدد معلمات الإدخال

T(n)= الوظيفة الفعلية التي تعبر عن وقت تشغيل الخوارزمية كدالة لـ n

ج= ثابت

f(n)= دالة تقريبية تعبر عن وقت تشغيل الخوارزمية كدالة لـ n

ثم بقدر ما يتعلق الأمر بـ Big O، فإن التقريب f(n) يعتبر جيدًا بما يكفي طالما أن الشرط أدناه صحيح.

lim     T(n) ≤ c×f(n)
n→∞

تقرأ المعادلة على الصورة: عندما تقترب n من اللانهاية ، T من n ، أصغر من أو تساوي c مضروبة في f من n.

في تدوين O الكبير يتم كتابة هذا كـ

T(n)∈O(n)

تتم قراءة هذا على أنه T of n موجود في O كبير من n.

العودة إلى اللغة الإنجليزية

استنادًا إلى التعريف الرياضي أعلاه، إذا قلت إن الخوارزمية الخاصة بك هي Big O لـ n، فهذا يعني أنها دالة لـ n (عدد معلمات الإدخال) أو أسرع.إذا كانت الخوارزمية الخاصة بك هي Big O لـ n، فستكون تلقائيًا أيضًا Big O لـ n المربع.

Big O of n يعني أن الخوارزمية الخاصة بي تعمل بهذه السرعة على الأقل.لا يمكنك إلقاء نظرة على تدوين Big O للخوارزمية الخاصة بك والقول إنها بطيئة.لا يمكنك إلا أن تقول بسرعة.

يفحص هذا خارجًا للحصول على فيديو تعليمي حول Big O من جامعة كاليفورنيا في بيركلي.إنه في الواقع مفهوم بسيط.إذا سمعت البروفيسور شوشوك (المعروف أيضًا باسم مدرس مستوى الله) يشرح ذلك، فسوف تقول "أوه، هذا كل ما في الأمر!".

Answer 28

لقد وجدت شرحًا رائعًا حقًا حول تدوين O الكبير خاصة بالنسبة لشخص ليس لديه الكثير من المعرفة بالرياضيات.

https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

يستخدم تدوين Big O في علوم الكمبيوتر لوصف الأداء أو تعقيد الخوارزمية.يصف Big O على وجه التحديد السيناريو الأسوأ ، ويمكن استخدامه لوصف وقت التنفيذ مطلوب أو المساحة المستخدمة (على سبيل المثالفي الذاكرة أو على القرص) بواسطة خوارزمية.

أي شخص يقرأ برمجة اللآلئ أو أي علوم كمبيوتر أخرى الكتب وليس لديها أسس في الرياضيات سوف تصطدم بالحائط عندما وصلوا إلى الفصول التي تذكر O (N log N) أو غيرها على ما يبدو بناء جملة مجنون.نأمل أن تساعدك هذه المقالة في الحصول على فهم أساسيات Big O واللوغاريتمات.

كمبرمج أولا وعالم رياضيات ثانيا (أو ربما ثالثا أو رابعا) لقد وجدت أن أفضل طريقة لفهم Big O تماما هي إنتاج بعض الأمثلة في التعليمات البرمجية.لذلك ، فيما يلي بعض الطلبات الشائعة ل النمو جنبا إلى جنب مع الأوصاف والأمثلة حيثما أمكن ذلك.

يا(1)

يصف O (1) خوارزمية سيتم تنفيذها دائما في نفس الوقت (أو المسافة) بغض النظر عن حجم مجموعة بيانات الإدخال.

bool IsFirstElementNull(IList<string> elements) {
    return elements[0] == null; } O(N)

على)

يصف O (N) خوارزمية سينمو أداؤها خطيا و بالتناسب المباشر مع حجم مجموعة بيانات الإدخال.المثال يوضح أدناه أيضا كيف تفضل Big O الأداء الأسوأ السيناريو;يمكن العثور على سلسلة مطابقة أثناء أي تكرار ل للحلقة وستعود الوظيفة مبكرا ، لكن تدوين Big O سيعود افترض دائما الحد الأعلى حيث ستؤدي الخوارزمية الحد الأقصى لعدد التكرارات.

bool ContainsValue(IList<string> elements, string value) {
    foreach (var element in elements)
    {
        if (element == value) return true;
    }

    return false;
} 

على²)

على²) يمثل خوارزمية يكون أداؤها مباشرا يتناسب مع مربع حجم مجموعة بيانات الإدخال.هذا يكون شائع مع الخوارزميات التي تتضمن تكرارات متداخلة على البيانات جبر.ستؤدي التكرارات المتداخلة الأعمق إلى O(N³)، على⁴) إلخ.

bool ContainsDuplicates(IList<string> elements) {
    for (var outer = 0; outer < elements.Count; outer++)
    {
        for (var inner = 0; inner < elements.Count; inner++)
        {
            // Don't compare with self
            if (outer == inner) continue;

            if (elements[outer] == elements[inner]) return true;
        }
    }

    return false;
}

يا (2^ن)

يا (2^ن) يشير إلى خوارزمية يتضاعف نموها مع كل إضافة إلى مجموعة بيانات الإدخال.منحنى النمو O(2^ن) الدالة هي أسي - يبدأ ضحلا جدا ، ثم يرتفع بشكل نيزكي.و مثال على O (2^ن) هي الحساب العودي لفيبوناتشي الأرقام:

int Fibonacci(int number) {
    if (number <= 1) return number;

    return Fibonacci(number - 2) + Fibonacci(number - 1);
}

اللوغاريتمات

اللوغاريتمات أصعب قليلا في الشرح لذا سأستخدم شائعا مثل:

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

يوصف هذا النوع من الخوارزمية بـ O(log N).التنصيف التكراري من مجموعات البيانات الموضحة في مثال البحث الثنائي ينتج نموا المنحنى الذي يبلغ ذروته في البداية ويتسطح ببطء حسب الحجم من مجموعات البيانات زيادة على سبيل المثالمجموعة بيانات إدخال تحتوي على 10 عناصر يستغرق ثانية واحدة لإكمالها ، تستغرق مجموعة البيانات التي تحتوي على 100 عنصر ثانيتان ، وستستغرق مجموعة البيانات التي تحتوي على 1000 عنصر ثلاث ثوان الثواني.مضاعفة حجم مجموعة بيانات الإدخال له تأثير ضئيل على نموها كما هو الحال بعد تكرار واحد للخوارزمية مجموعة البيانات سيتم تخفيضه إلى النصف وبالتالي على قدم المساواة مع مجموعة بيانات الإدخال نصف حجم.هذا يجعل الخوارزميات مثل البحث الثنائي فعالة للغاية عند التعامل مع مجموعات البيانات الكبيرة.

Answer 29

هذا تفسير مبسط للغاية ، لكنني آمل أن يغطي أهم التفاصيل.

دعنا نقول أن الخوارزمية التي تتعامل مع المشكلة تعتمد على بعض "العوامل" ، على سبيل المثال دعنا نجعلها ن و X.

اعتمادًا على N و X ، ستتطلب الخوارزمية بعض العمليات ، على سبيل المثال في أسوأ الحالات 3(N^2) + log(X) عمليات.

نظرًا لأن Big-O لا يهتم كثيرًا بعامل ثابت (ويعرف أيضًا باسم 3) ، فإن Big-O من خوارزميةك O(N^2 + log(X)). إنه يترجم أساسًا "مقدار العمليات التي تحتاجها الخوارزمية الخاصة بك لأسوأ مقاييس الحالة مع هذا".

Answer 30

مقدمة

خوارزمية: الإجراء/الصيغة لحل مشكلة

---

كيف تحليل الخوارزميات وكيف يمكننا مقارنة الخوارزميات ضد بعضها البعض؟

مثال: يُطلب منك أنت وصديق إنشاء وظيفة لتلخيص الأرقام من 0 إلى N. يمكنك التوصل إلى F (x) ويأتي صديقك بـ g (x). كلتا الوظيفتين لهما نفس النتيجة ، ولكن خوارزمية مختلفة. من أجل مقارنة كفاءة الخوارزميات بشكل موضوعي تدوين كبير.

تدوين كبير: يصف مدى سرعة نمو وقت التشغيل بالنسبة للمدخلات حيث تصبح المدخلات كبيرة بشكل تعسفي.

3 الوجبات الرئيسية:

1. قارن مدى سرعة نمو وقت التشغيل ليس قارن أوقات التشغيل الدقيقة (يعتمد على الأجهزة)
2. فقط مهتم بوقت التشغيل ينمو نسبة إلى المدخلات (ن)
3. كما ن يصبح كبيرًا بشكل تعسفي ، ركز على المصطلحات التي ستنمو أسرع مع تزايد (التفكير في اللانهاية) الملقب التحليل المقارب

تعقيد الفضاء: بصرف النظر عن التعقيد الزمني ، فإننا نهتم أيضًا بتعقيد الفضاء (مقدار الذاكرة/المساحة التي تستخدمها الخوارزمية). بدلاً من التحقق من وقت العمليات ، نتحقق من حجم تخصيص الذاكرة.