الخوارزميات في اللغة الإنجليزية البسيطة: تعقيد الوقت وتدوين Big-O

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

قبل أن تتمكن من فهم تعقيد الوقت في البرمجة ، عليك أن تفهم أين يتم تطبيقها بشكل شائع: في تصميم الخوارزميات .

إذن ما هي الخوارزمية على أي حال؟

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

function BakeCake(flavor, icing){ " 1. Heat Oven to 350 F 2. Mix flour, baking powder, salt 3. Beat butter and sugar until fluffy 4. Add eggs. 5. Mix in flour, baking powder, salt 6. Add milk and " + flavor + " 7. Mix further 8. Put in pan 9. Bake for 30 minutes 10." + if(icing === true) return 'add icing' + " 10. Stuff your face " } BakeCake('vanilla', true) => deliciousness

تعد الخوارزميات مفيدة في فحصنا لتعقيد الوقت لأنها تأتي في جميع الأشكال والأحجام.

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

لذا فإن السؤال الرئيسي هو: كيف نبدأ في تحليل الحلول الأكثر كفاءة؟

الرياضيات للإنقاذ! يعد تحليل تعقيد الوقت في البرمجة مجرد طريقة رياضية مبسطة للغاية لتحليل المدة التي ستستغرقها خوارزمية بعدد معين من المدخلات (n) لإكمال مهمتها. يتم تعريفه عادةً باستخدام تدوين Big-O .

ما هو تدوين Big O ، تسأل؟

إذا وعدت أنك لن تستسلم وتتوقف عن القراءة ، فسوف أخبرك بذلك.

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

من المحتمل أن يتراجع علماء الرياضيات قليلاً عن افتراض "التأثير الكلي" الخاص بي هناك ، ولكن بالنسبة للمطورين لتوفير الوقت ، فمن الأسهل تبسيط الأمور بهذه الطريقة:

Regular Big-O 2 O(1) --> It's just a constant number 2n + 10 O(n) --> n has the largest effect 5n^2 O(n^2) --> n^2 has the largest effect

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

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

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

مع وجود هذه المعرفة في متناول اليد ، دعنا نرى عدد الخطوات التي تنطوي عليها كل من هذه التعقيدات الزمنية:

let n = 16; O (1) = 1 step "(awesome!)" O (log n) = 4 steps "(awesome!)" -- assumed base 2 O (n) = 16 steps "(pretty good!)" O(n^2) = 256 steps "(uhh..we can work with this?)" O(2^n) = 65,536 steps "(...)"

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

إذًا ، كيف يمكننا تحليل الكود الخاص بنا باستخدام تدوين Big-O؟

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

سنستخدم هياكل البيانات أدناه للحصول على أمثلة لدينا:

var friends = { 'Mark' : true, 'Amy' : true, 'Carl' : false, 'Ray' : true, 'Laura' : false, } var sortedAges = [22, 24, 27, 29, 31]

O (1) - الوقت الثابت

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

//If I know the persons name, I only have to take one step to check: function isFriend(name){ //similar to knowing the index in an Array return friends[name]; }; isFriend('Mark') // returns True and only took one step function add(num1,num2){ // I have two numbers, takes one step to return the value return num1 + num2 }

O (تسجيل الدخول) - الوقت اللوغاريتمي

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

//You decrease the amount of work you have to do with each step function thisOld(num, array){ var midPoint = Math.floor( array.length /2 ); if( array[midPoint] === num) return true; if( array[midPoint]  only look at second half of the array if( array[midpoint] > num ) --> only look at first half of the array //recursively repeat until you arrive at your solution } thisOld(29, sortedAges) // returns true //Notes //There are a bunch of other checks that should go into this example for it to be truly functional, but not necessary for this explanation. //This solution works because our Array is sorted //Recursive solutions are often logarithmic //We'll get into recursion in another post!

O (n) - الوقت الخطي

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

//The number of steps you take is directly correlated to the your input size function addAges(array){ var sum = 0; for (let i=0 ; i < array.length; i++){ //has to go through each value sum += array[i] } return sum; } addAges(sortedAges) //133

O (n²) - الوقت التربيعي

حلقات for المتداخلة هي وقت تربيعي ، لأنك تقوم بتشغيل عملية خطية ضمن عملية خطية أخرى (أو n * n = n²).

//The number of steps you take is your input size squared function addedAges(array){ var addedAge = []; for (let i=0 ; i < array.length; i++){ //has to go through each value for(let j=i+1 ; j < array.length ; j++){ //and go through them again addedAge.push(array[i] + array[j]); } } return addedAge; } addedAges(sortedAges); //[ 46, 49, 51, 53, 51, 53, 55, 56, 58, 60 ] //Notes //Nested for loops. If one for loop is linear time (n) //Then two nested for loops are (n * n) or (n^2) Quadratic!

O (2 ^ n) - الوقت الأسي

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

//The number of steps it takes to accomplish a task is a constant to the n power //Thought example //Trying to find every combination of letters for a password of length n

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

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

لمساعدتك في عملية حل المشكلات ، إليك بعض الأسئلة البسيطة التي يجب طرحها:

1. هل هذا يحل المشكلة؟ نعم =>

2. هل لديك الوقت للعمل على هذا

نعم => انتقل إلى الخطوة 3

لا => عد إليها لاحقًا وانتقل إلى الخطوة 6 في الوقت الحالي.

3. هل يغطي جميع حالات الحافة؟ نعم =>

4. هل تعقيداتي منخفضة قدر الإمكان؟

لا => إعادة الكتابة أو التعديل في حل جديد -> ارجع إلى الخطوة 1

نعم => انتقل إلى الخطوة 5

5. هل الكود الخاص بي جاف؟ نعم =>

6. افرحوا!

No => Make it D.R.Y, then rejoice!

Analyze time complexity any and all times you are trying to solve a problem. It’ll make you a better developer in the log run. Your teammates and users will love you for it.

Again, most problems you will face as programmer — whether algorithmic or programmatic — will have tens if not hundreds of ways of solving it. They may vary in how they solve the problem, but they all still solve that problem.

You could be making decisions between whether to use sets or graphs to store data. You could be deciding whether or not to use Angular, React, or Backbone for a team project. All of these solutions solve the same problem in a different way.

Given this, it’s hard to say there is a single “right” or “best” answer to these problems. But it is possible to say there are “better” or “worse” answers to a given problem.

Using one of our previous examples, it might be better to use React for a team project if half your team has experience with it, so it’ll take less time to get up and running.

The ability to describe a better solution usually springs from some semblance of time complexity analysis.

In short, if you’re going to solve a problem, solve it well. And use some Big-O to help you figure out how.

Here’s a final recap:

  • O(1) — Constant Time: it only takes a single step for the algorithm to accomplish the task.
  • O(log n) — Logarithmic Time: The number of steps it takes to accomplish a task are decreased by some factor with each step.
  • O (n) - الوقت الخطي: يرتبط عدد الخطوات المطلوبة ارتباطًا مباشرًا (من 1 إلى 1).
  • O (n²) - الوقت التربيعي: عدد الخطوات اللازمة لإنجاز مهمة ما هو مربع n.
  • O (C ^ n) - أسي: عدد الخطوات اللازمة لإنجاز مهمة هو ثابت للقوة n (عدد كبير جدًا).

وإليك بعض الموارد المفيدة لمعرفة المزيد:

  • ويكيبيديا
  • ورقة الغش Big O هي مورد رائع مع تعقيدات زمنية خوارزمية شائعة وتمثيل رسومي. تحقق من ذلك!