شرح ما هو تدوين Big O: تعقيد المكان والزمان

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

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

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

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

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

جدول المحتويات

  1. ما هو تدوين Big O ولماذا هو مهم
  2. التعريف الرسمي لتدوين Big O
  3. Big O و Little O و Omega و Theta
  4. مقارنة التعقيد بين نظام التشغيل الكبير النموذجي
  5. تعقيد الزمان والمكان
  6. التعقيد الأفضل ، والمتوسط ​​، والأسوأ ، والمتوقع
  7. لماذا لا يهم Big O
  8. فى النهاية…

اذا هيا بنا نبدأ.

1. ما هو تدوين Big O ولماذا هو مهم

تدوين Big O هو تدوين رياضي يصف السلوك المحدود لوظيفة ما عندما تميل الحجة نحو قيمة معينة أو ما لا نهاية. إنه عضو في عائلة من الرموز التي اخترعها بول باخمان وإدموند لانداو وآخرين ، يُطلق عليهم مجتمعين تدوين باخمان-لانداو أو تدوين مقارب ". - تعريف ويكيبيديا لتدوين Big O

بكلمات واضحة ، يصف تدوين Big O مدى تعقيد الكود الخاص بك باستخدام المصطلحات الجبرية.

لفهم ماهية تدوين Big O ، يمكننا إلقاء نظرة على مثال نموذجي ، O (n²) ، والذي يُنطق عادةً "Big O squared" . يمثل الحرف "n" هنا حجم الإدخال ، وتعطينا الوظيفة "g (n) = n²" داخل "O ()" فكرة عن مدى تعقيد الخوارزمية فيما يتعلق بحجم الإدخال.

ستكون الخوارزمية النموذجية التي تحتوي على تعقيد O (n²) هي خوارزمية فرز التحديد . اختيار نوع هو خوارزمية الفرز التي تتكرر من خلال القائمة لضمان كل عنصر في الفهرس ط هو إيث أصغر / أكبر عنصر من عناصر القائمة. و CODEPEN يعطي أدناه مثال المرئي منه.

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

SelectionSort(List) { for(i from 0 to List.Length) { SmallestElement = List[i] for(j from i to List.Length) { if(SmallestElement > List[j]) { SmallestElement = List[j] } } Swap(List[i], SmallestElement) } }

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

أولاً ، تقوم حلقة for الداخلية بتشغيل البيانات داخل n مرة. ثم بعد زيادة i ، تعمل حلقة for الداخلية لـ n-1 مرة… ... حتى يتم تشغيلها مرة واحدة ، ثم تصل كلتا الحلقتين for إلى شروط الإنهاء.

ينتهي هذا الأمر في الواقع بإعطائنا مجموعًا هندسيًا ، ومع بعض رياضيات المدرسة الثانوية سنجد أن الحلقة الداخلية ستتكرر لمدة 1 + 2 ... + n مرة ، والتي تساوي n (n-1) / 2 مرة. إذا ضربنا هذا ، فسنحصل في النهاية على n² / 2-n / 2.

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

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

2. التعريف الرسمي لتدوين Big O

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

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

فكم حبة قمح يدين الملك للحكيم؟ نعلم أن رقعة الشطرنج بها 8 مربعات في 8 مربعات ، أي ما مجموعه 64 بلاطة ، لذلك يجب أن يحتوي البلاط النهائي على 2⁶⁴ حبات من القمح. إذا أجريت عملية حسابية عبر الإنترنت ، فسينتهي بك الأمر بالحصول على 1.8446744 * 10¹⁹ ، أي حوالي 18 متبوعًا بـ 18 صفرًا. بافتراض أن كل حبة قمح تزن 0.01 جرام فهذا يعطينا 184.467.440.737 طن قمح. و 184 مليار طن كثير ، أليس كذلك؟

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

الآن مربع 64 هو 4096. إذا أضفت هذا الرقم إلى 2⁶⁴ ، فسيتم فقده خارج الأرقام المهمة. لهذا السبب ، عندما ننظر إلى معدل النمو ، فإننا نهتم فقط بالشروط السائدة. ونظرًا لأننا نريد تحليل النمو فيما يتعلق بحجم الإدخال ، فإن المعاملات التي تضاعف الرقم فقط بدلاً من الزيادة مع حجم الإدخال لا تحتوي على معلومات مفيدة.

فيما يلي التعريف الرسمي لـ Big O:

يكون التعريف الرسمي مفيدًا عندما تحتاج إلى إجراء إثبات رياضي. على سبيل المثال ، يمكن تحديد التعقيد الزمني لفرز التحديد من خلال الوظيفة f (n) = n² / 2-n / 2 كما ناقشنا في القسم السابق.

إذا سمحنا لوظيفة g (n) أن تكون n² ، فيمكننا إيجاد ثابت c = 1 ، و N₀ = 0 ، وطالما أن N> N₀ ، N² ستكون دائمًا أكبر من N² / 2-N / 2. يمكننا إثبات ذلك بسهولة بطرح N² / 2 من كلتا الوظيفتين ، ثم يمكننا بسهولة رؤية N² / 2> -N / 2 لتكون صحيحة عندما تكون N> 0. لذلك ، يمكننا التوصل إلى استنتاج مفاده أن f (n) = O (n²) ، في نوع التحديد الآخر يكون الفرز "كبير O تربيع".

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

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

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

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

3. Big O، Little O، Omega & Theta

Big O: "f (n) هو O (g (n))" iff لبعض الثوابت c و N₀ و f (N) ≤ cg (N) لجميع N> N₀Omega: "f (n) هي Ω (g ( n)) "iff لبعض الثوابت c و N₀ ، f (N) ≥ cg (N) لجميع N> N₀Theta:" f (n) هي Θ (g (n)) "iff f (n) هي O (g (n)) و f (n) هي Ω (g (n)) Little O: "f (n) هي o (g (n))" iff f (n) هي O (g (n)) و f ( n) ليس Θ (g (n)) - تعريف رسمي لـ Big O و Omega و Theta و Little O

بكلمات واضحة:

  • Big O (O()) describes the upper bound of the complexity.
  • Omega (Ω()) describes the lower bound of the complexity.
  • Theta (Θ()) describes the exact bound of the complexity.
  • Little O (o()) describes the upper bound excluding the exact bound.

For example, the function g(n) = n² + 3n is O(n³), o(n⁴), Θ(n²) and Ω(n). But you would still be right if you say it is Ω(n²) or O(n²).

Generally, when we talk about Big O, what we actually meant is Theta. It is kind of meaningless when you give an upper bound that is way larger than the scope of the analysis. This would be similar to solving inequalities by putting ∞ on the larger side, which will almost always make you right.

But how do we determine which functions are more complex than others? In the next section you will be reading, we will learn that in detail.

4. Complexity Comparison Between Typical Big Os

When we are trying to figure out the Big O for a particular function g(n), we only care about the dominant term of the function. The dominant term is the term that grows the fastest.

For example, n² grows faster than n, so if we have something like g(n) = n² + 5n + 6, it will be big O(n²). If you have taken some calculus before, this is very similar to the shortcut of finding limits for fractional polynomials, where you only care about the dominant term for numerators and denominators in the end.

But which function grows faster than the others? There are actually quite a few rules.

1. O(1) has the least complexity

Often called “constant time”, if you can create an algorithm to solve the problem in O(1), you are probably at your best. In some scenarios, the complexity may go beyond O(1), then we can analyze them by finding its O(1/g(n)) counterpart. For example, O(1/n) is more complex than O(1/n²).

2. O(log(n)) is more complex than O(1), but less complex than polynomials

As complexity is often related to divide and conquer algorithms, O(log(n)) is generally a good complexity you can reach for sorting algorithms. O(log(n)) is less complex than O(√n), because the square root function can be considered a polynomial, where the exponent is 0.5.

3. Complexity of polynomials increases as the exponent increases

For example, O(n⁵) is more complex than O(n⁴). Due to the simplicity of it, we actually went over quite many examples of polynomials in the previous sections.

4. Exponentials have greater complexity than polynomials as long as the coefficients are positive multiples of n

O(2ⁿ) is more complex than O(n⁹⁹), but O(2ⁿ) is actually less complex than O(1). We generally take 2 as base for exponentials and logarithms because things tends to be binary in Computer Science, but exponents can be changed by changing the coefficients. If not specified, the base for logarithms is assumed to be 2.

5. Factorials have greater complexity than exponentials

If you are interested in the reasoning, look up the Gamma function, it is an analytic continuation of a factorial. A short proof is that both factorials and exponentials have the same number of multiplications, but the numbers that get multiplied grow for factorials, while remaining constant for exponentials.

6. Multiplying terms

When multiplying, the complexity will be greater than the original, but no more than the equivalence of multiplying something that is more complex. For example, O(n * log(n)) is more complex than O(n) but less complex than O(n²), because O(n²) = O(n * n) and n is more complex than log(n).

To test your understanding, try ranking the following functions from the most complex to the lease complex. The solutions with detailed explanations can be found in a later section as you read. Some of them are meant to be tricky and may require some deeper understanding of math. As you get to the solution, you will understand them more.

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

5. تعقيد الزمان والمكان

So far, we have only been discussing the time complexity of the algorithms. That is, we only care about how much time it takes for the program to complete the task. What also matters is the space the program takes to complete the task. The space complexity is related to how much memory the program will use, and therefore is also an important factor to analyze.

The space complexity works similarly to time complexity. For example, selection sort has a space complexity of O(1), because it only stores one minimum value and its index for comparison, the maximum space used does not increase with the input size.

Some algorithms, such as bucket sort, have a space complexity of O(n), but are able to chop down the time complexity to O(1). Bucket sort sorts the array by creating a sorted list of all the possible elements in the array, then increments the count whenever the element is encountered. In the end the sorted array will be the sorted list elements repeated by their counts.

6. Best, Average, Worst, Expected Complexity

The complexity can also be analyzed as best case, worst case, average case and expected case.

Let’s take insertion sort, for example. Insertion sort iterates through all the elements in the list. If the element is larger than its previous element, it inserts the element backwards until it is larger than the previous element.

If the array is initially sorted, no swap will be made. The algorithm will just iterate through the array once, which results a time complexity of O(n). Therefore, we would say that the best-case time complexity of insertion sort is O(n). A complexity of O(n) is also often called linear complexity.

Sometimes an algorithm just has bad luck. Quick sort, for example, will have to go through the list in O(n) time if the elements are sorted in the opposite order, but on average it sorts the array in O(n * log(n)) time. Generally, when we evaluate time complexity of an algorithm, we look at their worst-case performance. More on that and quick sort will be discussed in the next section as you read.

The average case complexity describes the expected performance of the algorithm. Sometimes involves calculating the probability of each scenarios. It can get complicated to go into the details and therefore not discussed in this article. Below is a cheat-sheet on the time and space complexity of typical algorithms.

Solution to Section 4 Question:

By inspecting the functions, we should be able to immediately rank the following polynomials from most complex to lease complex with rule 3. Where the square root of n is just n to the power of 0.5.

Then by applying rules 2 and 6, we will get the following. Base 3 log can be converted to base 2 with log base conversions. Base 3 log still grows a little bit slower then base 2 logs, and therefore gets ranked after.

The rest may look a little bit tricky, but let’s try to unveil their true faces and see where we can put them.

First of all, 2 to the power of 2 to the power of n is greater than 2 to the power of n, and the +1 spices it up even more.

And then since we know 2 to the power of log(n) with based 2 is equal to n, we can convert the following. The log with 0.001 as exponent grows a little bit more than constants, but less than almost anything else.

The one with n to the power of log(log(n)) is actually a variation of the quasi-polynomial, which is greater than polynomial but less than exponential. Since log(n) grows slower than n, the complexity of it is a bit less. The one with the inverse log converges to constant, as 1/log(n) diverges to infinity.

يمكن تمثيل العوامل من خلال عمليات الضرب ، وبالتالي يمكن تحويلها إلى إضافات خارج الدالة اللوغاريتمية. يمكن تحويل "n Choose 2" إلى كثير حدود مع كون المصطلح التكعيبي هو الأكبر.

وأخيرًا ، يمكننا ترتيب الدوال من الأكثر تعقيدًا إلى الأقل تعقيدًا.

لماذا لا يهم BigO

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

Since we have previously learned that the worst case time complexity for quick sort is O(n²), but O(n * log(n)) for merge sort, merge sort should be faster — right? Well you probably have guessed that the answer is false. The algorithms are just wired up in a way that makes quick sort the “quick sort”.

To demonstrate, check out this trinket.io I made. It compares the time for quick sort and merge sort. I have only managed to test it on arrays with a length up to 10000, but as you can see so far, the time for merge sort grows faster than quick sort. Despite quick sort having a worse case complexity of O(n²), the likelihood of that is really low. When it comes to the increase in speed quick sort has over merge sort bounded by the O(n * log(n)) complexity, quick sort ends up with a better performance in average.

I have also made the below graph to compare the ratio between the time they take, as it is hard to see them at lower values. And as you can see, the percentage time taken for quick sort is in a descending order.

The moral of the story is, Big O notation is only a mathematical analysis to provide a reference on the resources consumed by the algorithm. Practically, the results may be different. But it is generally a good practice trying to chop down the complexity of our algorithms, until we run into a case where we know what we are doing.

In the end…

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

آمل أن تقضي وقتًا ممتعًا في تعلم علوم الكمبيوتر !!!