מהי הסבר על Big O Notation: מורכבות המרחב והזמן

אתה באמת מבין את Big O? אם כן, זה ירענן את הבנתך לפני ראיון. אם לא, אל דאגה - בואו והצטרפו אלינו לכמה עשייה במדעי המחשב.

אם עברת קורסים הקשורים לאלגוריתם, בטח שמעת על המונח Big O notation . אם לא עשית זאת, נעבור על זה כאן ואז נבין יותר מה זה באמת.

סימון Big O הוא אחד הכלים הבסיסיים ביותר עבור מדעני המחשב לניתוח עלות האלגוריתם. זה נוהג טוב גם למהנדסי תוכנה להבין לעומק.

מאמר זה נכתב מתוך הנחה שכבר התמודדת עם קוד כלשהו. כמו כן, חלק מחומרים מעמיקים דורשים גם יסודות במתמטיקה בתיכון, ולכן יכולים להיות מעט פחות נוחים למתחילים בסך הכל. אבל אם אתה מוכן, בוא נתחיל!

במאמר זה נקיים דיון מעמיק על סימון Big O. נתחיל מאלגוריתם לדוגמא כדי לפתוח את ההבנה שלנו. לאחר מכן, ניכנס מעט למתמטיקה כדי לקבל הבנה פורמלית. לאחר מכן נעבור על כמה וריאציות נפוצות של סימון Big O. בסופו של דבר נדון בכמה מהמגבלות של Big O בתרחיש מעשי. תוכן עניינים ניתן למצוא למטה.

תוכן עניינים

מהי סימון ביג או, ולמה זה חשוב
הגדרה רשמית של סימון ביג או
ביג או, ליטל או, אומגה ותטא
מורכבות השוואה בין אופציות גדולות אופייניות
מורכבות זמן ומרחב
המורכבות הטובה ביותר, הממוצעת, הגרועה ביותר
למה ביג או לא משנה
בסוף…

אז בואו נתחיל.

1. מהי Big O Notation ולמה זה חשוב

"סימון O גדול הוא סימון מתמטי המתאר את ההתנהגות המגבילה של פונקציה כאשר הטיעון נוטה לערך או אינסוף מסוימים. הוא בן למשפחת סימונים שהומצאו על ידי פול בכמן, אדמונד לנדאו ואחרים, הנקראים באופן קולקטיבי סימון בכמן – לנדאו או סימון אסימפטוטי. "- הגדרת ויקיפדיה לסימון ביג או

במילים פשוטות, סימון Big O מתאר את מורכבות הקוד שלך באמצעות מונחים אלגבריים.

כדי להבין מהי סימון Big O, אנו יכולים להסתכל על דוגמא טיפוסית, O (n²) , שבדרך כלל מבטאים אותה "Big O בריבוע" . האות "n" מייצגת כאן את גודל הקלט , והפונקציה "g (n) = n²" בתוך ה- "O ()" נותנת לנו מושג עד כמה האלגוריתם מורכב ביחס לגודל הקלט.

אלגוריתם טיפוסי בעל מורכבות O (n²) יהיה האלגוריתם של מיון הבחירה . בחירת סוג היא אלגוריתם מיון כי סובב בין הרשימה כדי להבטיח כל אלמנט בבית המדד i הוא ה- i הקטן / האלמנט הגדול של הרשימה. ה- CODEPEN שלהלן נותן דוגמה ויזואלית לכך.

ניתן לתאר את האלגוריתם באמצעות הקוד הבא. על מנת לוודא את ה- i האלמנט הוא ה- i היסוד הקטן ביותר ברשימה, האלגוריתם הזה סובב הראשונה דרך הרשימה עם לולאת 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) } }

בתרחיש זה אנו רואים את המשתנה List כקלט, ולכן גודל הקלט n הוא מספר האלמנטים בתוך List . נניח כי הצהרת ה- if, והקצאת הערך שתוחמת על ידי הצהרת ה- if, אורכת זמן קבוע. אז נוכל למצוא את סימון ה- O הגדול עבור הפונקציה SelectionSort על ידי ניתוח כמה פעמים ההצהרות מבוצעות.

ראשית, הלולאה הפנימית מריצה את ההצהרות בתוך n פעמים. ואז, לאחר תוספת ה- i , הלולאה הפנימית פועלת במשך n-1 פעמים ... ... עד שהיא פועלת פעם אחת, אז שתי הלולאות מגיעות לתנאי הסיום שלהן.

זה בעצם בסופו של דבר נותן לנו סכום גיאומטרי, ועם מתמטיקה כלשהי בתיכון נגלה שהלולאה הפנימית תחזור על עצמה 1 + 2 ... + n פעמים, ששווה ל- n (n-1) / 2 פעמים. אם נכפיל את זה, בסופו של דבר נקבל n² / 2-n / 2.

כאשר אנו מחשבים סימון O גדול, אכפת לנו רק מהמונחים הדומיננטיים , ולא אכפת לנו מהמקדמים. לפיכך אנו לוקחים את ה- N² כ- O הגדול האחרון שלנו. אנו כותבים אותו כ- O (N²), מה שמבטא שוב "Big O בריבוע" .

עכשיו אתם אולי תוהים, במה מדובר "מונח דומיננטי" זה ? ולמה לא אכפת לנו מהמקדמים? אל דאגה, נעבור עליהם אחד אחד. זה יכול להיות קצת קשה להבין בהתחלה, אבל כל זה יהיה הרבה יותר הגיוני כשאתה קורא את החלק הבא.

2. הגדרה רשמית של סימון ביג או

פעם היה מלך הודי שרצה לתגמל חכם על הצטיינותו. האיש החכם לא ביקש דבר מלבד חיטה שתמלא לוח שחמט.

אבל הנה הכללים שלו: באריח הראשון הוא רוצה גרגיר אחד של חיטה, ואז 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, אנו רוצים לדעת את הגבול הדוק של הפונקציה. תוכלו להבין זאת יותר כשתקראו את החלק הבא.

אך לפני שנלך, בואו לבדוק את הבנתכם בשאלה הבאה. התשובה תימצא בסעיפים מאוחרים יותר כך שהיא לא תהיה זריקה משם.

שאלה: תמונה מיוצגת על ידי מערך דו-ממדי של פיקסלים. אם אתה משתמש בלולאה מקוננת כדי לחזור על כל פיקסל (כלומר, יש לך לולאה עבור שעוברת בין כל העמודות, ואז עוד לולאה בפנים שתעבור את כל השורות), מה מורכבות הזמן של האלגוריתם כאשר תמונה נחשבת כקלט?

3. Big O, Little O, Omega & Theta

Big O: "f (n) הוא O (g (n))" עבור קבועים מסוימים 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) הוא is (g (n)) "iff f (n) הוא O (g (n)) ו- f (n) הוא Ω (g (n)) O קטן: "f (n) הוא o (g (n))" אם 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²) מכיוון שיש לולאה מקוננת. עם זאת, 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 לבחור 2" לפולינום כאשר מונח מעוקב הוא הגדול ביותר.

ולבסוף, אנו יכולים לדרג את הפונקציות מה מורכבות ביותר לפחות מורכבות.

למה BigO לא משנה

!!! - אזהרה - !!! התכנים הנדונים כאן בדרך כלל אינם מקובלים על ידי רוב המתכנתים בעולם. שוחח על זה על אחריותך בלבד בראיון. אנשים באמת כתבו בבלוג על האופן שבו נכשלו בראיונות שלהם בגוגל בגלל שהם הטילו ספק בסמכות, כמו כאן. !!! - אזהרה - !!!

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…

I like coding, learning new things and sharing them with the community. If there is anything in which you are particularly interested, please let me know. I generally write on web design, software architecture, mathematics and data science. You can find some great articles I have written before if you are interested in any of the topics above.

Hope you have a great time learning computer science!!!