מבוא לאלגוריתמים

[I dont belong here]

מבוא לאלגוריתמים

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

|x-y| <= (M-m)/n​

כאשר M הוא המקסימום של הסדרה ו m הוא המינימום. אני כבר נואש, יש למישהו רעיון?

 

[I dont belong here]

צריך לכתוב אלגוריתם

שיחזיר את שני האיברים האלה.

 

[Okuryo]

../images/Emo119.gifזה די מסובך,

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

 

[I dont belong here]

אני חושב שהבנתי אותך

אבל מה שקורה שאם אני עושה את זה עד שאני מגיע ל2 איברים (בצורה רקורסיבית) אז יש לי nlogn בסיבוכיות. או שלא הבנתי אותך עד הסוף

 

[I dont belong here]

טוב הגעתי למסקנה שזה O

תודה רבה! הצלת אותי.

 

[Okuryo]

../images/Emo119.gifכן, זה ב-(O(n ../images/Emo13.gif