שאלה ממש קטנה ומפגרת שמציקה לי- דחוף לפני המבחן

מנהל: TA_Isana

שלח תגובה
Shirley_sw
הודעות: 22
הצטרף: 13:00 12/12/2008

שאלה ממש קטנה ומפגרת שמציקה לי- דחוף לפני המבחן

שליחה על ידי Shirley_sw » 08:52 26/07/2009

בוקר טוב,

משהו קטן שמציק לי,

כשיוצרים מערך בפונקציית איתחול, משום מה אני זוכרת שדיברנו על זה שזה 0(1)
אבל בעצם זה לא מסתדר לי כי הרי ג'אבה מאפסת את המערך אם הוא של שלמים, או שמה לו false אם זה בולייאן וכו'..
אז זה 0(1) או בבכלל 0(n)??


תודה רבה.. :oops:

halpertc
הודעות: 6
הצטרף: 15:01 29/04/2009

Re: שאלה ממש קטנה ומפגרת שמציקה לי- דחוף לפני המבחן

שליחה על ידי halpertc » 09:10 26/07/2009

Java לא מאפסת את כל המערך אלא משתמשת ב-3 מערכים כדי לדמות איפוס כמו שראינו באחד התרגולים.

Shirley_sw
הודעות: 22
הצטרף: 13:00 12/12/2008

Re: שאלה ממש קטנה ומפגרת שמציקה לי- דחוף לפני המבחן

שליחה על ידי Shirley_sw » 09:12 26/07/2009

אתה מדבר על smart array?
אז אני יכולה לכתוב שאני משתמשת "במערך" (ולא להדגיש מערך חכם) ולהגיד שפעולת האיתחול לוקחת 0(1)? שאר הפעולות של מערך חכם הן באותו זמן כמו מערך רגיל?

TA_Gila
הודעות: 66
הצטרף: 14:56 24/04/2009
יצירת קשר:

Re: שאלה ממש קטנה ומפגרת שמציקה לי- דחוף לפני המבחן

שליחה על ידי TA_Gila » 13:13 26/07/2009

אם לא מציינים שמדובר במערך חכם (כמו זה שראינו בתירגול) אז ברור שזמן האיתחול לא יהיה קבוע אלא כגודל המערך.

באופן דומה, אם משתמשים ב-BST אי-אפשר לטעון שהזמן שלוקחת כל פעולה בסיסית הוא (O(log n. בשביל זה צריך להשתמש דווקא בעץ מאוזן, למשל בעץ AVL ולציין זאת במפורש!

שלח תגובה

חזור אל “- מבני נתונים”