שלום... יש לי שאלה לכאלה שעושים
- פותח הנושא מעיני17
- פורסם בתאריך
או קיי.
"על רגל אחת ואז תחזור לויקיפדיה וCLR ותנסה להבין. עקרונית, כשמתכננים אלגוריתם כלשהו, מעניין אותנו מאוד לדעת עד כמה הוא יעיל. תורת החישוביות מגדירה אילו בעיות ניתן לפתור בצורה אלגוריתמית, ואילו לא, אבל אילו שניתן לפתור בצורה אלגוריתמית, לא בהכרח ניתן לפתור בצורה מעשית בגלל שהפתרון הקיים אינו יעיל. למשל - מגדלי הנוי או סוכן נוסע אלה בעיות בהחלט פתירות ברמה האלגוריתמית (בניגוד, למשל, לבעיית העצירה שאינה פתירה כלל), אך כל הפתרונות הידועים הם בסיבוכיות גבוהה כל כך, שאינם מעשיים. אז מה זה הסיבוכיות הזאת? זה בעצם המחיר של הפתרון. כמה עולה לך להריץ את האלגוריתם הזה על קלט כלשהו (בד"כ מדברים על סיבוכיות במושגים של פונקציה של N, כשN זה גודל הקלט של האלגוריתם), בד"כ מודדים את המקרה הגרוע ביותר (ז"א קלט בו האלגוריתם יהיה הכי יקר). מדד הסיבוכיות אינו מדויק, ובד"כ מסתפקים בסדרי גודל (מכאן הסימנים O, אומגה וטטה, המגדירים חסמים של פונקציה במתמטיקה). כשהאלגוריתם חסום על ידי פונקציה כלשהי מלמעלה (האלגוריתם הוא O של פונקציה כשלהי), זה אומר שלכל קלט, במקרה הכי גרוע, עלות האלגוריתם לא תעבור את גודל הפונקציה עבור הN הזה, להוציא קבועים). איך בונים את הפונקציה הזאת של עלות האלגוריתם? סופרים פעולות אטומיות שהאלגוריתם מבצע. מהי פעולה אטומית זה תלוי באלגוריתם, למשל פעולת החיבור בד"כ אטומית ברוב המקרים, אבל באלגוריתמים חישוביים דווקא זאת לא פעולה אטומית כלל וכלל, ואפילו די יקרה. בד"כ בוחרים פעולה בסיסית עבור האלגוריתם כפעולה אטומית, וסופרים כמה פעמים היא מתבצעת. דוגמא: אלגוריתם מיון בועות. לא אכתוב לך את האלגוריתם, אתה בטח מכיר אותו. הפעולות האטומיות שם אלה פעולות החלפה והשוואה, ואילו N זה גודל המערך אותו ממיינים. כל איבר (במקרה הגרוע ביותר) מושווה לכל אחד מהאיברים האחרים, מוחלף עם כל איבר אחר. ז"א עבור כל איבר מתבצעות 2N פעולות (2 אפשר לזרוק בהיותו קבוע), וזה מתבצע לכל N האיברים => הסיבוכיות של האלגוריתם במקרה הגרוע ביותר חסומה על ידי פונקצית N^2. החסם הוא הדוק, כי פועולת ההשוואה מתבצעות גם כשאין צורך להחליף, זאת אומרת שיתבצעו לכל היותר סדר גודל של N^2 פעולות, וגם לכל הפחות N^2 פעולות (ז"א, אם המערך כבר ממוין יתבעו פחות פעולות, כי לא יהיו החלפות, אבל סדר גודל לא ישתנה)." credits לויני....
"על רגל אחת ואז תחזור לויקיפדיה וCLR ותנסה להבין. עקרונית, כשמתכננים אלגוריתם כלשהו, מעניין אותנו מאוד לדעת עד כמה הוא יעיל. תורת החישוביות מגדירה אילו בעיות ניתן לפתור בצורה אלגוריתמית, ואילו לא, אבל אילו שניתן לפתור בצורה אלגוריתמית, לא בהכרח ניתן לפתור בצורה מעשית בגלל שהפתרון הקיים אינו יעיל. למשל - מגדלי הנוי או סוכן נוסע אלה בעיות בהחלט פתירות ברמה האלגוריתמית (בניגוד, למשל, לבעיית העצירה שאינה פתירה כלל), אך כל הפתרונות הידועים הם בסיבוכיות גבוהה כל כך, שאינם מעשיים. אז מה זה הסיבוכיות הזאת? זה בעצם המחיר של הפתרון. כמה עולה לך להריץ את האלגוריתם הזה על קלט כלשהו (בד"כ מדברים על סיבוכיות במושגים של פונקציה של N, כשN זה גודל הקלט של האלגוריתם), בד"כ מודדים את המקרה הגרוע ביותר (ז"א קלט בו האלגוריתם יהיה הכי יקר). מדד הסיבוכיות אינו מדויק, ובד"כ מסתפקים בסדרי גודל (מכאן הסימנים O, אומגה וטטה, המגדירים חסמים של פונקציה במתמטיקה). כשהאלגוריתם חסום על ידי פונקציה כלשהי מלמעלה (האלגוריתם הוא O של פונקציה כשלהי), זה אומר שלכל קלט, במקרה הכי גרוע, עלות האלגוריתם לא תעבור את גודל הפונקציה עבור הN הזה, להוציא קבועים). איך בונים את הפונקציה הזאת של עלות האלגוריתם? סופרים פעולות אטומיות שהאלגוריתם מבצע. מהי פעולה אטומית זה תלוי באלגוריתם, למשל פעולת החיבור בד"כ אטומית ברוב המקרים, אבל באלגוריתמים חישוביים דווקא זאת לא פעולה אטומית כלל וכלל, ואפילו די יקרה. בד"כ בוחרים פעולה בסיסית עבור האלגוריתם כפעולה אטומית, וסופרים כמה פעמים היא מתבצעת. דוגמא: אלגוריתם מיון בועות. לא אכתוב לך את האלגוריתם, אתה בטח מכיר אותו. הפעולות האטומיות שם אלה פעולות החלפה והשוואה, ואילו N זה גודל המערך אותו ממיינים. כל איבר (במקרה הגרוע ביותר) מושווה לכל אחד מהאיברים האחרים, מוחלף עם כל איבר אחר. ז"א עבור כל איבר מתבצעות 2N פעולות (2 אפשר לזרוק בהיותו קבוע), וזה מתבצע לכל N האיברים => הסיבוכיות של האלגוריתם במקרה הגרוע ביותר חסומה על ידי פונקצית N^2. החסם הוא הדוק, כי פועולת ההשוואה מתבצעות גם כשאין צורך להחליף, זאת אומרת שיתבצעו לכל היותר סדר גודל של N^2 פעולות, וגם לכל הפחות N^2 פעולות (ז"א, אם המערך כבר ממוין יתבעו פחות פעולות, כי לא יהיו החלפות, אבל סדר גודל לא ישתנה)." credits לויני....
/ O(n^2( ? זה מה שיש לנו בד"כ..בר באבא שלך
New member
אי דטרמיניזם ירד במיקוד
Copyright©1996-2021,Tapuz Media Ltd. Forum software by XenForo® © 2010-2020 XenForo Ltd.