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

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

שאלה

נתון מערך A המכיל $\displaystyle n$ מספרים, כל אחד בתחום $\displaystyle [1,...,k]$‏ ($\displaystyle k$ מספר שלם כלשהו). רוצים לענות מספר רב של פעמים על שאלות מהסוג: בהינתן $\displaystyle a$ ו$\displaystyle b$ כלשהם, כמה מ$\displaystyle n$ האיברים בA נמצאים בתחום $\displaystyle [a,...,b]$? לצורך כך רוצים לכתוב שתי פונקציות:

1. Init מקבלת את המערך A והערך $\displaystyle k$, ומבצעת פעולות אתחול כלשהן.
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 בזמן $\displaystyle O(1)$.) הוסף משתנים גלובליים ופונקציות עזר כרצונך.

תשובה

הפתרון דומה מאד למיון ספירה. ראשית, הנה הפסוודו-קוד ל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. בניתוח מיון ספירה ראינו שהסיבוכיות היא $\displaystyle \Theta (n+k)$.

לאחר שאתחלנו את המערך 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

קל לראות שהסיבוכיות היא $\displaystyle O(1)$.