שלום לכולם,
אני רוצה להיות בטוח: האם סיבוכיות הזמן של הפונקציה הבאה היא O(nlogn), וסיבוכיות המקום O(logn), כש n הוא אורך המחרוזת?
ואם כן, יש לכם מושג איך אני יכול להוריד את סיבוכיות הזמן להיות O(n)?

קוד:

int foldaux (char *s, int n)

{
	int i,flag=1;
	if (n==0 || n%2==1) return 0;
	i = n/2;
	do {
		i--;
		if (s[i]!=s[n-i-1]) flag=0;
	} while (i);

	return flag + foldaux(s,n/2);
}

תודה מראש.

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

על פניו - בלי להבין ממש מה אתה מנסה לעשות כאן, זה נראה כמו nLog(n) בזמן אבל לגבי מקום זה נראה כמו N.

שבודקת האם מחרוזת היא פולינדרומית, וכנ"ל לגבי כל תת מחרוזת שלה באורך חצי. כלומר, עבור abcddcba היא תחזיר 1, עבור abbaabba היא תחזיר 2.

למה סיבוכיות המקום היא N? הרי בכל קריאה של הפונ' המערך "מקוצץ" בחצי, כלומר העומק המקסימלי הוא logn, לדעתי.

סיבוכיות המקום היא N כי אתה מעביר מצביע למערך.
אם היית מעביר את המערך BYVALUE אז אולי זה היה גם נותן סיבוכיות מקום של NLOGN

למה אתה לא עושה בדיקה גם על "צד ימין"?

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

נו, זה אותו מצביע, הוא לא דורש זכרון חדש, לא תלוי באורך הקלט. אם הייתי מעביר By Value אז כן, זה היה NLOGN.