מכירים את זה שאתם פותרים בעיה אלגוריתמית כלשהי ב LeetCode מנתחים את הזמן הסיבוכיות וזורקים
לאוויר ישר את הביטוי ( )O האות ״או גדול״ באנגלית של משהו ? כמו (2^N(O) N(O .
הקדמה:
כאשר מנתחים סיבוכיות זמן לצורך הנושא, מתעוררת בעיה, איך לנתח זמן של אלגוריתם ? הרי אם ננתח זמן של אלגוריתם ע״י זמן שעון ונשים אותו בשני מחשבים שונים מחשב a ו b כאשר מחשב a הוא טוב מבחינת נתונים ממחשב b אזי אין ספק שהאלגוריתם שלי ירוץ מהר יותר במחשב a. לפיכך אנו מנתחים זמן ריצה
של אלגוריתם ע״י פונקציות ולא ע״י זמן שעון כדי לקבל אספקט על האלגוריתם שלי שנקי משיקול של נתוני מחשב.
כעת אם נשיב לב לדוגמא הכי פשוטה לניתוח של אלגוריתם נניח לולאת for שעושה פרינט למסך הרי זמן הריצה שלה הוא N במדויק (בהנחה ש לולאת ה for רצה על כל הקלט שקיבלתי). אז איפה נכנס ה “O של“ לתמונה בכלל ?, מה זה ה O גדול? ואיזה אפשרויות יש לנו בכלל ?
אז אם נחזור לשיעורי המתמטיקה נזכור את החסמים הקיימים:
- או קטנה o חסם עליון לא הדוק
- או גדולה O חסם עליון הדוק
- אומגה גדולה Ω חסם תחתון הדוק
- אומגה קטנה ω חסם תחתון לא הדוק
- טתא ϴ( חסם תחתון הדוק + חסם עליון הדוק)
אני כרגע לא רוצה להתמקד בחסמים האחרים, אלה רק להתמקד בחסם O גדול שעליו נדבר בהסבר.
אז אם ניתן הגדרה מדויקת מהו בדיוק:
הגדרה פורמלית לחסם עליון הדוק : תהיינה (n(g ו (n(t שתי פונקציות חיוביות אסימפטומטית
אזי ((n(g(O)=n(t אם קיימים חיובים 0N ו C כך שהתקיים:
אז בואו ניקח דוגמה: נניח עשיתי אלגוריתם כלשהו וראיתי שזמן הפעולות המדויק שלו הוא:
כלומר במקרה הזה אני רוצה להוכיח כי :
נניח כי:
אז עבור 1=n0 כלומר האי שוויון לא מתקיים:
10*(2^1)+6 =16=> t(n)
15*(2^1)=15=> C*g(n)
אבל עבור 2=n0 כאן כבר אי השוויון מתקיים:
אבל שימו לב ל משפט
אני צריך שלכל נקודה מ 2=n0 ומעלה יתקיים השוויון גדול שווה וכך אני למעשה יחסום את t(n)
ע״י C כפול (n(g עבור n גדול דיים.
את שאר ההוכחה עבור 4=n3,=n וכו' .. אפשר להוכיח באינדוקציה או ישנם דרכים נוספות דבר שכרגע לא מעניין
אותי בהסבר (אבל תאמינו לי שזה נכון).
לבסוף אם נביט מה אנחנו משיגים כאן, נבחין כי ע״י שיטה זו אנחנו בונים ״באקטים״ (סדרי גודל) עליהם נכניס
את הפונקציות שלנו.
במקרה שלנו נכניס את (n(t לבאקט של אן בריבוע , אבל עדיין נשאלת השאלה למה זה טוב בכלל?
תשובה: פשטות..!!
ראשית: יהיה לי מאוד קשה לנתח כל אלגוריתם עד לרמת הקבועים , לא פשוט בכלל, (קשה מאוד).
שנית אם אני אתחיל לנתח אלגוריתם על כל קבוע או n- יות שקטנות יותר מ-הN עם הפולינום הגדול ביותר שנותן
לי ״את הקצב ״ של זמן הריצה שלי למשל:
עבור מספרים ענקיים הN יות ש קטנות בסדרי גודל מ אן בריבוע (במקרה המוצג לעיל) , לא יתרמו לי משהו
משמעותי מבחינת הגדילה של הפונקציה ולכן יהיו זניחות.
אז למה זה זניח?
תחשבו על מישהו שיש לו בבנק דסיליון טלפייים דולר.
Decillion: 1 , 000 , 000 , 000 , 000 , 000 , 000 , 000 , 000 , 000 , 000 , 000
1,000,000,000,000,000,000,000,000,000,000,000 (10^33)
• אם יוסיפו לו עוד 88 שקלים בבנק זה יעניין אותו? כנראה שלא? זה אנלוגיה לקבועים , זה לא מעניין
בכלל.
• אם יוסיפו לו עוד מיליון שקל ,אפילו מיליארד שקל זה יעניין אותו? כן, אבל לא בצורה דרמטית !!! כי זה
די כלום בשבילו.
וזה אנלוגיה ל n-יות הקטנות יותר, מכיוון ש הגידול שלהם עבור מספרים גדולים מאוד הוא פחות ב״סדר
גודל״ מ ה-N שהוא נותן ה״קצב״ או במקרה הזה הפולינום הכי גדול, אזי הם זניחים לפיכך אני אתחשב
רק ב אן עם הפולינום הגדול ביותר.
כעת אם ניקח למשל את אחד המיונים המפורסמים Sort Insertion
אם ממש נתעמק מה זמן הריצה המדויק של האלגוריתם נקבל (תחזיקו חזק):
כלומר נראה כאן המון n – יות כמו:
שתכלס לא מעניינות אותי .
כי מי שיקבע לי את ה״קצב״ זה בסוף כל החברה של אן בריבוע כמו:
שהם למעשה הפולינום הגבוה ביותר כאן..!!
מסקנה כל הביטוי כאן יהיה (2^N(O , וזה מה שמעניין אותי!!, סדר הגודל שלו.
ועכשיו הולך להגיע הבום העוד יותר גדול !
האם תמיד בהכרח עדיף בעולם האמיתי לבחור אלגוריתם שסדר הגודל שלו קטן יותר?
תשובה: לא תמיד!!
כעת נדבר על אלגוריתמים שבאופן תאורטי עם זמן סיבוכיות נמוך יותר אך בפועל רצים איטי יותר, וגם נסקור באיזה אלגורתמים משתמשים כיום ב ״עולם האמיתי״ .
אז הדוגמא הכי קלאסית שאני יכול לתת לכם הוא שני המיונים המפורסמים Quicksort ו mergesort
(אני מניח שאתם מכירים אותם לא אתחיל להסביר עליהם)
כמו שאתם בוודאי מכירים קוויקסורט נחשב במקרה הגרוע O(N^2) ו מרג׳סורט נחשב כ O(NLOGN) , עכשיו אני מניח כבר שקראתם שבמקרה הממוצע קוויקסורט משיג תוצאות של O(NLOGN) אבל האמת היא שאפילו יותר מזה , הוא משיג תוצאות במציאות הרבה יותר טובות ממרג׳ סורט כמעט תמיד.
אני אזכיר לכם שהמהירות של קוויקסורט מושפעת מה״שגרה״ שנקראת partition שבעצם בכל איטרציה מחלקת את המערך לשני חלקים חלק שגדול מ X וחלק שקטן מ X (כאשר X הוא מספר כלשהו שבחרתי במערך). וכאן טמון הסוד אם אני אצליח לחלק את המערך באופן מאוזן בתת המערכים (בחלוקה הרקורסיבית), אני אצליח להשיג את המקרה הממוצע קרי O(NLOGN)
עוד משהו שיש לתת עליו את הדעת והוא מה זה מקרה מאוזן?
אז לחלק את המערך באופן מאוזן סביב x הוא לאו דווקא לחלק אותו חצי חצי אפילו אנחנו יכולים להשיג תוצאה יותר גרועה והיא חילוק מאוזן סביב נקודת הפרטישן כאשר היחס הוא של 1:9 כן כן..!! גם זה יניב לי חלוקה מאוזנת (כפי שניתן לראות בתמונה)
כעת כתבתי סקריפט קצר שייתן לחוש באופן אינטואיטיבי ונעים את המהירות של קוויקסורט על פני מרג סורט הקוד כתוב בפייתון והוא נמצא כאן:
https://www.online-python.com/3nMJoXTlEz
הקוד הבא מחולק ל 3 חלקים עיקריים:
- אלגוריתם איטראטיבי של מרג׳ סורט וקוויק סורט כדי לא להעמיס על המחשב שלנו עם קריאות רקורסיביות.
- פונקציה בשם benchmark שתבדוק את הזמן time שלוקח לכל אלגוריתם לסיים את פעילותו
- נריץ אותם בטרדים נפרדים כך ש במיון עם מספרים ממש גדולים נחסוך זמן המתנה.
נראה כמה מסקנות מעניינות מאוד מהקוד הנל:
אם נדאג לכך שהחלוקה תהיה מאוזנת ע״י כך שנשים ב n1 מספר שווה אחד לשני ,
במערך random data שהוא בעצם מערך שמייצר לי מספרים באופן אקראי
random_data = [random.randint(1, n1) for _ in range(n1)]
למשל עבור n1 = 10 יכול להיווצר לי המערך הבא: [3, 4, 1, 9, 2, 9, 8, 10, 6, 7] כלומר 10 איברים שגודל האיבר הוא מ 1-10
אזי במקרה הנל תמיד quickSort ינצח , תנסו בעצמכם:)
למשל עבור n1=9,999,999
נקבל:
- שימו לב שלכל ריצה מספר השניות ישתנו, אבל היחס פחות או יותר בין הריצות תמיד יהיה לטובת קוויקסורט
דבר זה קורה מכיוון ש החלוקה של השגרה partition היא מאוזנת (כי המספרים במערך תמיד שונים אחד מהשני) ועקב כך באופן סטטיסטי בתת ריצות של קוויקסורט התקיים חלוקה מאוזנת.
אבל נראה משהו מעניין אם n1 יהיה שונה כך ש
random_data = [random.randint(1, n2) for _ in range(n1)]
התקיים כי n1 >= n2*100
100 בערכה גסה
אזי במקרה כזה כבר mergesort ינצח
למשל עבור n1=100 ו n2=100000
וזאת מכיוון שעכשיו הרבה מספרים יחזרו המון פעמים ולכן החלוקה של השגרה partition תהיה פחות טובה!!!
(נקודה למחשבה שלכם – מדוע)*
כלומר אני יכול להסיק את המסקנה (האינטואיטיבית) הבאה:
במקרים שאני יודע שהסדר שלי יהיה ע״פ מפתחות שונים אחד מהשני (נניח שזה אובייקטים) אז כדאי למיין אותם ב קוויקסורט.
ובמקרים שיש לי וודאות גבוהה של חזרה על מפתחות שונים (חזרה של כמה וכמה פעמים בכל פעם) אזי כדאי לי להשתמש ב מרג׳ סורט.
אז עכשיו נשאל מה קורה בעולם האמיתי: (ניקח לדיון את מנוע ה v8 של גוגל)
בעבר:
Array.prototype.sort הסתמך על מימוש Quicksort עם טיפה שינוי קטן.
הבסיס הוא Quicksort עם נטייה ל-Insertion Sort עבור מערכים קטנים יותר (אורך <10).
הנטייה ל-Insertion Sort נעשתה גם כאשר הרקורסיה של Quicksort הגיעה לאורך מערך משנה של 10 איברים. (בתת מערכים )
באופן כללי כדאי לדעת כי מיון הכנסה הוא יותר יעיל עבור מערכים קטנים יותר.
כיום v8
משתמש באלגוריתם שנקרא TimSort
הסבר מתוך הבלוג
TimSort (שקרוי על שם מי שפיתח אותו, טים פיטר, ממפתחי פייטון – זה לא אלגוריתם שהגיע מהאקדמיה) בבסיסו מריץ MergeSort (אלגוריתם שלרוב מבצע טוב מהרגיל) בעוד הוא משתמש ב batches קטנים ב Insertion Sort – היעיל במיוחד למיון קבוצות קטנות של נתונים.
בנתונים מהעולם האמיתי המידע לא מפוזר באופן אקראי לחלוטין. בעצם: קשה מאוד לייצר נתונים אקראיים לחלוטין. בנתונים ״רגילים״ של מערכים יש בו רצפים, גדולים או קטנים, של איברים ממוינים.
TimSort פועל בגדול באופן הבא:
- סריקה של הנתונים ואיתור רצפים עולים ורצפים יורדים. אם הרצף יורד – הוא פשוט יהפוך אותו.
- הנתונים כבר ממוינים? סיימנו ב (O(n. לא נשמע חוכמה, אבל QuickSort ו MergeSort יבזבזו כאן (O(n*lgn, זה יכול להוות כ10 או פי 100 – יותר זמן ריצה.
- קבוצות של עד 64 איברים – ממיינים בעזרת Insertion Sort, היעיל לקבוצות קטנות של נתונים וגם נהנה מ Data Locality.
- שימוש ב Merge Sort על מנת למיין את הקבוצות הממוינות – כאשר נשמר איזון בין הקבוצות בעקבות המיון המוקדם
מקווה שנהניתם 🙂
פוסטים ומאמרים נוספים ניתן למצוא בדף הלינקדין shay Sarussi Elshten
