רוטר - מבנה נתונים-צריך עזרה בחישוב סיבוכיות זמן ריצה של 2 אלגוריתמים דומים

האשכול	מחבר	תאריך כתיבה	מספר
בעיקרון אתה צריך לבדוק כמה פעמים הלולאות יתבצעו, וכמה פעולות בכל איטרציה	ohadeytan	04.03.14 19:49	1
לדעתי בשנייה זה O(N^2)	danny444	04.03.14 19:58	2
מכתב:	ohadeytan	04.03.14 20:02	3
לא משנה	IDAN_500	05.03.14 21:16	4
כנראה שהשני זה NLOGN	Fstyle	08.03.14 08:55	5
הסיבוכיות היא לינארית, כנס להסבר...	IDAN_500	08.03.14 20:04	6
טעות שלי	IDAN_500	08.03.14 23:08	7

ohadeytan

חבר מתאריך 7.8.06
623 הודעות, 3 פידבק, 5 נקודות

19:49 04.03.14

1. בעיקרון אתה צריך לבדוק כמה פעמים הלולאות יתבצעו, וכמה פעולות בכל איטרציה
בתגובה להודעה מספר 0

תשים לב מה משפיע על מספר הריצות ומה לא (למשל הערך של a לא משפיע בכלל).
בפונקציה הראשונה:
הלולאה החיצונית תרוץ 5 פעמים בלבד כל פעם עם ערך x שקטן בחמישית n, זה קבוע לא משנה מהו n.
בכל ריצה היא מבצעת x פעולות, כלומר סה"כ:
n+4n/5+3n/5+2n/5+n/5
שזה סה"כ O(n) כמובן.
בפונקציה השניה מספר האיטרציות כבר תלוי בn והוא
n+n/5+n/25+...
אבל זה גם O(n)
בהצלחה

(מקווה שלא פיספסתי משהו)

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

danny444
חבר מתאריך 14.9.08
1982 הודעות, דרג אמינות חבר זה

19:58 04.03.14

2. לדעתי בשנייה זה O(N^2)
בתגובה להודעה מספר 1

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ohadeytan

חבר מתאריך 7.8.06
623 הודעות, 3 פידבק, 5 נקודות

20:02 04.03.14

3. מכתב:
בתגובה להודעה מספר 2

הלולאה הפנימית רצה n פעמים בפעם הראשונה זה נכון, אבל בריצה השנייה היא כבר רצה רק n/5 פעמים וכו' כמו שרשמתי.
גם הלולאה החיצונית לא רצה n פעמים אלא log(n) פעמים (כי כל פעם מחלקים ב5), לכן ניתוח גס היה נותן O של n*log(n)
אבל ניתוח מדוייק יותר כמו שעשיתי מראה שזה סכום שהוא לינארי ב n ולכן זה חסם יותר הדוק ומדוייק.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

IDAN_500
חבר מתאריך 11.12.03
2321 הודעות, דרג אמינות חבר זה

21:16 05.03.14

4. לא משנה
בתגובה להודעה מספר 1

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Fstyle
חבר מתאריך 24.5.05
357 הודעות, דרג אמינות חבר זה

08:55 08.03.14

5. כנראה שהשני זה NLOGN
בתגובה להודעה מספר 0

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

IDAN_500
חבר מתאריך 11.12.03
2321 הודעות, דרג אמינות חבר זה

20:04 08.03.14

6. הסיבוכיות היא לינארית, כנס להסבר...
בתגובה להודעה מספר 5

(1-n+n/5+n/5^2+n/5^3+...+n/5^(log5n =
תוציא n מחוץ לסוגריים, ותקבל בתוך הסוגריים סדרה הנדסית שהמנה היא 1/5, כלומר הסכום מתכנס למספר קבוע, ולכן הסיבוכיות היא לינארית.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

IDAN_500
חבר מתאריך 11.12.03
2321 הודעות, דרג אמינות חבר זה

23:08 08.03.14

7. טעות שלי
בתגובה להודעה מספר 6

זה לא בדיוק יצא מספר קבוע (תהיה תלוי ב n) והסכום הזה יהיה שווה ל -
5/4 * (n-1)/n כל זה כפול ה n שהיו מחוץ לסוגריים, ומפה קל לראות את הסיבוכיות הלינארית.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד