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