תרגילי מתמטיקה 4 יחידות לחברה של מוטי

[GaBi_88]

[font=monospace]int i, j, k;
[/font]
[font=monospace]for (i = 1; i [/font]
[font=monospace]for (j = 0; j [/font]
[font=monospace]for (k = n; k > j; k--){
syso("**");
[/font]}
[font=monospace]}
[/font]}

 

למשל בדוגמא הספציפית הזאת, הלולאה ה-3 לא מתקיימת אף פעם.

איך אני מתייחס לאחרות, מהיא צורת החישוב?

[ofir]

הלולאת הראשית תרוץ n/3 פעמים. שזה o(n) הלולאה עם ה j גם

סה"כ n^2

כמו שאמרת הלולאה השלישית לא רלוונטית....

[ofir]

סליחה. תיקון. הלולאה הראשית log3n

סהכ nlog3n

[Pika007]

נצל"ש

יש פה תותחי פיזיקה/כימיה?

איכשהו מבין 12 שאלות קלות להחריד באיזשהו גיליון, קיבלנו זוועה אחת כזו-

 

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

[GaBi_88]

אופיר, איך אתה מבצע את החישוב?

[fatboy1340]

נצל"ש

יש פה תותחי פיזיקה/כימיה?

איכשהו מבין 12 שאלות קלות להחריד באיזשהו גיליון, קיבלנו זוועה אחת כזו-

 

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

 

אני קצת חלוד בנוסחאות - אבל - האם התייחסת לכך שקו ספקטרום C הןא שביעי במספר?

[Pika007]

הפוך גוטה, הפוך. הרמות הולכות מאורך גל ארוך לקצר, רק ש A אינו קו שנוצר בגלל דעיכה למצב הבסיס, אלא למצב המעורר הראשון (כנראה! לא מצוין בבירור) כלומר n=2, אבל אין שום דרך לוודא את זה.

עריכה אחרונה ב-14 לאפריל, 2014 על ידי Pika007

[ofir]

אופיר, איך אתה מבצע את החישוב?

 

ה *= זאת בדיוק הפעולה ההפוכה ללוג (בתנאי שהכופל קבוע)

שאר החישוב זה הכפלה של הלולאה הראשית במשנית.

[m3x7r3m3]

לא יודע לגבי השאר, אותי זה מאוד מעניין.

הערה לגבי הסיבוכיות:

לולאה בתוך לולאה זה לא באופן אוטומטי N^2.

אם אחת הלולאות רצה מספר קבוע של פעמים אז עדיין זה יהיה n.

לדוגמא, אם אחת הלולאות רצה על הספרות

 

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

 

[font=monospace]int i, j, k;
[/font]
[font=monospace]for (i = 1; i [/font]
[font=monospace]for (j = 0; j [/font]
[font=monospace]for (k = n; k > j; k--){
syso("**");
[/font]}
[font=monospace]}
[/font]}

 

למשל בדוגמא הספציפית הזאת, הלולאה ה-3 לא מתקיימת אף פעם.

איך אני מתייחס לאחרות, מהיא צורת החישוב?

 

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

האמצעית כמובן n והפנימית ביותר תלויה בלולאה האמצעית, הפנימית עבור j=0 תרוץ n פעמים, אחר כך n-1 וכו, למעשה שתי הלולאות הפנימיות ירוצו סה"כ סכום של 1...n פעמים וסה"כ שלושת הלולאות ירוצו log3n*sum(1...n) כשבעיקרון כותבים את הסכום עם סיגמא.

[ofir]

לא שמתי לב שהלולאה השלישית בתוך השניה.

אז שתי הפנימיות הן n^2 הסבר:

sum(1..n)=(n×(n+1)/2)=(n^2+n)/2=O(n^2)

 

וסהכ n^2log3n

[m3x7r3m3]

זה נכון עבור O אך לא עבור תטא.

 

הסבר: n*sum(1...n) כמובן יהיה שייך ל-O(N^2) כי חסום על ידי N^2 מלמעלה, אבל הוא לא שייך לתטא של N^2 מכיוון שהוא לא חסום ע"י N^2 מלמטה.

תטא זוהי שייכות לסדר גודל כאשר האלגוריתם חסום מלמעלה ומלמטה ע"י אותו סדר גודל.

 

כלומר O(n^2log3n) אבל תטא של (nlog3nsum(1...n), יש גם מרצים שלא יקבלו תשובה של O(n^2).

[Guy_25]

בימים האחרונים אני כותב הגשה בנושא "עצים בינאריים" בשפת C

רציתי לשאול שאלה כללית, מה הדרך היעילה ביותר לקלוט נתונים אל תוך עץ?

האם לאחסן את הקלט במערך ולאחר מכן להכניס את המערך לעץ כרצוני?

או שמא עדיף בזמן קליטת הקלט להכניס את הנתונים לעץ?

[m3x7r3m3]

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

 

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

[Guy_25]

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

אנחנו נדרשים לבנות עץ בינארי שמכיל חישוב מתמטי בין ספרות בלבד.

הוגדר לנו main שמקבל סטרינג שבה נמצא הביטוי המתמטי הדרוש לחישוב.

צריך לכתוב 2 פונקציות:

1) מכניסה את החישוב לעץ כפי שהוגדר

2) מחשבת את הביטוי

 

איך מכניסים את הביטוי לעץ:

כל אופרטור משמש כצומת וכל ספרה משמשת כעלה.

כלומר הביטוי 2+4 יתורגם לעץ:

+

\ /

2 4

ולצורך העניין 3*(2+4) יתורגם

 

*

\ /

3 +

\ /

4 2

וכן הלאה וכן הלאה.

 

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

 

דרך אגב,

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

 

עריכה:

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

[liav.h]

לא הבנתי מה בדיוק אתה שואל.

הם מעוניינים שתיעזר במבנה העץ לחישוב הביטוי המתמטי.

מקבל מחרוזת ובונה ממנה עץ מתאים.

לאחר מכן עובר על העץ ומבצע את החישוב.

 

בקשר לשאלה השניה - תטא של N - הכוונה לחסם הדוק (עליון ותחתון) בסדר גודל של N.

כלומר, O(N) מגדיר חסם עליון בסדר גודל של N.

אומגה של N מגדיר חסם תחתון בסדר גודל של N.

ותטא מתייחסת לקיום השניים הנ"ל - כלומר, אם גם מתקיים O(N) וגם מתקיים אומגה של N, אז יתקיים תטא של N.