מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/אלגוריתמים למיון בזמן לינארי/תרגילים

שאילתות על מספר איברים בתחום

עריכה

שאלה

עריכה

נתון מערך A המכיל   מספרים, כל אחד בתחום  ‏ (  מספר שלם כלשהו). רוצים לענות מספר רב של פעמים על שאלות מהסוג: בהינתן   ו  כלשהם, כמה מ  האיברים בA נמצאים בתחום  ? לצורך כך רוצים לכתוב שתי פונקציות:

  1. Init מקבלת את המערך A והערך  , ומבצעת פעולות אתחול כלשהן.
  2. Range מקבלת שני מספרים a וb, ומחזירה כמה מאיברי A נמצאים בין שני המספרים.להלן דוגמה לשימוש אפשרי:
1	A = [1, 3, 2, 3, 3, 3, 15, 3]

	# Initializes whatever is needed
2	Init(A, 15)

	# Prints 8.
3	Print( Range(1, 16) )

	# Prints 1.
4	Print( Range(1, 1) )

	# Prints 1.
5	Print( Range(2, 2) )

	# Prints 7.
6	Print( Range(1, 14) )

אנא כתוב מימוש יעיל ככל האפשר לשתי הפונקציות, ונתח אותן. (נסה להגיע לכך שRange בזמן  .) הוסף משתנים גלובליים ופונקציות עזר כרצונך.

תשובה

עריכה

הפתרון דומה מאד למיון ספירה. ראשית, הנה הפסוודו-קוד לInit:

# A global array.
1	Count

Init(Values, k)
1	Count = Make-Array(k)

2	for i in [1, ..., k]
3		Count[i] = 0
	
4	for j in [1, ..., Length(Values))
5		value = Values[j]
6		++Count[value]
	
7	for i in [2, ..., k]
8		Count[i] = Count[i] + Count[i - 1]

המערך Count הוא משתנה גלובלי. הפונקציה Range מאתחלת אותו כך שהאיבר הi שלו מכיל את מספר האיברים הקטנים או שווים לi בA. בניתוח מיון ספירה ראינו שהסיבוכיות היא  .

לאחר שאתחלנו את המערך Count, הפונקציה Range פשוטה מאד. כל שעלינו לעשות הוא לחסר את מספר האיברים הקטנים מa ממספר האיברים הקטנים או שווים לb:

Range(a, b)
	# First find the number of values less than a.
1	if a == 1
2		less-than-a = 0
3	else if a - 1  Length(Count)
4		less-than-a = Count[a - 1]
5	else
6		less-than-a = Count[Length(Count)]

	# Now find the number of values less than or equal to b.

7	if b  Length(Count)
8		at-most-b = Count[b] 
9	else
10		at-most-b = Count[Length(Count)]
	
	# The answer is obviously the difference between the two.
11	return at-most-b - less-than-a

קל לראות שהסיבוכיות היא  .