סימון אסימפטוטי
סימון אסימפטוטי (ידוע גם כסימון שבח) - Big O. מה זה זמן מופחת.
ArrayList זה מערך גמיש בגודלו. הוא יודעה לגדול באופן אוטומטי כאשר אתם מוסיפים איברים. ArrayList מיישם מערך רגיל, אבל כאשר הוא מגיעה לגבול שלו - מיצר מערך חדש בגודל כפול והעתיק לשם כל האיברים. איך ניתן לתאר הכנסה של איבר ל ArrayList מבחינה אסימפטוטית? זאת שאלה טיפה טריקית. מערך התמעלה. יש בו N איברים. אנחנו מייצרים מערך חדש בגודל 2N ומעתיקים N איברים עליו. זה יקח O(n). אבל, אנחנו יודעים, שזה קורה רק לפעמים. בדרך כלל עלות של הוספה תהיה
O(1)
זמן.
אנחנו צריכים לקחת בחשבון 2 מיקרים האלה. וזה מה שעושה זמן מופחת.
אז מה יהיה זמן מופחת:
כאשר אנחנו מוסיפים איבר, אנחנו מכפילים קיבולת,
כאשר גודל של מערך הוא חזקה של 2. לכן, לאחר x איברים, אנחנו נעשה :
1, 2, 4, 8, 16,... x
העתקות.
מה הסכום של 1+2+4+...+ x ?
עדיף להתחיל לספור מהסוף:
x + x/2 + x/4 + x/8 +...+1 = 2x
לכן, הכנסה ל ArrayList של X איברים יקח
O(2x)
אבל זמן מופחת של כל הכנסה תהיה:
O(1)