מדריך למתחילים לסימון Big O

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

להלן מספר סוגים נפוצים של מורכבות זמן ב- Big O Notation.

• O (1) - מורכבות זמן קבועה
• O (n) - מורכבות זמן ליניארית
• O (log n) - מורכבות זמן לוגריתמית
• O (n ^ 2) - מורכבות זמן ריבועית

אני מקווה שבסוף המאמר הזה תוכלו להבין את היסודות של Big O Notation.

O (1) - זמן קבוע

לאלגוריתמים של זמן קבוע תמיד ייקח אותו זמן לביצוע. זמן הביצוע של אלגוריתם זה אינו תלוי בגודל הקלט. דוגמה טובה לזמן O (1) היא גישה לערך עם אינדקס מערך.

var arr = [ 1,2,3,4,5];

arr[2]; // => 3

דוגמאות אחרות כוללות: פעולות דחיפה () ופופ () במערך.

O (n) - מורכבות זמן ליניארית

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

דוגמה טובה היא למצוא תקליטור בערימה של תקליטורים או לקרוא ספר, כאשר n הוא מספר העמודים.

דוגמאות ב- O (n) הוא שימוש בחיפוש לינארי:

//if we used for loop to print out the values of the arrays

for (var i = 0; i < array.length; i++) { console.log(array[i]);}

var arr1 = [orange, apple, banana, lemon]; //=> 4 steps

var arr2 = [apple, htc,samsung, sony, motorola]; //=> 5 steps

O (log n) - מורכבות זמן לוגריתמית

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

//Binary search implementationvar doSearch = function(array, targetValue) { var minIndex = 0; var maxIndex = array.length - 1; var currentIndex; var currentElement; while (minIndex <= maxIndex) { currentIndex = (minIndex + maxIndex) / 2 | 0; currentElement = array[currentIndex]; if (currentElement  targetValue) { maxIndex = currentIndex - 1; } else { return currentIndex; } } return -1; //If the index of the element is not found.};

var numbers = [11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33];

doSearch(numbers, 23) //=>; 6

דוגמאות נוספות למורכבות הזמן הלוגריתמית כוללות:

Example 1;

for (var i = 1; i < n; i = i * 2) console.log(i);}

Example 2;

for (i = n; i >= 1; i = i/2) console.log(i);}

O (n ^ 2) - מורכבות זמן ריבועית

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

תיתקל במורכבות זמן ריבועית באלגוריתמים הכוללים איטרציות מקוננות, כגון מקוננות לולאות. למעשה, הלולאות המקוננות העמוקות יותר יביאו ל- O (n ^ 3), O (n ^ 4) וכו '.

for(var i = 0; i < length; i++) { //has O(n) time complexity for(var j = 0; j < length; j++) { //has O(n^2) time complexity // More loops? }}

דוגמאות נוספות למורכבות זמן ריבועית כוללות מיון בועות, מיון בחירה ומיון הכנסה.

מאמר זה רק מגרד את פני השטח של Big O Notation. אם ברצונך להבין יותר אודות Big O Notation, אני ממליץ לבדוק את גיליון ה- Cheat של Big-O.