חידה - מדעי המחשב

[גיל14]

חידה - מדעי המחשב

עץ בינארי יִקַרֵא (סליחה אם יש טעות בניקוד) עץ "פרו ורבו" אם לאחד מצמתיו יש שני נכדים (לפחות), שכל אחד מבן שונה. החידה: מהו סדר גודל הסיבוכיות הקטנה ביותר הדרושה לבעית ההכרעה (האם עץ בינארי נתון הוא עץ "פרו ורבו")?

 

[עריסטו]

../images/Emo62.gif נראה לי מוזר

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

 

[גיל14]

../images/Emo127.gif וכמובן עם הנתון החסר

ואם כל הרמות מלאות פרט, אולי, לאחרונה?

 

[גיל14]

"עץ שלם"

 

[עריסטו]

לא הבנתי את השאלה

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

כי רמה מס' 2 מלאה, כלומר לשורש יש שני נכדים שכל אחד מבן אחר...

 

[גיל14]

../images/Emo127.gif מקרה אחרון

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

 

[גיל14]

../images/Emo128.gif הפתרונות לעיל תקפים, לא חשוב