רוטר - סיבוכיות זמן ריצה C

יומן פעילות	לוח שנה	מבזקי חדשות	תקנון	RSS	כותרות	כותרות לפי תגובה	ניקוי קוקיז	IP	להורדת אפליקציה
eBay	AliExpress	GearBest	Amazon	Booking	Kiwi	SkyScanner	Trip Advisor

"סיבוכיות זמן ריצה C - שאלה כללית.."

גירסת הדפסה

קבוצות דיון פיתוח, תיכנות ובניית אתרים נושא #10266	מנהל סגן המנהל מפקח Winner צל"ש מומחה

אשכול מספר 10266

ShocKi

חבר מתאריך 19.3.02
20171 הודעות, 10 פידבק, 17 נקודות

22:22 10.02.11

סיבוכיות זמן ריצה C - שאלה כללית..

מישהו יכול להסביר לי מתי הסיבוכיות היא log?
אני לא מצליח להבין איך אני מבין בין log למשהו אחר..
אני שם לב שבהרבה פעמים הסיבוכיות log היא של לולאת while אבל ברור לי שזה לא תמיד ככה...

מתי זה log?

קאש-באק ישראלי: https://www.cashback.co.il/?uref=33330
קאשבק לAsos ואמזון דרך Ebates: https://goo.gl/MX87Y7 - מקבלים 10$ לאחר שימוש ראשון.

שתף

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

האשכול	מחבר	תאריך כתיבה	מספר
מכתב	ldan192	11.02.11 00:10	1
למה? איך אתה רואה את זה...	ShocKi	11.02.11 21:29	2
כי...	ldan192	11.02.11 21:52	3
תודה :)	ShocKi	13.02.11 02:52	6
אם תעטוף בלולאה כפולה...	ldan192	13.02.11 20:38	7
את זה אני יודע..	ShocKi	13.02.11 23:41	8
אין הבדל. פה ה-log בבסיס 3, שם בבסיס 2	ldan192	13.02.11 23:52	9
תודה רבה	ShocKi	14.02.11 01:33	11
יש לי PDF מצויין לנושא הזה:	akoka2	12.02.11 09:17	4
תודה אבל ביומיים שלפני המבחן	ShocKi	13.02.11 02:51	5
ממליץ לקרוא את הספר של קורמן	Webmonster	14.02.11 00:15	10

ldan192
חבר מתאריך 14.9.08
95119 הודעות

00:10 11.02.11

1. מכתב
בתגובה להודעה מספר 0

פשוט מאוד, למשל:

void fun(int a) {
int sum = 0;
while (!(a /= 2))
sum += a;
}

אתה מבצע loga~ בבסיס 2 צעדי לולאה
למשל עבור קלט 16 - מריץ
16, 8, 4, 2, 1

בברכה,
עידן

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

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

ShocKi

חבר מתאריך 19.3.02
20171 הודעות, 10 פידבק, 17 נקודות

21:29 11.02.11

2. למה? איך אתה רואה את זה...
בתגובה להודעה מספר 1

ברור לי שזה עובד לפי ספירת סיבובים..
למשל לולאה שרצה מ 1 עד n אז הסיבוכיות היא n.
ולולאה שרצה מ 1 עד 10 אז זה 1.
אבל אני לא מבין את העיקריון של הסיבוכיות כאשר לולאה רצה למשל עד n/2 או דברים בסגנון הזה...

איך אתם מזהים את זה?

קאש-באק ישראלי: https://www.cashback.co.il/?uref=33330
קאשבק לAsos ואמזון דרך Ebates: https://goo.gl/MX87Y7 - מקבלים 10$ לאחר שימוש ראשון.

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

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

ldan192
חבר מתאריך 14.9.08
95119 הודעות

21:52 11.02.11

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

נניח שתעשה n איטרציות בסה"כ...
כלומר לקחת מספר (y), חילקת אותו n פעמים עד שהוא התאפס.
כלומר, y=2^n (כי אם תחלק את y ב-2 n+1~ פעמים - המספר מתאפס) ולכן ((n=teta(log2(y

בברכה,
עידן

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

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

ShocKi

חבר מתאריך 19.3.02
20171 הודעות, 10 פידבק, 17 נקודות

02:52 13.02.11

6. תודה :)
בתגובה להודעה מספר 3

אתה יכול לתת דוגמא למתי זה יהיה nlogn... חוץ מהמקרה שאתה מפעיל על מה שכתבת עכשיו לולאה חיצונית שתרוץ עד n.

קאש-באק ישראלי: https://www.cashback.co.il/?uref=33330
קאשבק לAsos ואמזון דרך Ebates: https://goo.gl/MX87Y7 - מקבלים 10$ לאחר שימוש ראשון.

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

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

ldan192
חבר מתאריך 14.9.08
95119 הודעות

20:38 13.02.11

7. אם תעטוף בלולאה כפולה...
בתגובה להודעה מספר 6

for (int i=0; i<n; ++i)
for (j=1; j<n; j*=2)
do_somthing_in_O(1);

כל לולאה פנימית (j) לוקחת logn, כמו שהסברתי מקודם,
הלולאה החיצונית - n פעמים. סה"כ n*logn

בברכה,
עידן

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

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

ShocKi

חבר מתאריך 19.3.02
20171 הודעות, 10 פידבק, 17 נקודות

23:41 13.02.11

8. את זה אני יודע..
בתגובה להודעה מספר 7

(רשמתי חוץ מהמקרה הזה)...

מה תהייה הסיבוכיות במקרה הזה?

for (int i=0; i<n; ++i)
for (j=1; j<n; j*=3)
do_somthing_in_O(1);

קאש-באק ישראלי: https://www.cashback.co.il/?uref=33330
קאשבק לAsos ואמזון דרך Ebates: https://goo.gl/MX87Y7 - מקבלים 10$ לאחר שימוש ראשון.

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

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

ldan192
חבר מתאריך 14.9.08
95119 הודעות

23:52 13.02.11

9. אין הבדל. פה ה-log בבסיס 3, שם בבסיס 2
בתגובה להודעה מספר 8

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

בברכה,
עידן

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

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

ShocKi

חבר מתאריך 19.3.02
20171 הודעות, 10 פידבק, 17 נקודות

01:33 14.02.11

11. תודה רבה
בתגובה להודעה מספר 9

קאש-באק ישראלי: https://www.cashback.co.il/?uref=33330
קאשבק לAsos ואמזון דרך Ebates: https://goo.gl/MX87Y7 - מקבלים 10$ לאחר שימוש ראשון.

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

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

akoka2

דרג אמינות חבר זה

09:17 12.02.11

4. יש לי PDF מצויין לנושא הזה:
בתגובה להודעה מספר 0

Beginning Algorithms
תוכל לראות פה קצת מה הוא מכיל:
http://www.amazon.com/Beginning-Algorithms-Wrox-Guides/dp/0764596748
אני לא סגור על זה שהספר מכסה את סימן לנדאו(Big O Notation):
http://en.wikipedia.org/wiki/Big_O_notation

הינה הלינק להורדה:
http://www.zshare.net/download/864473399e647310/

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

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

ShocKi

חבר מתאריך 19.3.02
20171 הודעות, 10 פידבק, 17 נקודות

02:51 13.02.11

5. תודה אבל ביומיים שלפני המבחן
בתגובה להודעה מספר 4

אין לי זמן לקרוא ספרים :|

קאש-באק ישראלי: https://www.cashback.co.il/?uref=33330
קאשבק לAsos ואמזון דרך Ebates: https://goo.gl/MX87Y7 - מקבלים 10$ לאחר שימוש ראשון.

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

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

Webmonster
חבר מתאריך 21.4.02
2499 הודעות, דרג אמינות חבר זה

00:15 14.02.11

10. ממליץ לקרוא את הספר של קורמן
בתגובה להודעה מספר 0

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

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