שאלה על סיבוכיות

[לושיי]

שאלה על סיבוכיות

אני צריך להגיע לסיבוכיות לינארית

O​

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

 

[DNile]

מה הn שלך?

האם זה אורך הרשימה הראשונה? אורך הרשימה השניה? מה היחס בין אורכי הרשימה? ובכלל, לא אמרת מה התרגיל שלך.

 

[לושיי]

אז ככה:

יש לי N שהוא אורך הרשימה הראשונה שעליו אני רץ ן - M שהוא אורך הרשימה השנייה ועליו אני מבצע את החיפוש הבינארי. אני לא יכול לרשום את התרגיל כי זה קשור לאונ'

 

[DNile]

אם לא תכתוב את התרגיל,

יהיה מאוד קשה להבין מה אתה מנסה לעשות. לגבי האורכים - האם יש לך יחס כלשהוא בין M לN? עקרונית, הסיבוכיות שלך היא

O(NlogM)​

שזה ליניארי רק אם M קבוע.

 

[לושיי]

תשובה מספקת ../images/Emo13.gif תודה רבה

 

[לושיי]

רגע רגע איך אני יודע

אם M קבוע? אם הוא אינו תלוי ב- N הוא נחשב קבוע?

 

[DNile]

אתה יודע על פי השאלה.

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

 

[לושיי]

אני באמת מצטער שאני לא יכול לרשום

לך את השאלה אבל אולי בכל זאת. על פי מה אתה מגדיר משהו כקבוע? אם אני נגדיר את M ב- COUNST האם הוא יחשב כקבוע?

 

[אלדד28]

אם M תלוי ב-N,

הוא לא קבוע. אם הוא תמיד מאית או אלפית מ-N, הוא תלוי ב-N ואינו קבוע. אם הוא תמיד 100 או 1000000, הוא קבוע.