צהריים טובים,

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

למשל בקוד הבא:

int begins_with(char *s1, char *s2)
{
while (*s1 && *s2) {
if (*s1 != *s2)
return 0;
s1++; s2++;
}
return (*s2==0);
}

האם בחישוב סיבוכיות מקום יש צורך לקחת את אורך החרוזות או שהסיבוכיות מקום היא סדר גודל של 1?

תודה מראש.

http://en.wikipedia.org/wiki/Problem_size

בד"כ מדברים על סיבוכיות כתלות בקידוד מסויים של הקלט. מן הסתם צריכים לקחת בחשבון את סכום גדלי המחרוזות.

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

אם נקרא לאורך המחרוזות הקצרה n ולהפרש שבין אורכי המחרוזות m אז למעשה המקום המירבי שיכול ל"היתפס" בתוכנית הוא mxn?

int count_occurances(char *s1, char *s2)
{
int counter = 0,
curr_pos = 0,
last_pos = strlen(s1)  strlen(s2);
while (curr_pos <= last_pos) {
counter += begins_with(s1+curr_pos, s2);
curr_pos++;
}
return counter;
}

תודה.

min(n,m) - זהו מספר הפעולות שאתה עושה.

"המדד של כמות הזיכרון הנצרך נקרא סיבוכיות מקום. הגדרה יותר מפורטת של סיבוכיות המקום

היא: סדר הגודל של מספר תאי הזיכרון שמנצל האלגוריתם בזמן ריצתו. "

בשתי הפונקציות שלך מדובר על O של 1. בלי שום קשר לאורך המחרוזות. הפונקציה משתמשת בזכרון בגודל קובע לכל קלט.

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

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

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

http://estudy.openu.ac.il/opus/static/binaries/edit_news/bank2%5C%D7%A1%D7%99%D7%91%D7%95%D7%9B%D7%99%D7%95%D7%AA%20%D7%9E%D7%A7%D7%95%D7%9D_0.pdf

הבנתי תודה לך על ההסבר.

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

עוברים על שתיהן, וחסם הדוק לא קיים בכלל?

בפונקציה השניה אם נקרא להפרש שבין אורכי המחרוזות m ולאורך המחרוזת בפונציקה הקודמת n אז הסיבוכיות היא מסדר mxn?

תודה שוב פעם.