לילה טוב,

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

קוד:

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

קוד:

 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;
} 

סיבוכיות מקום - בשתי הפונקציות הסיבוכיות מסדר גודל של 1 (קבוע).

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

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

תודה רבה מראש.

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

!!אזהרה!!

ההודעה עלולה להכיל שברי אגוזים ו/או איברי דגים כלשהם

!!אזהרה!!