samael

הסכום שלך זה מכפלה של גודל הקטע בערך הפונקציה. גם אם  ערך הפונקציה הוא 1, גודל הקטע הרי שואף לאפס..

1. שני מערכים בגודל n הם עדיין בסיבוכיות של On
2. לא. למעשה, מדי פעם אוהבים לתת שאלה במבחן שבה מספרים על פרופסור שהחליט לשפר את סיבוכיות זמן הריצה של מרגסורט באמצעות חלוקת המערכים ל-3 ולשאול למה (או האם) הוא טועה.
 
איפה אמרו לכם שזה חייב להיות חזקות של 2? תביא לינק.

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

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