מבנה נתונים: שאלה
- פותח הנושא shochat1
- פורסם בתאריך
ההסבר הוא פשוט חישוב
אם מדובר בפונקציה - אז מדובר בחישוב מתמטי גרידא אם מדובר בחישוב סיבוכיות אלגוריתם - אז מדובר בספירת צעדים, עבור כל המקרים האפשריים, ומפה המקרה הגרוע זה המקרה עם המספר הצעדים הגדול ביותר כתלות בקלט, הטוב ביותר זה המקרה עם הספר הצעדים הקטן ביותר כתלות בקלט, והמקרה הממוצע זה מספר הצעדים כתלות בקלט ה"ממוצע" (שהגדרה של זה תלויה באלגוריתם עצמו).
אם מדובר בפונקציה - אז מדובר בחישוב מתמטי גרידא אם מדובר בחישוב סיבוכיות אלגוריתם - אז מדובר בספירת צעדים, עבור כל המקרים האפשריים, ומפה המקרה הגרוע זה המקרה עם המספר הצעדים הגדול ביותר כתלות בקלט, הטוב ביותר זה המקרה עם הספר הצעדים הקטן ביותר כתלות בקלט, והמקרה הממוצע זה מספר הצעדים כתלות בקלט ה"ממוצע" (שהגדרה של זה תלויה באלגוריתם עצמו).
אני לא מבין
O - פונקציה F היא O של G אם G זאת כפולה של F במקדם סופי כלשהו. o - פונקציה F היא o זשל G אם F זניחה יחסית לG (ז"א בשאיפה לאינסוף, חלוקת F בG תתן 0) אומגה גדול - פונקציה F היא אומגה גדול של G אם G זאת כפולה של F במקדם חיובי כלשהו. אומגה קטן - פונקציה F היא אומגה קטן של G אם G זניחה יחסית לF (ז"א בשאיפה לאינסוף, חלוקה של F בG תתן אינסוף). F היא תתה של G אם ורק אם F היא גם O של G וגם אומגה גדול של G. אלה הגדרות מתמטיות. F היא O של G אומר, בניפנוף ידיים, שG חוסמת את F מלמעלה, אבל F יכולה להיות שווה לG, ואילו במקרה של o , אז G חוסמת את F מלמעלה וגם F לעולם לא תשתווה לG (אפשר להקביל את O ליחס => ואת o ליחס >) בהתאמה אומגה גדול זה <= ואומגה קטן זה <. איך זה עוזר לי לתאר מקרים טוב גרוע וממוצע לגבי אומגדה או ותטה
O - פונקציה F היא O של G אם G זאת כפולה של F במקדם סופי כלשהו. o - פונקציה F היא o זשל G אם F זניחה יחסית לG (ז"א בשאיפה לאינסוף, חלוקת F בG תתן 0) אומגה גדול - פונקציה F היא אומגה גדול של G אם G זאת כפולה של F במקדם חיובי כלשהו. אומגה קטן - פונקציה F היא אומגה קטן של G אם G זניחה יחסית לF (ז"א בשאיפה לאינסוף, חלוקה של F בG תתן אינסוף). F היא תתה של G אם ורק אם F היא גם O של G וגם אומגה גדול של G. אלה הגדרות מתמטיות. F היא O של G אומר, בניפנוף ידיים, שG חוסמת את F מלמעלה, אבל F יכולה להיות שווה לG, ואילו במקרה של o , אז G חוסמת את F מלמעלה וגם F לעולם לא תשתווה לG (אפשר להקביל את O ליחס => ואת o ליחס >) בהתאמה אומגה גדול זה <= ואומגה קטן זה <. איך זה עוזר לי לתאר מקרים טוב גרוע וממוצע לגבי אומגדה או ותטה
אז ככה
אם אנו מדברים על המקרה טוב בכלל אנו מדברים על זה שהפריט אותו אנו מחפשים נמצא ממש בתחילת המחסנית המקרה הגרוע שהוא נמצא בסוף המחסנית ואז צריך לעבור את כולה בשביל למצוא אותו המקרה הממוצע כאשר הוא באחד מתוך n-1 האיברים האחרים אך האם המקרה הגרוע של O הוא שבקלט הכי גרוע שיכניסו סדר גודל של זמן הריצה יהיה מקסימום n ולא יעבור את ה- n. והמקרה הטוב יהיה שלו יהיה 1 השאלה אם זה נכון ואם נדבר על אומגה יהיו התשובות עבורו??
אם אנו מדברים על המקרה טוב בכלל אנו מדברים על זה שהפריט אותו אנו מחפשים נמצא ממש בתחילת המחסנית המקרה הגרוע שהוא נמצא בסוף המחסנית ואז צריך לעבור את כולה בשביל למצוא אותו המקרה הממוצע כאשר הוא באחד מתוך n-1 האיברים האחרים אך האם המקרה הגרוע של O הוא שבקלט הכי גרוע שיכניסו סדר גודל של זמן הריצה יהיה מקסימום n ולא יעבור את ה- n. והמקרה הטוב יהיה שלו יהיה 1 השאלה אם זה נכון ואם נדבר על אומגה יהיו התשובות עבורו??
Copyright©1996-2021,Tapuz Media Ltd. Forum software by XenForo® © 2010-2020 XenForo Ltd.