[Powered by Google Translate] בטח שמע אנשים מדברים על אלגוריתם מהיר או יעיל לביצוע המשימה הספציפית שלך, אבל מה בדיוק זה אומר לגבי אלגוריתם כדי להיות מהיר או יעיל? טוב, זה לא מדבר על מדידה בזמן אמת, כמו שניות או דקות. הסיבה לכך היא חומרת מחשב ותוכנה להשתנות באופן דרסטי. התכנית שלי אולי איטית יותר משלך, משום שאני מפעיל אותו במחשב ישן יותר, או כי אני במקרה יהיה משחק משחק וידאו מקוון באותו הזמן, המשתלט כל הזיכרון שלי, או שאני יכול להיות מפעיל התכנית שלי דרך תוכנות שונות אשר מתקשר עם מכונה אחרת ברמה נמוכה. זה כמו להשוות תפוחים ותפוזים. רק בגלל שהמחשב שלי האיטי לוקח יותר זמן יותר משלך להחזיר תשובה זה לא אומר שיש לך אלגוריתם היעיל יותר. 

לכן, מאז אנחנו לא יכולים להשוות ישירות את runtimes של תוכניות בשניות או דקות, איך אנחנו להשוות 2 אלגוריתמים שונים ללא קשר לחומרה שלהם או סביבת תוכנה? כדי ליצור צורה אחידה יותר של מדידת יעילות אלגוריתמית, מדעני מחשב ומתמטיקאים פתחו מושגים למדידת המורכבות אסימפטוטי של תכנית וסימון בשם 'Ohnotation הגדול' לתיאור זה. ההגדרה הרשמית היא שפונקציה f (x) פועל על מנת של g (x) אם קיים חלק (x) ערך, x ₀ ו חלק קבוע, C, שעבורו f (x) היא פחות או שווה ל שהזמנים הקבועים g (x) לכל x הגדול מ ₀ x. 

אבל אל תפחד משם על ידי ההגדרה פורמלית. מה זה בעצם אומר במונחים תיאורטיים פחות? ובכן, זה בעצם דרך של ניתוח כמה מהר זמן הריצה של תכנית גדל אסימפטוטית. כלומר, כגודלו של התשומות שלך מגביר לקראת אינסוף, תגיד, אתה ממיין מערך של 1000 בהשוואה לגודל מערך בגודל 10. איך זמן הריצה של התכנית שלך יגדל? לדוגמה, תניח לספור את מספר התווים במחרוזת הדרך הפשוטה  על ידי הליכה דרך כל השרשרת מכתב אחר מכתב והוספת 1 למונה לכל דמות. אלגוריתם זה אמר לרוץ בזמן ליניארי ביחס למספר התווים, 'נ' במחרוזת. בקיצור, הוא פועל בO (n). מדוע זה קורה? ובכן, שימוש בגישה זו, הזמן הנדרש לכל אורך המחרוזת הוא פרופורציונלי למספר התווים. לספור את מספר התווים במחרוזת 20-אופי הוא הולך לקחת זמן כפול כפי שהוא לוקח כדי לספור את התווים במחרוזת 10-אופי, כי אתה צריך להסתכל על כל הדמויות וכל תו לוקח את אותה כמות הזמן להסתכל. ככל שתגדיל את מספר התווים, זמן הריצה יהיה להגדיל באופן ליניארי עם אורך הקלט. 

כעת, דמיינו אם אתה מחליט שזמן ליניארי, O (n), פשוט לא היה מהיר מספיק בשבילך? אולי אתה אחסון מחרוזות ענקיות, ואתה לא יכול להרשות את תוספת זמן זה ייקח לעבור את כל הדמויות שלהם נספרות אחד על אחד. אז, אתה מחליט לנסות משהו אחר. מה אם קורה כבר כדי לאחסן את מספר התווים במחרוזת, למשל, במשתנה שנקראה "לן, ' בשלב המוקדם של התכנית, עוד לפני שאתה לאחסן את התו הראשון במחרוזת שלך? ואז, כל מה שהיית צריך לעשות עכשיו כדי לברר את אורך המחרוזת, הוא לבדוק מה הערך של המשתנה. לא היית צריך להסתכל על עצמו בכל המחרוזת, וגישת הערך של משתנה כמו len נחשבת פעולת זמן asymptotically מתמדת, או O (1). מדוע זה קורה? ובכן, זוכר מה מורכבות asymptotic אומרות. כיצד משתנה זמן הריצה כגודל התשומות שלך גדלה? 

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

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

כפי שאתם יכולים לנחש, יש הרבה runtimes O הגדול שונה למדידה עם אלגוריתמים. O (n) ² אלגוריתמי asymptotically איטיים יותר מאלגוריתמי O (n). כלומר, ככל שמספר אלמנטים (n) גדל, סופו של דבר O (n) ² אלגוריתמים ייקחו יותר זמן מ O אלגוריתמים (n) כדי לברוח. זה לא אומר שאלגוריתמי O (n) תמיד לרוץ מהר יותר מ O (n) אלגוריתמי ², גם באותה הסביבה, באותה החומרה. אולי עבור גדלי קלט קטנים,  O (n) ² אלגוריתם באמת עשוי לעבוד מהר יותר, אבל, בסופו, כגודל הקלט מגדיל לקראת אינסוף, O זמן הריצה (n) ² של האלגוריתם סופו של דבר להאפיל על זמן הריצה של אלגוריתם O (n). בדיוק כמו כל פונקציה מתמטית ריבועית  סופו של דבר להשתלט על כל פונקציה לינארית, לא משנה כמה מראש יתחיל הפונקציה לינארית מתחיל עם. אם אתה עובד עם כמויות גדולות של נתונים, אלגוריתמים שרצים בO (n) ² זמן באמת יכול בסופו של האטת התכנית שלך, אבל לגודל קלט קטן, אתה כנראה אפילו לא שמת לב. 

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

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

אלגוריתם חזק זה חותך את גודל המערך במחצית עם כל פעולה. לכן, כדי למצוא את רכיב במערך ממוין בגודל 8, לכל היותר (להתחבר ₂ 8), או 3 של פעולות אלה, בדיקת אלמנט האמצע, ואז לחתוך את המערך במחצית יידרש, ואילו מערך בגודל 16 לוקח (להתחבר ₂ 16), או 4 פעולות. זה רק מבצע נוסף 1 למערך בגודל כפול. הכפלת הגודל של המערך מגדיל את זמן הריצה על ידי גוש של קוד זה רק 1. שוב, בודק מרכיב אמצע הרשימה, ואז פיצול. אז, זה אומר לפעול בזמן לוגריתמים, O (logn). אבל הרגע, אתה אומר, לא זה תלוי איפה ברשימת האלמנט שאתה מחפש הוא? מה אם האלמנט הראשון אתה מסתכל קורה להיות נכון? ואז, זה לוקח מבצע 1 בלבד, לא משנה כמה גדול היא הרשימה. 

ובכן, זו הסיבה שמדעני מחשב יש יותר תנאים למורכבות אסימפטוטי המשקף את תמונת מצב ומקרה הגרוע ביותר הופעות של אלגוריתם. לייתר דיוק, את הגבול העליון ותחתון בזמן הריצה. במקרה הטוב ביותר לחיפוש בינארי, האלמנט שלנו הוא ממש שם באמצע, ואתה מקבל את זה בזמן קבוע, לא משנה כמה גדול את שאר המערך הוא. הסמל משמש לכך הוא Ω. לכן, אלגוריתם זה אמר לרוץ בΩ (1). במקרה הטוב ביותר, הוא מוצא את אלמנט מהירות, לא משנה כמה גדול הוא המערך, אבל במקרה הגרוע ביותר, יש לבצע (logn) בדיקות מפוצלות של המערך כדי למצוא את האלמנט הנכון. גבולות מקרה הגרוע ביותר העליונים מופנים לעם "O" הגדול שאתה כבר יודע. אז, זה O (logn), אבל Ω (1). 

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

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

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

אם אתה מפעיל באלגוריתם O (n) ², או יותר גרוע, O (2 ⁿ) אלגוריתם, אחד מסוגי הצמיחה המהירים ביותר, אתה באמת מתחיל לשים לב להאטה כשאתה מתחיל לעבוד עם כמויות גדולות יותר של נתונים. 

זה מורכבות אסימפטוטי. תודה.