סיבוכיות

[shiffit]

סיבוכיות

T = T(n/4) + T(3n/4) +1 במה הפונקציה הזו חסומה?

 

[GuestOfHonor]

אם אני לא טועה - log n

אפשר לוודא הריגה בעזרת 'שיטת ההצבה' (באינדוקציה) או בנפנופי ידיים בעזרת עץ.

 

[shiffit]

אז זהו שזה מה שאני חושבת

אבל בפיתרון של אוניברסיטת תל אביב אומרים שזה n ואני לא מצליחה להבין למה

 

[הפלאפל כבר דהוי]

זה כמובן שואף ל-3/4n שזה O של n

 

[GuestOfHonor]

אני זוכר במעומעם

שהראו לנו במבנה נתונים דוגמא עם שליש N ושני שליש N והראו בעזרת עץ קריאות שזה חסום תטה של log n. אבל כיוון שאני במיעוט ולא באמת ניסיתי לפתור את זה אני מקבל את דעת הרוב

.

 

[danby]

כמו צאן לטבח

תמשיך לקבל את דעת הרוב מבלי לחשוב עליה ונראה לאן תגיע.... קונפורמיזם זה לחלשים (בעיקר בראש).

 

[GuestOfHonor]

כמו צאן לקבע

במקרה אני קצת סומך פה על החבר'ה בפורום שידעו לתת תשובה נכונה לבעיה פשוטה, ולכן חוסך לעצמי את ה5 דקות שלוקח לוודא את זה באינדוקציה, בעיקר לאור המבחן שיש לי מחר. חצוף.

 

[danby]

תלמד לקבל ביקורת

 

[GuestOfHonor]

תלמד לתת אותה

ולא להיכנס באנשים שאתה לא מכיר על סמך הודעה אחת שראית. חצוף * 2.

 

[danby]

תקרא לי חצוף * 17

זה לא יעזור לך. עדין אתה לא יודע לקבל ביקורות. גם אם היא נוקבת וחריפה. ויכול להיות שאני לא יודע לתת ביקורות, וכן, בקריאה לאחור היא אולי היתה אישית מבלי שאני אכיר אותך כדי לכתוב את מה שאמרתי. אני עדין חושב שלקבל עמדה של "הרוב" מבלי אפילו לחשוב עליה זה אחד הדברים הכי גרועים שקיימים (באופן כללי בחברה שלנו). אני מתנצל אם נפגעת מהאופן שבו נאמרו הדברים - אבל אני עומד מאחורי המהות שלהם (גם אם זה בלי קשר לאופן בוא הם נאמרו). קונפורמיזם זה לחלשים.

 

[gil levi]

אתה צודק וטועה.

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

 

[danby]

זאת בדיוק הבעיה

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

 

[אמיתי ר]

O(N)

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

 

[shiffit]

משהוא יכול לפרט לי יותר

אני צריכה הסבר כי אני לא מבינה למה

 

[ron369]

ברור שזה N

הנקודה היא שבכל רמה בעץ הרקורסיה, סכום הקלטים של ה-T-ים הוא קבוע (N).

 

[shiffit]

אז זהו

שאם היה מדבור ב - T= T(n/4) + T(3n/4) + n התשובה הייתה בוודאות nlogn ועדיין בכל שורה יש n סכום העלים

 

[ron369]

אבל זה עדיין N.

(תחשבי טוב על הנושא

)

 

[inferno3]

לדעתי זה logn

באמת כמו שאמרו בכל רמה בעץ מגיעים ל-N( לא בכל רמה,כי קרוב לסוף חלק מהקודקודים נעלמים) גובה העץ הוא :

log 0.75 now we need to sum up all levels sigma 1 to log0.75 n and we're done.​

 

[inferno3]

תיקון

הבסיס של הלוג הוא אחד ושליש ולא שלושה רבעים,זה עדיין יוצא אותו דבר.

 

[forge]

אכן מדובר ב- טטה של N

אכן יש פער שלא ניתן להתעלם ממנו בין החסם העליון לתחתון. (לוג 4 של N לתחתון ולוג 4/3 של N לעליון). אולם, נבחין כי העץ שמתקבל הוא עץ מלא (הרקורסיה מגיעה לכל איבר פעם אחת בלבד) מס' העלים בעץ הוא N => מס' הקוד' הפנימיים הוא טטה של N => מס' הקוד' הכולל הוא טטה של N =>הזמן הכולל הוא טטה של N מ.ש.ל