Big-O للأطفال بعمر ثماني سنوات؟[ينسخ]

Question

هذا السؤال لديه بالفعل إجابة هنا:

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

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

• مثل ما الذي ستفعله عملية O(n^2) بالضبط؟
• وماذا يعني ذلك إذا كانت العملية هي O(n log(n))؟
• وهل يجب على شخص ما أن يدخن الكراك ليكتب O(x!)؟

Answer 1

إحدى طرق التفكير في الأمر هي:

O(N^2) يعني بالنسبة لكل عنصر أنك تفعل شيئًا مع كل عنصر آخر، مثل مقارنتها.نوع الفقاعة هو مثال على ذلك.

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

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

Answer 2

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

Big-O       |  computations for 10 things |  computations for 100 things
----------------------------------------------------------------------
O(1)        |   1                         |     1
O(log(n))   |   3                         |     7
O(n)        |  10                         |   100
O(n log(n)) |  30                         |   700
O(n^2)      | 100                         | 10000

لذا خذ الفرز السريع وهو O(n log(n)) مقابل الفرز الفقاعي وهو O(n^2).عند فرز 10 أشياء، يكون الفرز السريع أسرع بثلاث مرات من فرز الفقاعات.ولكن عند فرز 100 شيء، يكون الأمر أسرع 14 مرة!من الواضح أن اختيار أسرع خوارزمية أمر مهم إذن.عندما تصل إلى قواعد بيانات تحتوي على مليون صف، فقد يعني ذلك الفرق بين تنفيذ الاستعلام الخاص بك في 0.2 ثانية، مقابل استغراقه لساعات.

هناك شيء آخر يجب أخذه في الاعتبار وهو أن الخوارزمية السيئة هي أحد الأشياء التي لا يمكن لقانون مور أن يساعدها.على سبيل المثال، إذا كان لديك بعض الحسابات العلمية مثل O(n^3) ويمكنها حساب 100 شيء في اليوم، فإن مضاعفة سرعة المعالج تحصل على 125 شيئًا فقط في اليوم.ومع ذلك، قم بإجراء هذا الحساب إلى O(n^2) وستقوم بـ 1000 شيء يوميًا.

إيضاح:في الواقع، لا يقول Big-O شيئًا عن الأداء المقارن لخوارزميات مختلفة عند نفس نقطة الحجم المحددة، بل يتحدث بدلاً من ذلك عن الأداء المقارن لنفس الخوارزمية عند نقاط حجم مختلفة:

                 computations     computations       computations
Big-O       |   for 10 things |  for 100 things |  for 1000 things
----------------------------------------------------------------------
O(1)        |        1        |        1        |         1
O(log(n))   |        1        |        3        |         7
O(n)        |        1        |       10        |       100
O(n log(n)) |        1        |       33        |       664
O(n^2)      |        1        |      100        |     10000

Answer 3

قد تجد أنه من المفيد تصور ذلك:

أيضا على لوجي/لوجكس حجم الوظائف ن^1/2, ، ن، ن² تبدو جميعها خطوط مستقيمة, ، بينما على سجلY/X حجم 2^ن, ، ه^ن, 10^ن هي خطوط مستقيمة و ن! هو خطي (يبدو ن سجل ن).

Answer 4

قد يكون هذا حسابيًا للغاية، ولكن هذه هي محاولتي.(أنا أكون عالم الرياضيات.)

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

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

لذا فإن الصفقة الحقيقية هي F(ن).لو F لا ينمو على الإطلاق مع ن, ، على سبيل المثال. F(ن) = 1، فسوف تقوم بالتوسع بشكل خيالي --- سيكون وقت تشغيلك دائمًا عادلاً أ + ب.لو F ينمو خطيا مع ن, ، أي. F(ن) = ن, ، سيتم قياس وقت التشغيل الخاص بك إلى حد كبير بأفضل ما يمكن توقعه --- إذا كان المستخدمون ينتظرون 10 ns لـ 10 عناصر، فسوف ينتظرون 10000 ns لـ 10000 عنصر (تجاهل الثابت الإضافي).ولكن إذا كان ينمو بشكل أسرع، مثل ن², ، فأنت في ورطة؛ستبدأ الأمور في التباطؤ كثيرًا عندما تحصل على مجموعات أكبر. F(ن) = ن سجل(ن) هو حل وسط جيد، عادة:لا يمكن أن تكون عمليتك بهذه البساطة بحيث تعطي مقياسًا خطيًا، ولكنك تمكنت من تقليل الأشياء بحيث يتم قياسها بشكل أفضل بكثير من F(ن) = ن².

ومن الناحية العملية، إليك بعض الأمثلة الجيدة:

• س(1):استرجاع عنصر من مصفوفة.نحن نعرف بالضبط مكان وجوده في الذاكرة، لذا نذهب للحصول عليه.لا يهم إذا كانت المجموعة تحتوي على 10 عناصر أو 10000؛فهو لا يزال في الفهرس (على سبيل المثال) 3، لذلك ننتقل فقط إلى الموقع 3 في الذاكرة.
• يا(ن):استرجاع عنصر من قائمة مرتبطة.هنا، أ = 0.5، لأنه في المتوسط ​​سيتعين عليك مراجعة نصف القائمة المرتبطة قبل العثور على العنصر الذي تبحث عنه.
• يا(ن²):خوارزميات الفرز "الغبية" المختلفة.لأن استراتيجيتهم بشكل عام تتضمن، لكل عنصر (ن)، فإنك تنظر إلى جميع العناصر الأخرى (مرات أخرى ن, ، إعطاء ن²)، ثم ضع نفسك في المكان المناسب.
• يا(ن سجل(ن))):خوارزميات الفرز "الذكية" المختلفة.اتضح أنك تحتاج فقط إلى النظر، على سبيل المثال، إلى 10 عناصر في 10¹⁰- جمع العناصر لفرز نفسك بذكاء بالنسبة لك الجميع آخر في المجموعة.لأن الجميع كذلك أيضًا سننظر إلى 10 عناصر، ويتم تنسيق السلوك الناشئ بشكل صحيح بحيث يكون هذا كافيًا لإنتاج قائمة مرتبة.
• يا(ن!):خوارزمية "تجرب كل شيء"، نظرًا لوجود (متناسب مع) ن!مجموعات ممكنة من ن العناصر التي قد تحل مشكلة معينة.لذلك فهو يكرر كل هذه المجموعات، ويجربها، ثم يتوقف عندما ينجح.

Answer 5

إجابة don.neufeld جيدة جدًا، لكن من المحتمل أن أشرحها في جزأين:أولاً، هناك تسلسل هرمي تقريبي لـ O() الذي تقع فيه معظم الخوارزميات.بعد ذلك، يمكنك إلقاء نظرة على كل واحدة منها للتوصل إلى رسومات تخطيطية لما هي عليه عادي خوارزميات ذلك التعقيد الزمني تفعل.

لأغراض عملية، فإن O() الوحيدة التي يبدو أنها مهمة هي:

• O(1) "الوقت الثابت" - الوقت المطلوب مستقل عن حجم الإدخال.كفئة تقريبية، سأقوم بتضمين خوارزميات مثل عمليات البحث عن التجزئة وUnion-Find هنا، على الرغم من أن أيًا منهما ليس في الواقع O(1).
• O(log(n)) "لوغاريتمي" - يصبح أبطأ عندما تحصل على مدخلات أكبر، ولكن بمجرد أن تصبح مدخلاتك كبيرة إلى حد ما، فلن تتغير بدرجة كافية للقلق.إذا كان وقت التشغيل الخاص بك على ما يرام مع بيانات ذات حجم معقول، فيمكنك إغراقه بالقدر الذي تريده من البيانات الإضافية وسيظل الأمر على ما يرام.
• O(n) "خطي" - كلما زادت المدخلات، كلما استغرق الأمر وقتًا أطول، في مقايضة متساوية.ثلاثة أضعاف حجم الإدخال سيستغرق ما يقرب من ثلاثة أضعاف الوقت.
• O(n log(n)) "أفضل من الدرجة التربيعية" - زيادة حجم الإدخال أمر مؤلم، ولكن لا يزال من الممكن التحكم فيه.من المحتمل أن تكون الخوارزمية جيدة، لكن المشكلة الأساسية أكثر صعوبة (القرارات أقل محلية فيما يتعلق ببيانات الإدخال) من تلك المشكلات التي يمكن حلها في الوقت الخطي.إذا كانت أحجام المدخلات الخاصة بك ترتفع، فلا تفترض أنه يمكنك بالضرورة التعامل مع ضعف الحجم دون تغيير البنية الخاصة بك (على سبيل المثال، عن طريق نقل الأشياء إلى حسابات دفعة بين عشية وضحاها، أو عدم القيام بالأشياء لكل إطار).لا بأس إذا زاد حجم الإدخال قليلاً؛فقط احترس من المضاعفات.
• O(n^2) "تربيعي" - لن يعمل إلا عند حجم معين من مدخلاتك، لذا انتبه إلى الحجم الذي يمكن أن يصل إليه.أيضًا، قد تكون الخوارزمية الخاصة بك سيئة - فكر جيدًا لمعرفة ما إذا كانت هناك خوارزمية O(n log(n)) من شأنها أن تمنحك ما تحتاجه.بمجرد وصولك إلى هنا، اشعر بالامتنان الشديد للأجهزة الرائعة التي تم منحنا إياها.منذ وقت ليس ببعيد، كان ما تحاول القيام به مستحيلاً لجميع الأغراض العملية.
• O(n^3) "مكعب" - لا يختلف تمامًا عن O(n^2).تنطبق نفس التعليقات، ولكن أكثر من ذلك.هناك فرصة جيدة لأن تتمكن خوارزمية أكثر ذكاءً من تقليص حجمها هذه المرة إلى شيء أصغر، على سبيل المثال O(n^2 log(n)) أو O(n^2.8...)، ولكن مرة أخرى، هناك فرصة جيدة لذلك لن يستحق العناء.(أنت بالفعل محدود في حجم مدخلاتك العملية، وبالتالي فإن العوامل الثابتة التي قد تكون مطلوبة للخوارزميات الأكثر ذكاءً من المحتمل أن تطغى على مزاياها في الحالات العملية.كما أن التفكير بطيء؛إن السماح للكمبيوتر بمضغه قد يوفر لك الوقت بشكل عام.)
• O(2^n) "أسي" - المشكلة إما أنها صعبة حسابيًا بشكل أساسي أو أنك أحمق.هذه المشاكل لها نكهة مميزة بالنسبة لهم.يتم تحديد أحجام المدخلات الخاصة بك بحد أقصى محدد إلى حد ما.ستعرف بسرعة ما إذا كنت تتناسب مع هذا الحد أم لا.

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

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

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

لا شيء من هذه صارمة.لا سيما خوارزميات الوقت الخطية (O(n)):يمكنني أن أتوصل إلى عدد من الأمثلة حيث يتعين عليك النظر إلى جميع المدخلات، ثم نصفها، ثم نصفها، وما إلى ذلك.أو العكس - حيث تقوم بجمع أزواج من المدخلات معًا، ثم تكرر على المخرجات.هذه لا تتناسب مع الوصف أعلاه، نظرًا لأنك لا تنظر إلى كل مدخلات مرة واحدة، ولكنها لا تزال تظهر في وقت خطي.ومع ذلك، في 99.2% من الحالات، يعني الوقت الخطي النظر إلى كل مدخل مرة واحدة.

Answer 6

من السهل إثبات الكثير من هذه الأشياء باستخدام شيء غير برمجي، مثل خلط البطاقات.

فرز مجموعة أوراق اللعب من خلال المرور عبر المجموعة بأكملها للعثور على الآس البستوني، ثم المرور عبر المجموعة بأكملها للعثور على ورقتي البستوني، وهكذا سيكون أسوأ حالة n^2، إذا تم فرز المجموعة بالفعل بشكل عكسي.لقد نظرت إلى جميع البطاقات الـ 52 52 مرة.

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

Answer 7

حسنًا - هناك بعض الإجابات الجيدة جدًا هنا ولكن يبدو أن جميعها تقريبًا ترتكب نفس الخطأ وهو منتشر في الاستخدام الشائع.

بشكل غير رسمي، نكتب أن f(n) = O( g(n) ) إذا كان g(n) يصل إلى عامل قياس ولكل n أكبر من بعض n0، أكبر من و (ن).أي ف(ن) لا ينمو بشكل أسرع من، أو هو يحدها من فوق بواسطة ز (ن).هذا لا يخبرنا شيئًا عن مدى سرعة نمو f(n)، باستثناء حقيقة أنه مضمون أنه لن يكون أسوأ من g(n).

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

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

بدلًا من ذلك، إذا أردنا أن نقول إن دالة تنمو بنفس سرعة نمو أي دالة أخرى، فإننا نستخدمها ثيتا لتوضيح هذه النقطة (سأكتب T( f(n) ) ليعني heta of f(n) في تخفيض السعر).T( g(n) ) هي يد قصيرة يحدها من فوق و تحت بواسطة g(n)، مرة أخرى، حتى عامل القياس وبشكل مقارب.

هذا هو f(n) = T( g(n) ) <=> f(n) = O(g(n)) و g(n) = O(f(n)).في مثالنا، يمكننا أن نرى أن n != T( 2^n ) لأن 2^n != O(n).

لماذا تقلق بشأن هذا؟لأنك في سؤالك تكتب "هل سيضطر شخص ما إلى تدخين الكراك لكتابة O (x!)؟" الجواب لا - لأن كل ما تكتبه في الأساس سيكون مقيدا من الأعلى بوظيفة العامل.وقت تشغيل الفرز السريع هو O(n!) - إنه ليس مقيدًا.

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

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

كيف يرتبط هذا بسؤالك حول الإنجازات العملية لهذه الحدود؟حسنًا، لسوء الحظ، يخفي تدوين O() الثوابت التي يتعين على تطبيقات العالم الحقيقي التعامل معها.لذا، على الرغم من أنه يمكننا القول، على سبيل المثال، بالنسبة لعملية T(n^2) أنه يتعين علينا زيارة كل زوج محتمل من العناصر، إلا أننا لا نعرف عدد المرات التي يتعين علينا زيارتهم (باستثناء أنها ليست دالة لـ ن).لذلك قد يتعين علينا زيارة كل زوج 10 مرات، أو 10^10 مرات، ولا يوجد تمييز بين عبارة T(n^2).يتم أيضًا إخفاء الوظائف ذات الترتيب الأدنى - قد يتعين علينا زيارة كل زوج من العناصر مرة واحدة، وكل عنصر فردي 100 مرة، لأن n^2 + 100n = T(n^2).الفكرة وراء تدوين O() هي أنه بالنسبة إلى n كبيرة بدرجة كافية، فإن هذا لا يهم على الإطلاق لأن n^2 تصبح أكبر بكثير من 100n لدرجة أننا لا نلاحظ حتى تأثير 100n على وقت التشغيل.ومع ذلك، فإننا غالبًا ما نتعامل مع "صغير بما فيه الكفاية" بحيث تُحدث العوامل الثابتة وما إلى ذلك فرقًا حقيقيًا وهامًا.

على سبيل المثال، الفرز السريع (متوسط ​​التكلفة T(n.log n)) وheapsort (متوسط ​​التكلفة T(n.log n)) كلاهما خوارزميات فرز بنفس متوسط ​​التكلفة - ومع ذلك فإن الفرز السريع عادة ما يكون أسرع بكثير من الفرز الكومة.وذلك لأن heapsort يقوم بعدد قليل من المقارنات لكل عنصر مقارنة بالفرز السريع.

هذا لا يعني أن تدوين O() عديم الفائدة، ولكنه غير دقيق.إنها أداة غير حادة يمكن استخدامها من أجل n الصغيرة.

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

Answer 8

أحاول أن أشرح ذلك من خلال إعطاء أمثلة بسيطة على التعليمات البرمجية في C#.

ل List<int> numbers = new List<int> {1,2,3,4,5,6,7,12,543,7};

يبدو O(1).

return numbers.First();

يبدو O(n).

int result = 0;
foreach (int num in numbers)
{
    result += num;
}
return result;

يبدو O(n log(n))

int result = 0;
foreach (int num in numbers)
{
    int index = numbers.length - 1;
    while (index > 1)
    {
        // yeah, stupid, but couldn't come up with something more useful :-(
        result += numbers[index];
        index /= 2;
    }
}
return result;

يبدو O(n^2).

int result = 0;
foreach (int outerNum in numbers)
{
    foreach (int innerNum in numbers)
    {
        result += outerNum * innerNum;
    }
}
return result;

يبدو أن O(n!) متعب من التوصل إلى أي شيء بسيط.
لكن أتمنى أن تكون قد فهمت النقطة العامة؟

Answer 9

الطريقة التي أصف بها الأمر لأصدقائي غير التقنيين هي كما يلي:

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

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

الآن، فكر في الضرب متعدد الأرقام.ربما تعلمت ذلك في عمر 8 أو 9 سنوات تقريبًا.لقد قمت (كما نأمل) بالكثير من التدريبات المتكررة لتعلم الآليات التي تقف وراءها.

الآن، تخيل أنني أعطيتك هذين الرقمين المكونين من 100 رقم وطلبت منك ضربهما معًا.هذا سيكون كثيرًا، كثيراً مهمة أصعب، وهو الأمر الذي قد يستغرق ساعات طويلة للقيام به - ومن غير المرجح أن تفعله دون أخطاء.والسبب في ذلك هو أن الضرب (هذا الإصدار) هو O(n^2);يجب ضرب كل رقم في الرقم السفلي بكل رقم في الرقم العلوي، مما يترك إجمالي عمليات n^2 تقريبًا.في حالة الأعداد المكونة من 100 رقم، يكون هذا 10000 ضرب.

Answer 10

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

O(n) يعني أن الوقت الذي ستستغرقه الخوارزمية الخاصة بك ينمو خطيًا مع زيادة مدخلاتك.O(n^2) يعني أن الوقت الذي تستغرقه الخوارزمية ينمو مع مربع إدخالك.وهكذا دواليك.

Answer 11

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

O(1) -> زيادة N لا تُحدث أي فرق على الإطلاق

O(log(N)) -> في كل مرة تضاعف فيها V N، عليك قضاء وقت إضافي T لإكمال المهمة.V يضاعف N مرة أخرى، وأنت تنفق نفس المبلغ.

O(N) -> في كل مرة تضاعف فيها V N، فإنك تقضي ضعف الوقت.

O(N^2) -> في كل مرة تضاعف فيها V N، فإنك تقضي 4x من الوقت.(ليس عادلا!!!)

O(N log(N)) -> في كل مرة تضاعف فيها V N، فإنك تقضي ضعف الوقت بالإضافة إلى المزيد.

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

يمكن أن تحتوي بعض الحدود على تعبيرات غريبة إذا أحدثت فرقًا للأشخاص المعنيين.لقد رأيت أشياء مثل O(N log(N) log(log(N))) في مكان ما في Knuth’s Art of Computer Programming لبعض الخوارزميات.(لا أستطيع أن أتذكر أي واحد من الجزء العلوي من رأسي)

Answer 12

شيء واحد لم يتم التطرق إليه بعد لسبب ما:

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

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

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

Answer 13

"الحدس" وراء Big-O

تخيل "منافسة" بين وظيفتين على x، مع اقتراب x من اللانهاية:و (خ) و ز (خ).

الآن، إذا كانت إحدى الدالات من نقطة ما (بعض x) لها دائمًا قيمة أعلى من الأخرى، فلنسمي هذه الدالة "أسرع" من الأخرى.

لذا، على سبيل المثال، إذا رأيت لكل x > 100 أن f(x) > g(x)، فإن f(x) "أسرع" من g(x).

في هذه الحالة نقول g(x) = O(f(x)).تطرح f(x) نوعًا ما من "حد السرعة" لـ g(x)، حيث أنها تتجاوزها في النهاية وتتركها وراءها إلى الأبد.

هذا ليس بالضبط تعريف تدوين كبير O, ، والتي تنص أيضًا على أن f(x) يجب أن تكون أكبر من C*g(x) فقط لبعض C الثابتة (وهي مجرد طريقة أخرى للقول أنه لا يمكنك مساعدة g(x) على الفوز بالمنافسة عن طريق ضربها في عامل ثابت - f(x) سيفوز دائمًا في النهاية).يستخدم التعريف الرسمي أيضًا القيم المطلقة.لكن آمل أن أكون قد تمكنت من جعل الأمر بديهيًا.

Answer 14

• وهل يجب على شخص ما أن يدخن الكراك ليكتب O(x!)؟

لا، فقط استخدم Prolog.إذا كتبت خوارزمية فرز في Prolog من خلال وصف أن كل عنصر يجب أن يكون أكبر من السابق، وتركت التراجع يقوم بالفرز نيابةً عنك، فسيكون ذلك O(x!).يُعرف أيضًا باسم "نوع التقليب".

Answer 15

تعجبني إجابة دون نيوفيلد، ولكن أعتقد أنه يمكنني إضافة شيء ما حول O(n log n).

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

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

إذا فكرت في الأمر بعناية، سترى أن الفرز السريع يقوم بتنفيذ خوارزمية تقسيم O(n) على عناصر n بأكملها، ثم تقسيم O(n) مرتين على عناصر n/2، ثم 4 مرات على عناصر n/4، إلخ...حتى تصل إلى أقسام n على عنصر واحد (وهو منحط).عدد المرات التي تقسم فيها n إلى النصف للوصول إلى 1 هو تقريبًا log n، وكل خطوة هي O(n)، لذا فإن القسمة العودية هي O(n log n).يتم إنشاء Mergesort بالطريقة الأخرى، بدءًا من إعادة التركيب n لعنصر واحد، والانتهاء بإعادة التركيب n من العناصر، حيث تكون إعادة التركيب لقائمتين مفروزتين هي O(n).

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

Answer 16

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

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

Answer 17

فكر في الأمر على أنه تكديس قطع الليغو (ن) عموديًا والقفز فوقها.

O(1) يعني في كل خطوة أنك لا تفعل شيئًا.الارتفاع يبقى كما هو.

O(n) يعني أنه في كل خطوة، تقوم بتكديس الكتل c، حيث c1 ثابت.

O(n^2) يعني أنه في كل خطوة، تقوم بتكديس الكتل c2 x n، حيث c2 ثابت، وn هو عدد الكتل المكدسة.

O(nlogn) يعني أنه في كل خطوة، تقوم بتكديس كتل c3 x n x log n، حيث c3 ثابت، وn هو عدد الكتل المكدسة.

Answer 18

لفهم O(n log n)، تذكر أن log n يعني log-base-2 لـ n.ثم انظر إلى كل جزء:

O(n) هو، أكثر أو أقل، عندما تعمل على كل عنصر في المجموعة.

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

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

Answer 19

فقط للرد على تعليقين على مشاركتي أعلاه:

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

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

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

Answer 20

أخبر سجلك (n) البالغ من العمر ثماني سنوات يعني عدد المرات التي يتعين عليك فيها تقطيع طول n سجل إلى قسمين حتى يصل إلى الحجم n=1 :p

O (n log n) عادة ما يتم الفرز O (n ^ 2) عادة ما يقارن جميع أزواج العناصر

Answer 21

لنفترض أن لديك جهاز كمبيوتر يمكنه حل مشكلة ذات حجم معين.تخيل الآن أنه يمكننا مضاعفة الأداء عدة مرات.ما حجم المشكلة التي يمكننا حلها مع كل عملية مضاعفة؟

إذا تمكنا من حل مسألة مضاعفة الحجم، فهذا هو O(n).

إذا كان لدينا مضاعف ليس واحدًا، فهذا نوع من التعقيد متعدد الحدود.على سبيل المثال، إذا كانت كل مضاعفة تسمح لنا بزيادة حجم المشكلة بحوالي 40%، فهي O(n^2)، وحوالي 30% ستكون O(n^3).

إذا أضفنا فقط إلى حجم المشكلة، فسيكون الأمر أسيًا أو أسوأ.على سبيل المثال، إذا كانت كل مضاعفة تعني أنه يمكننا حل مشكلة أكبر بمقدار 1، فهي O(2^n).(وهذا هو السبب في أن فرض مفتاح التشفير الغاشمة يصبح مستحيلاً فعليًا باستخدام مفاتيح ذات حجم معقول:يتطلب مفتاح 128 بت حوالي 16 كوينتيليون مرة معالجة أكثر من 64 بت.)

Answer 22

هل تتذكر حكاية السلحفاة والأرنب (السلحفاة والأرنب)؟

على المدى الطويل، تفوز السلحفاة، ولكن على المدى القصير يفوز الأرنب.

هذا مثل O(logN) (السلحفاة) مقابل.يا (ن) (أرنب).

إذا اختلفت طريقتان في حجم O الكبير، فهناك مستوى من N ستفوز عنده إحداهما، لكن Big-O لا تقول شيئًا عن مدى حجم N.

Answer 23

لكي أبقى صادقًا مع السؤال المطروح، سأجيب على السؤال بنفس الطريقة التي أجيب بها على طفل يبلغ من العمر 8 سنوات

لنفترض أن بائع الآيس كريم يقوم بإعداد عدد من الآيس كريم (على سبيل المثال N) بأشكال مختلفة مرتبة بطريقة منظمة.تريد أن تأكل الآيس كريم الموجود في المنتصف

حالة 1 :- يمكنك تناول الآيس كريم فقط إذا كنت قد أكلت كل الآيس كريم أصغر منه سيكون عليك أن تأكل نصف جميع الآيس كريم المحضرة (المدخلات). تعتمد الإجابة بشكل مباشر على حجم الإدخال سيكون الحل من أجل o (N)

الحالة 2:- يمكنك تناول الآيس كريم مباشرة في المنتصف

الحل هو O(1)

الحالة 3 :يمكنك تناول الآيس كريم فقط إذا كنت قد أكلت كل الآيس كريم أصغر منه وفي كل مرة تأكل الآيس كريم تسمح لطفل آخر (طفل جديد في كل مرة) بتناول كل الآيس كريم الخاص به إجمالي الوقت المستغرق سيكون N + N + N....... (N/2) مرات سيكون الحل O (N2)

Answer 24

السجل (ن) يعني النمو اللوغاريتمي.ومن الأمثلة على ذلك خوارزميات فرق تسد.إذا كان لديك 1000 رقم مرتبة في مصفوفة (على سبيل المثال.3، 10، 34، 244، 1203 ...) وتريد البحث عن رقم في القائمة (ابحث عن موضعه)، يمكنك البدء بالتحقق من قيمة الرقم في الفهرس 500.إذا كان أقل مما تسعى إليه، فانتقل إلى 750.إذا كان أعلى مما تسعى إليه، فاقفز إلى 250.ثم تكرر العملية حتى تجد القيمة (والمفتاح).في كل مرة نقفز فيها إلى نصف مساحة البحث، يمكننا التخلص من اختبار العديد من القيم الأخرى لأننا نعلم أن الرقم 3004 لا يمكن أن يكون أعلى من الرقم 5000 (تذكر أنها قائمة مرتبة).

n log(n) يعني n * log(n).

Answer 25

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

مثل ما سيكون بالضبط O(n^2) العملية تفعل؟

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

ملحوظة:هذا يقترب من العائد البسيط n(n-1) وهو قريب بما فيه الكفاية ل n^2.

وماذا يعني ذلك إذا كانت العملية O(n log(n))?

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

ملحوظة:هذا سوف يسفر n * log n to the base 10.

وهل يتعين على شخص ما أن يدخن الكراك ليكتب O(x!)?

أنت طفل غني وفي خزانة الملابس الخاصة بك هناك الكثير من الملابس، هناك x أدراج لكل نوع من الملابس، الأدراج بجوار بعضها البعض، الدرج الأول به قطعة واحدة، كل درج به عدد من الملابس كما هو الحال في الدرج الموجود على يساره وقطعة أخرى، لذلك لديك شيء مثل 1 قبعة، 2 شعر مستعار،.. (x-1) السراويل، ثم x قمصان.الآن، بكم طريقة يمكنك ارتداء الملابس باستخدام قطعة واحدة من كل درج.

ملحوظة:يمثل هذا المثال عدد الأوراق في شجرة القرار حيث number of children = depth, ، والذي يتم من خلال 1 * 2 * 3 * .. * x