שאלה קטנה במבוא למדמ"ח

[Fluff]

עבור מערך באורך n, האם עדכון של כל הערכים במערך (שינוי המערך עצמו, לא יצירת מערך חדש) זה סיבוכיות מקום נוסף http://www.codecogs.com/gif.latex?O(1) או http://www.codecogs.com/gif.latex?O(n)?

למשל משהו כמו arr=arr+1

[stanly]

נו באמת...

 

אם זה קוד כמו שאתה מתאר אז ברור שזה O(1) אתה גם מדגיש שזה מקום נוסף.

 

אם יש רקורסיה או משהו כזה אז יכול להיות שיש צריכת מקום כתלות בקלט.

[Fluff]

הממ תודה, רק וידאתי.

יש לי עוד שאלה:

יש ב-C איזושהי דרך להכריז על סתם מחרוזת (ואז אחרי זה לשים שם מחרוזת מה-scanf)?

כי שמתי לב שהקוד 

char s[]="";

מאוד בעייתי, אבל למשל

char s[50];

 

עובד מצוין, רק שהוא דורש לחסום את אורך המחרוזת מראש. (ודברים כמו  http://www.codecogs.com/gif.latex?char%5C:s%5B%5C:%5D בכלל לא עובדים ב-C)

[stanly]

ב-C אין מחרוזת מוגדרת מראש, יש CHAR כפי שרשמת שמכיל תו אחד.

 

יש הסכמה בעל פה שמחרוזת מציגים על ידי מערך תוים שמסתיים בתו 0\ שזה NULL.

 

מה שרשמת בקוד הראשון מקצה מערך של מחרוזת ריקה, כלומר התו היחיד בה הוא NULL ואי אפשר לשים מחרוזת יותר גדולה.

 

בקוד השני מותר לשים כל מחרוזת עד גודל 49 (לא כולל את ה-NULL)

 

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