אני רוצה לדעת אם עניתי על שאלות

[siro1]

אני רוצה לדעת אם עניתי על שאלות

אלו נכון- א. קיים מערך בן 26 מקומות, ובו 25 מאותיות הא"ב האנגלי. (כלומר חסרה אות אחת). למצוא אלגוריתם שמוצא איזו אות חסרה. רשמי מהי הסיבוכיות ב. במערך הפעם יש את 24 מספרים מ-0 עד 25 ,כאשר מספר אחד חסר. שוב צריך למצוא את המס' החסר כאשר צריכים לשפר את סדר הגודל של הסיבוכיות באופן משמעותי. רשמי סיבוכיות אלו הפתרונות שלי- א. אני מחשבת את סכום האסקי של כל האותיות ושמה במשתנה A , אח"כ מחשבת את סכום האסקי של האותיות במערך ושמה במשתנה B. האות החסרה היא האות שהאסקי שלה A-B . בבהנחה שגודל המערך הוא N הסיבוכיות היא O של N. ב.מחשבים את סכום האיברים במערך ושמים במשתנה B. למציאת סכום המספרים מ -0 עד 25 אשתמש בנוסחא n+1)n/2 וכך חוסכים את זמן סיכום כל המספרים. אך עדיין הסיבוכיות היא O של N . איך ניתן לשפר יותר את האלגוריתם? האם הפתרונות שהצעתי טובים או קיימים יותר מוצלחים? תודה

 

[DadleFish]

לדעתי...

הפתרון השני חייב להיות (O(N, וייתכן שציפו לפתרון התרגיל הראשון בסדר גודל גדול מ-(O(N למרות שקשה לי אפילו לחשוב על פתרון שעונה על זה

בכל מקרה, נדמה לי שאי אפשר לרדת מ-(O(N בשאלה השניה, כי חייבים לסרוק את המערך לפחות פעם אחת.

 

[siro1]

תודה! אז הפתרון הראשון שלי היה

יעיל יותר ממה שציפו.... טוב לדעת

 

[DadleFish]

כנראה, זה ההסבר היחיד שלי...

 

[yonyl]

לא נכון!!!

הפיתרון הראשון הוא ב O של 1

 

[vinney]

הא?

 

[DadleFish]

מצטרף להא?

 

[yonyl]

אוקי הסבר

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

 

[yonyl]

דרך אגב

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

 

[DadleFish]

במילים אחרות,

כל פתרון לסודוקו, לא משנה מה הוא עושה, יתבצע לתפיסתך ב-(O(1?

 

[yonyl]

עקרונית כן.

 

[yonyl]

מהו קבוע

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

 

[yonyl]

קתב לא קצת

 

[yonyl]

אופס אני לא יודע לכתוב - קצב !

 

[yonyl]

והסבר נוסף מזוית שונה

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

 

[vinney]

המם...

אם תשנה את ה25 ל26 סיבוכיות תגדל? תגדל. אז זה לא O של 1.

 

[yonyl]

אבל השאלה פרטנית- לא כללית

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

 

[vinney]

אתה מתפלסף ואתה יודע את זה

 

[yonyl]

אולי התכוונתו

שבראשון אתה תסרוק פעם ראשונה ותחפש את 'A' פעם שניה ותחפש את 'B' וכך הלאה.לא נראה לי שמישהו ייפתור בדרך כזאת מטומטמת, אבל אולי. ואז כביכול הסדר גודל לפי הכוונה שלהם היא N בחזקת N למרות שכפי שכתבתי למעטה זה עדין יהיה O של 1.