هل قمت بتطبيق نظرية التعقيد الحسابي في الحياة الحقيقية؟

Question

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

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

Answer 1

س(1):كود عادي بدون حلقات.يتدفق فقط من خلال.عمليات البحث في جدول البحث هي O(1) أيضًا.

يا (سجل (ن)):خوارزميات محسنة بكفاءة.مثال:خوارزميات الشجرة الثنائية والبحث الثنائي.عادة لا تؤذي.أنت محظوظ إذا كان لديك مثل هذه الخوارزمية في متناول اليد.

على):حلقة واحدة على البيانات.يؤذي لكبير جدا ن.

يا (ن * سجل (ن)):خوارزمية تقوم بنوع من استراتيجية فرق تسد.يؤذي لكبير ن.مثال نموذجي:دمج النوع

يا (ن * ن):حلقة متداخلة من نوع ما.يؤلم حتى مع ن صغير.شائع مع حسابات المصفوفات الساذجة.تريد تجنب هذا النوع من الخوارزمية إذا استطعت.

O(ن^x لـ x>2):بناء شرير مع حلقات متداخلة متعددة.يؤلم لصغيرة جدا.

يا (س ^ ن، ن!والأسوأ):خوارزميات فظيعة (وغالبًا ما تكون متكررة) لا ترغب في وجودها في كود الإنتاج إلا في الحالات التي يتم التحكم فيها للغاية، ولعدد صغير جدًا من n، وإذا لم يكن هناك بديل أفضل بالفعل.قد ينفجر وقت الحساب مع n=n+1.

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

مثال بسيط:يكتب مبرمجو لغة C الساذجون هذا النوع من الحلقات:

for (int cnt=0; cnt < strlen(s) ; cnt++) {
  /* some code */
}

هذه خوارزمية O(n*n) بسبب تطبيق strlen().تؤدي حلقات التداخل إلى مضاعفة التعقيدات داخل الجزء الكبير O.O(n) داخل O(n) يعطي O(n*n).O(n^3) داخل O(n) يعطي O(n^4).في المثال، سيؤدي الحساب المسبق لطول السلسلة إلى تحويل الحلقة على الفور إلى O(n). وقد كتب جويل أيضا عن هذا.

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

Answer 2

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

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

SELECT User.*, COUNT(Order.*) OrderCount FROM User Join Order ON User.UserId = Order.UserId

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

CREATE INDEX ORDER_USERID ON Order(UserId)

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

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

Answer 3

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

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

Answer 4

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

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

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

Answer 5

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

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

Answer 6

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

أتساءل ما إذا كان هذا أحد الأسئلة التي لا يمكن إلا أن تحصل على إجابات بـ "نعم"؟يذهلني أن مجموعة الأشخاص الذين يفهمون التعقيد الحسابي تعادل تقريبًا مجموعة الأشخاص الذين يعتقدون أنه مهم.لذا، فإن أي شخص قد يجيب بـ لا ربما لا يفهم السؤال، وبالتالي سينتقل إلى السؤال التالي بدلاً من التوقف للرد.مجرد فكرة ؛-)

Answer 7

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

الأمثلة هي:

• تطبيق الخرائط...مثل خرائط Google - كيف يمكنك معالجة بيانات خطوط الطرق في جميع أنحاء العالم ورسمها؟وتحتاج إلى رسمها بسرعة!
• تطبيق لوجستي...أعتقد أن رجل المبيعات المتجول يتعاطى المنشطات
• بيانات التعدين...تتطلب جميع المؤسسات الكبرى واحدًا، كيف يمكنك استخراج قاعدة بيانات تحتوي على 100 جدول و10 ملايين صف والتوصل إلى نتائج مفيدة قبل أن تصبح الاتجاهات قديمة؟

سيساعدك الحصول على دورة تدريبية في التعقيد الحسابي في تحليل واختيار/إنشاء الخوارزميات الفعالة لمثل هذه السيناريوهات.

صدقني، شيء بسيط مثل تقليل المعامل، مثلًا من T(3n) إلى T(2n) يمكن أن يحدث اختلافات كبيرة عندما يتم قياس "n" بالأيام إن لم يكن بالأشهر.

Answer 8

هناك الكثير من النصائح الجيدة هنا، وأنا متأكد من أن معظم المبرمجين استخدموا معرفتهم المعقدة من حين لآخر.

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

أراهن أن عددًا قليلاً جدًا من المحترفين ربما يهتمون بـ Big-O بقدر اهتمام مبرمجي الألعاب.

Answer 9

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

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

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

Answer 10

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

Answer 11

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

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

Answer 12

'نعم' و 'لا'

نعم) كثيرا ما أستخدمها تدوين O كبير عند تطوير وتنفيذ الخوارزميات.على سبيل المثالعندما يتعين عليك التعامل مع 10 ^ 3 عناصر وتعقيد الخوارزمية الأولى هو O(n log(n)) والثانية O(n^3)، يمكنك ببساطة القول أن الخوارزمية الأولى هي في الوقت الفعلي تقريبًا بينما تتطلب الثانية حسابات كبيرة.

في بعض الأحيان المعرفة حول فئات التعقيد NP يمكن أن تكون مفيدة.يمكن أن يساعدك ذلك على إدراك أنه يمكنك التوقف عن التفكير في اختراع خوارزمية فعالة عندما يمكن اختزال بعض مشكلات NP الكاملة إلى المشكلة التي تفكر فيها.

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

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

Answer 13

@ مارتن:هل يمكنك توضيح عمليات التفكير وراء ذلك؟

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

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

Answer 14

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