רוטר - חידה פשוטה יחסית,

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

"חידה פשוטה יחסית,"

גירסת הדפסה

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

אשכול מספר 15465

Deuce
חבר מתאריך 1.9.08
6225 הודעות

20:33 09.09.09

חידה פשוטה יחסית,

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

שתף

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

האשכול	מחבר	תאריך כתיבה	מספר
הקטנים ממה? X= מK עצמו?	ronen333	18.09.09 00:25	1
k המספרים הקטנים.	Deuce	18.09.09 00:31	2
פתרון.	Deuce	18.09.09 19:32	3

ronen333
חבר מתאריך 20.2.03
6069 הודעות

00:25 18.09.09

1. הקטנים ממה? X= מK עצמו?
בתגובה להודעה מספר 0

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

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

Deuce
חבר מתאריך 1.9.08
6225 הודעות

00:31 18.09.09

2. k המספרים הקטנים.
בתגובה להודעה מספר 1

אם נניח k = 5 אז את 5 המספרים הקטנים.
אם אגב לא באופן ממויין אפשר יותר יעיל

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

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

Deuce
חבר מתאריך 1.9.08
6225 הודעות

19:32 18.09.09

3. פתרון.
בתגובה להודעה מספר 0

אפשרות א' - הפיכת המערך לערימת מינימום בינארית (O(n, הכנסת המינימום לעץ מאוזן כלשהו (O(1). ביצוע k איטרציות במהלכן אנו קוראים כל פעם ל-min על העץ ומכניסים את שני בניו מהערימה לתוך העץ. זה עולה לנו O(klog k). נשים לב כמובן כי העץ מסודר לפי ערכי המפתחות אשר מצביעים בין היתר לצמתים המתאימים בערימה.
אפשרות ב' - קריאה ל-Select(k) שמחזירה את האיבר ה-kי במערך (O(n, סריקת המערך והכנסת כל האיברים הקטנים מהאיבר שהוחזר לתוך מערך חדש (O(n)). מיון המערך החדש בעזרת למשל mergeSort - זה עולה klog k.

סה"כ:
O(n + klog k)

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

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