רוטר - שאלה קצרה לגבי מבני נתונים (ערימה)

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

"שאלה קצרה לגבי מבני נתונים (ערימה)"

גירסת הדפסה

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

אשכול מספר 10723

eminem
חבר מתאריך 14.11.03
4348 הודעות, 1 פידבק, -2 נקודות

20:19 02.06.12

שאלה קצרה לגבי מבני נתונים (ערימה)

יש לי את השאלה הבאה
לפי מבנה הערימה ידוע כי הוצאה מערימה זה log n
אבל איך אני יכול להוכיח שהטענה של מוטי היא שגויה??

תודה מראש

שתף

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

האשכול	מחבר	תאריך כתיבה	מספר
אתה צריך להבין מאיפה ה-Logn המקורי	CaTz	02.06.12 23:56	1
אתה מובן במאה אחוז, רק עוד משהו קטן	eminem	03.06.12 00:29	2
אם הוא מצליח לעשות Heapify בזמן ריצה קטן יותר	CaTz	03.06.12 09:40	4
ממה שאני זוכר	D-KinG	03.06.12 00:57	3
תוכיח בשלילה.	Yariv-H	04.06.12 23:55	5
אני לא זוכר יותר מדי, אבל לא נראה לי שזו	VeNom	05.06.12 08:30	6
אתה צודק...	zbengg	05.06.12 21:17	7
אתה צודק בכוונתך אולם	ShocKi	07.06.12 21:01	8
שמע	VeNom	07.06.12 23:34	10
האמת שראיתי את התשובה הבא ב-stackoverflow	eminem	07.06.12 23:49	11
אם תמצא דרך לבצע heapify בפחות מ logn	ShocKi	15.06.12 10:47	12
בדיוק ככה המרצה שלנו הוכיח... תודה רבה	eminem	07.06.12 21:26	9
:) לא מאמין שיכנסו ליותר מיזה במסגרת תרגיל בקורס :)	Yariv-H	16.06.12 09:50	13

CaTz
חבר מתאריך 2.10.04
14537 הודעות, דרג אמינות חבר זה

23:56 02.06.12

1. אתה צריך להבין מאיפה ה-Logn המקורי
בתגובה להודעה מספר 0

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

מקווה שהייתי מובן :|

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

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

eminem
חבר מתאריך 14.11.03
4348 הודעות, 1 פידבק, -2 נקודות

00:29 03.06.12

2. אתה מובן במאה אחוז, רק עוד משהו קטן
בתגובה להודעה מספר 1

ידוע לי שה-log n נובע מה-Heapify ומעצם הגדרות של ערימה (לפי מודולציה של עץ בינארי) שזהו עץ מלא (נראה לי ככה קוראים לזה) שלכל קודקוד חייב להיות שני בנים אלא אם כן מדובר ברמה האחת לפני האחרונה ששם לא הכל חייב להתמלא
לכן ה-Heapify עובר log n

אבל השאלה היא אם ההסבר הזה מסביר מדוע אין מצב שבעולם שהוא יממש את זה בשורש שך לוג n ?

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

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

CaTz
חבר מתאריך 2.10.04
14537 הודעות, דרג אמינות חבר זה

09:40 03.06.12

4. אם הוא מצליח לעשות Heapify בזמן ריצה קטן יותר
בתגובה להודעה מספר 2

אתה סותר את התכונה של הערימה שגובה העץ הוא logn.
משהו כזה

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

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

D-KinG
חבר מתאריך 8.6.02
3490 הודעות, דרג אמינות חבר זה

00:57 03.06.12

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

הדרך לתקוף את הדברים האלה זה בדרכ לסתור את זה שבשביל למיין מערך אתה צריך לפחות nlogn
אם היית יכול לעשות את מה שמוטי טוען, היית יכול לקחת מערך, לעשות ממנו ערימה ב-n, ואחרי זה לעשות heapsort בפחות מ-nlogn (אם באמת אני זוכר נכון את הסיבוכיות של כל הדברים האלו..)

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

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

Yariv-H

חבר מתאריך 24.3.02
5856 הודעות, 1 פידבק, 2 נקודות

23:55 04.06.12

5. תוכיח בשלילה.
בתגובה להודעה מספר 0

תניח שמוטי יכול לעשות את זה בשורש לוג N
תראה שלהוציא את האיבר לוקח o(1)
תניח שהוא יכול לסדר את הערימה ב שורש logn
ותראה שבשביל לסדר אותה צריך logn ע"י היפיאיי , סתירה.

http://coursebooks.cs.huji.ac.il/wikis/MediaWiki/coursebooks/index.php/%D7%9E%D7%91%D7%A0%D7%99_%D7%A0%D7%AA%D7%95%D7%A0%D7%99%D7%9D_%D7%AA%D7%A9%D7%A1%22%D7%98/%D7%94%D7%A8%D7%A6%D7%90%D7%95%D7%AA/%D7%94%D7%A8%D7%A6%D7%90%D7%94_6

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

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

VeNom

חבר מתאריך 7.6.02
7922 הודעות, 1 פידבק, 2 נקודות

08:30 05.06.12

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

הדרך להפריך את זה.
ואם מחר אני אמצא אלגוריתם יותר יעיל מ heapify שאף אחד לא חשב עליו?
אני לא זוכר שמישהו הוכיח שזו הדרך המהירה ביותר האפשרית.
אם אני זוכר נכון צריך להישען על עוגן שאין מיון השוואה שיכול לרוץ מתחת ל nlogn על מערך בגודל n.
בהנחה והיה אפשר לבצע הוצאת מקסימום בשורש לוג אן,יכולת למיין קולקציה בגודל N בסיבוכיות של

n*sqrt(log(n))

וזה לא אפשרי כי יש הוכחה שאי אפשר לבצע מיון השוואתי בפחות מזה.

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

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

zbengg
חבר מתאריך 24.9.08
2300 הודעות, דרג אמינות חבר זה

21:17 05.06.12

7. אתה צודק...
בתגובה להודעה מספר 6

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

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

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

ShocKi

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

21:01 07.06.12

8. אתה צודק בכוונתך אולם
בתגובה להודעה מספר 6

ערכתי לאחרונה בתאריך 07.06.12 בשעה 21:07 בברכה, ShocKi

אני חושש שאתה לא תמצא אלגוריתם שמבצע heapify ב o(logn) 'או קטן', כי אם תמצא כזה.. ניתן יהיה להשתמש בו כדי לבצע מיון ערמה ב o(nlogn) וזו סתירה לחסם תחתון למיון השוואות.

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

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

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

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

VeNom

חבר מתאריך 7.6.02
7922 הודעות, 1 פידבק, 2 נקודות

23:34 07.06.12

10. שמע
בתגובה להודעה מספר 8

במקרה של מיון השוואתי יש הוכחה שלמה שאי אפשר לבצע מיון השוואתי בפחות מ nlogn.
במקרה של heapify אני לא זוכר שיש הוכחה כזו(אולי אני טועה).כלומר מחר אולי חבר שלך ימצא דרך מהפכנית לבצע heapify בצורה יותר יעילה ולכן לא נראה לי שזה הכיוון(אם כי אני חלוד..כבר שנתיים שכל מה שאני בערך זוכר זה ליסט ומערך )

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

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

eminem
חבר מתאריך 14.11.03
4348 הודעות, 1 פידבק, -2 נקודות

23:49 07.06.12

11. האמת שראיתי את התשובה הבא ב-stackoverflow
בתגובה להודעה מספר 10

מישהו רשם לי שאילו באמת יכלת לבצע את מה שמוטי אומר (שם בפורום קראתי לו ג'ימס )
הרי ש-heap sort יהיה יותר יעיל מ- O(nlogn וכמו שאמרת לגבי ההוכחה שאי אפשר לבצע מיון השוואותי בפחות מ-nlogn

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

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

ShocKi

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

10:47 15.06.12

12. אם תמצא דרך לבצע heapify בפחות מ logn
בתגובה להודעה מספר 10

אני אוכל למיין מערך בפחות מ nlogn ולכן אוכל לפרוץ את החסם התחתון של מיון השוואות.

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

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

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

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

eminem
חבר מתאריך 14.11.03
4348 הודעות, 1 פידבק, -2 נקודות

21:26 07.06.12

9. בדיוק ככה המרצה שלנו הוכיח... תודה רבה
בתגובה להודעה מספר 5

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

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

Yariv-H

חבר מתאריך 24.3.02
5856 הודעות, 1 פידבק, 2 נקודות

09:50 16.06.12

13. :) לא מאמין שיכנסו ליותר מיזה במסגרת תרגיל בקורס :)
בתגובה להודעה מספר 9

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

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

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