סיבוכיות זמן ריצה

[snaidis]

סיבוכיות זמן ריצה

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

 

[vinney]

הויקיפדיה לא עוזרת לך?

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

 

[snaidis]

לא, ויקיפדיה ממש לא עזרה

אם אתה תוכל להסביר לי ולהדגים אני מאוד אשמח

 

[vinney]

טוב, על רגל אחת

ואז תחזור לויקיפדיה וCLR ותנסה להבין. עקרונית, כשמתכננים אלגוריתם כלשהו, מעניין אותנו מאוד לדעת עד כמה הוא יעיל. תורת החישוביות מגדירה אילו בעיות ניתן לפתור בצורה אלגוריתמית, ואילו לא, אבל אילו שניתן לפתור בצורה אלגוריתמית, לא בהכרח ניתן לפתור בצורה מעשית בגלל שהפתרון הקיים אינו יעיל. למשל - מגדלי הנוי או סוכן נוסע אלה בעיות בהחלט פתירות ברמה האלגוריתמית (בניגוד, למשל, לבעיית העצירה שאינה פתירה כלל), אך כל הפתרונות הידועים הם בסיבוכיות גבוהה כל כך, שאינם מעשיים. אז מה זה הסיבוכיות הזאת? זה בעצם המחיר של הפתרון. כמה עולה לך להריץ את האלגוריתם הזה על קלט כלשהו (בד"כ מדברים על סיבוכיות במושגים של פונקציה של N, כשN זה גודל הקלט של האלגוריתם), בד"כ מודדים את המקרה הגרוע ביותר (ז"א קלט בו האלגוריתם יהיה הכי יקר). מדד הסיבוכיות אינו מדויק, ובד"כ מסתפקים בסדרי גודל (מכאן הסימנים O, אומגה וטטה, המגדירים חסמים של פונקציה במתמטיקה). כשהאלגוריתם חסום על ידי פונקציה כלשהי מלמעלה (האלגוריתם הוא O של פונקציה כשלהי), זה אומר שלכל קלט, במקרה הכי גרוע, עלות האלגוריתם לא תעבור את גודל הפונקציה עבור הN הזה, להוציא קבועים). איך בונים את הפונקציה הזאת של עלות האלגוריתם? סופרים פעולות אטומיות שהאלגוריתם מבצע. מהי פעולה אטומית זה תלוי באלגוריתם, למשל פעולת החיבור בד"כ אטומית ברוב המקרים, אבל באלגוריתמים חישוביים דווקא זאת לא פעולה אטומית כלל וכלל, ואפילו די יקרה. בד"כ בוחרים פעולה בסיסית עבור האלגוריתם כפעולה אטומית, וסופרים כמה פעמים היא מתבצעת. דוגמא: אלגוריתם מיון בועות. לא אכתוב לך את האלגוריתם, אתה בטח מכיר אותו. הפעולות האטומיות שם אלה פעולות החלפה והשוואה, ואילו N זה גודל המערך אותו ממיינים. כל איבר (במקרה הגרוע ביותר) מושווה לכל אחד מהאיברים האחרים, מוחלף עם כל איבר אחר. ז"א עבור כל איבר מתבצעות 2N פעולות (2 אפשר לזרוק בהיותו קבוע), וזה מתבצע לכל N האיברים => הסיבוכיות של האלגוריתם במקרה הגרוע ביותר חסומה על ידי פונקצית N^2. החסם הוא הדוק, כי פועולת ההשוואה מתבצעות גם כשאין צורך להחליף, זאת אומרת שיתבצעו לכל היותר סדר גודל של N^2 פעולות, וגם לכל הפחות N^2 פעולות (ז"א, אם המערך כבר ממוין יתבעו פחות פעולות, כי לא יהיו החלפות, אבל סדר גודל לא ישתנה). מקווה שזה מבהיר קצת. אם לא אז תגיד איזה חלק לא הבנת

 

[snaidis]

וואו, תודה רבה לך זה הבהיר לי קצת

תודה רבה על ההשקעה והמאמץ על התגובה

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

 

[vinney]

תסתכל בקישורים

יש שם כמה קישורים לאתרים של קורסים במבני נתונים וסיבוכיות.

 

[snaidis]

לא ממש מצאתי ../images/Emo10.gif

 

[vinney]

נו באמת

פה יש לפחות 3 קישורים שקשורים למבני נתונים.

 

[incrediboy]

נראה לי שהספר של CLR הכי יעזור לך

נ.ב: אני מאמין שיש אותו גם באינטרנט .. בתור ebook

 

[vinney]

לא בצורה חוקית, כמה שידוע לי

אתה יכול לקנות אותו בתרגום (מצוין) לעברית, תסתכל בקישורים