418531 ภาคต้น 2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ 8 - ประวัติรุ่นแก้ไข

Cardcaptor เมื่อ 17:39, 4 กันยายน 2552

2009-09-04T17:39:19Z

Cardcaptor เมื่อ 17:26, 4 กันยายน 2552

2009-09-04T17:26:15Z

Cardcaptor เมื่อ 15:09, 4 กันยายน 2552

2009-09-04T15:09:42Z

Cardcaptor: หน้าที่ถูกสร้างด้วย 'อัลกอริทึมสำหรับนับอินเวอร์ชันสำคัญนั้นเหมือนก…'

2009-09-04T15:09:03Z

หน้าที่ถูกสร้างด้วย 'อัลกอริทึมสำหรับนับอินเวอร์ชันสำคัญนั้นเหมือนก…'

หน้าใหม่

อัลกอริทึมสำหรับนับอินเวอร์ชันสำคัญนั้นเหมือนกับอัลกอริทึมการนับอินเวอร์ชันธรรมดาเกือบทุกประการ กล่าวคือเราจะนับอินเวอร์ชันสำคัญไปพร้อมๆ กับทำ merge sort แต่สำหรับการนับอินเวอร์ชันสำคัญ เราจะปรับปรุงฟังก์ชัน merge เล็กน้อยดังต่อไปนี้

ในฟังก์ชัน merge เรามีตัวแปร <math>i_x \,</math> และ <math>i_y \,</math> เพื่อบอกตำแหน่งของสมาชิกในอะเรย์ <math>x \,</math> และ <math>y \,</math> ที่ยังไม่ได้นำไปใส่อะเรย์ <math>z \,</math> ซึ่งเป็นผลลัพธ์ แต่ในอัลกอริทึมสำหรับการนับอินเวอร์ชันสำคัญ เราจะให้มีตัวแปร <math>i_{2y} \,</math> ซึ่งเราจะนิยามให้เป็นจำนวนเต็มที่มากที่สุดที่ทำให้ <math>x[i_x] > 2y[i_{2y}] \,</math> สังเกตว่า <math>i_{2y}</math> มีค่าเท่ากับจำนวนสมาชิกของอะเรย์ <math>y \,</math> ที่มีค่าน้อยกว่า <math>x[i_x] / 2 \,</math> ด้วยเหตุนี้ เมื่อเรานำสมาชิกจาก <math>x \,</math> ไปใส่ใน </math>z \,</math> เราสามารถนำ <math>i_{2y} \,</math> ไปบวกเข้ากับจำนวนอินเวอร์ชันสำคัญได้ เมื่อทำเช่นนี้ไปจนครบสมาชิกทุกตัวของ <math>x \,</math> เราจะได้จำนวนอินเวอร์ชันสำคัญที่เลขตัวหน้าอยู่ใน <math>x \,</math> และเลขตัวหลังอยู่ใน <math>y \,</math>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 17:39, 4 กันยายน 2552
แถว 65:		แถว 65:
	}		}
	</geshi>		</geshi>
		+
		+	เวลาการทำงานของฟังก์ชัน Merge ใหม่คือ <math>O(n) \,</math> เหมือนเดิม เนื่องจากลูป
		+	<geshi lang="c">
		+	while (i2y < ny) and (x[ix] > 2*y[i2y+1]) do
		+	i2y = i2y + 1
		+	</geshi>
		+	จะเริ่มต้นทำงานรวมทั้งหมดไม่เกิน <math>n_x \,</math> ครั้ง (เนื่องจากมันจะเริ่มต้นทำงานทุกครั้งที่ <math>x[i_x] \,</math> จะถูกนำไปใส่ยังอะเรย์ <math>z\,</math>) และคำสั่ง <code>i2y = i2y + 1</code> จะทำงานไม่เกิน <math>n_y \,</math> ครั้งเนื่องจาก <math>i_{2y} \leq n_y \,</math> ฉะนั้นเวลาที่เราใช้ทั้งหมดกับการจัดการค่า <math>i_{2y} \,</math> ไม่เกิน <math>O(n_x + n_y) = O(n) \,</math>
		+
		+	ด้วยเหตุนี้เราจึงสามารถนับอินเวอร์ชันสำคัญได้ในเวลา <math>O(n \log n)\,</math>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 17:26, 4 กันยายน 2552
แถว 2:		แถว 2:

	ในฟังก์ชัน merge เรามีตัวแปร <math>i_x \,</math> และ <math>i_y \,</math> เพื่อบอกตำแหน่งของสมาชิกในอะเรย์ <math>x \,</math> และ <math>y \,</math> ที่ยังไม่ได้นำไปใส่อะเรย์ <math>z \,</math> ซึ่งเป็นผลลัพธ์ แต่ในอัลกอริทึมสำหรับการนับอินเวอร์ชันสำคัญ เราจะให้มีตัวแปร <math>i_{2y} \,</math> ซึ่งเราจะนิยามให้เป็นจำนวนเต็มที่มากที่สุดที่ทำให้ <math>x[i_x] > 2y[i_{2y}] \,</math> สังเกตว่า <math>i_{2y}</math> มีค่าเท่ากับจำนวนสมาชิกของอะเรย์ <math>y \,</math> ที่มีค่าน้อยกว่า <math>x[i_x] / 2 \,</math> ด้วยเหตุนี้ เมื่อเรานำสมาชิกจาก <math>x \,</math> ไปใส่ใน <math>z \,</math> เราสามารถนำ <math>i_{2y} \,</math> ไปบวกเข้ากับจำนวนอินเวอร์ชันสำคัญได้ เมื่อทำเช่นนี้ไปจนครบสมาชิกทุกตัวของ <math>x \,</math> เราจะได้จำนวนอินเวอร์ชันสำคัญที่เลขตัวหน้าอยู่ใน <math>x \,</math> และเลขตัวหลังอยู่ใน <math>y \,</math>		ในฟังก์ชัน merge เรามีตัวแปร <math>i_x \,</math> และ <math>i_y \,</math> เพื่อบอกตำแหน่งของสมาชิกในอะเรย์ <math>x \,</math> และ <math>y \,</math> ที่ยังไม่ได้นำไปใส่อะเรย์ <math>z \,</math> ซึ่งเป็นผลลัพธ์ แต่ในอัลกอริทึมสำหรับการนับอินเวอร์ชันสำคัญ เราจะให้มีตัวแปร <math>i_{2y} \,</math> ซึ่งเราจะนิยามให้เป็นจำนวนเต็มที่มากที่สุดที่ทำให้ <math>x[i_x] > 2y[i_{2y}] \,</math> สังเกตว่า <math>i_{2y}</math> มีค่าเท่ากับจำนวนสมาชิกของอะเรย์ <math>y \,</math> ที่มีค่าน้อยกว่า <math>x[i_x] / 2 \,</math> ด้วยเหตุนี้ เมื่อเรานำสมาชิกจาก <math>x \,</math> ไปใส่ใน <math>z \,</math> เราสามารถนำ <math>i_{2y} \,</math> ไปบวกเข้ากับจำนวนอินเวอร์ชันสำคัญได้ เมื่อทำเช่นนี้ไปจนครบสมาชิกทุกตัวของ <math>x \,</math> เราจะได้จำนวนอินเวอร์ชันสำคัญที่เลขตัวหน้าอยู่ใน <math>x \,</math> และเลขตัวหลังอยู่ใน <math>y \,</math>
		+
		+	เมื่อเรานำสมาชิกตัวหนึ่งของ <math>x \,</math> ไปใส่ใน <math>z \,</math> เราจะเพิ่มค่า <math>i_x \,</math> ขึ้นหนึ่ง ซึ่งนั่นหมายความว่าเราจะต้องเปลี่ยน <math>i_{2y} \,</math> ให้สอดคล้องกับ <math>x[i_x] \,</math> ค่าใหม่ การเปลี่ยน <math>i_{2y} \,</math> นี้ทำได้โดยเพิ่ม <math>i_{2y} \,</math> ไปเรื่อยๆ จนกระทั่ง <math>x[i_x] \leq 2y[i_{2y}+1]\,</math>
		+
		+	เราสามารถนำแนวความคิดข้างบนมาเขียนเป็น pseudocode ได้ดังต่อไปนี้
		+
		+	<geshi lang="c">
		+	Merge(x, nx, y, ny)
		+	{
		+	สร้างอะเรย์ z ขนาด nx + ny
		+
		+	ix = 1
		+	iy = 1
		+	iz = 1
		+
		+	i2y = 0
		+	while (i2y < ny) and (x[ix] > 2*y[i2y+1]) do
		+	i2y = i2y + 1
		+
		+	inversion_count = 0 // จำนวนอินเวอร์ชันสำคัญ
		+
		+	while (ix <= nx) and (y <= ny) do
		+	{
		+	if x[ix] < y[iy] then
		+	{
		+	z[iz] = x[ix]
		+	ix = ix + 1
		+	iz = iz + 1
		+	// เพิ่มจำนวนอินเวอร์ชันสำคัญขึ้น i2y
		+	inversion_count = inversion_count + i2y
		+	// ปรับค่า i2y ใหม่
		+	while (i2y < ny) and (x[ix] > 2*y[i2y+1]) do
		+	i2y = i2y + 1
		+	}
		+	else
		+	{
		+	z[iz] = y[iy]
		+	iy = iy + 1
		+	iz = iz + 1
		+	}
		+	}
		+
		+	while ix <= nx do
		+	{
		+	z[iz] = x[ix]
		+	ix = ix + 1
		+	iz = iz + 1
		+	// เพิ่มจำนวนอินเวอร์ชันสำคัญขึ้น i2y
		+	inversion_count = inversion_count + i2y
		+	// ปรับค่า i2y ใหม่
		+	while (i2y < ny) and (x[ix] > 2*y[i2y+1]) do
		+	i2y = i2y + 1
		+	}
		+
		+	while iy <= ny do
		+	{
		+	z[iz] = y[iy]
		+	iy = iy + 1
		+	iz = iz + 1
		+	}
		+
		+	return inversion_count, z
		+	}
		+	</geshi>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 15:09, 4 กันยายน 2552
แถว 1:		แถว 1:
	อัลกอริทึมสำหรับนับอินเวอร์ชันสำคัญนั้นเหมือนกับอัลกอริทึมการนับอินเวอร์ชันธรรมดาเกือบทุกประการ กล่าวคือเราจะนับอินเวอร์ชันสำคัญไปพร้อมๆ กับทำ merge sort แต่สำหรับการนับอินเวอร์ชันสำคัญ เราจะปรับปรุงฟังก์ชัน merge เล็กน้อยดังต่อไปนี้		อัลกอริทึมสำหรับนับอินเวอร์ชันสำคัญนั้นเหมือนกับอัลกอริทึมการนับอินเวอร์ชันธรรมดาเกือบทุกประการ กล่าวคือเราจะนับอินเวอร์ชันสำคัญไปพร้อมๆ กับทำ merge sort แต่สำหรับการนับอินเวอร์ชันสำคัญ เราจะปรับปรุงฟังก์ชัน merge เล็กน้อยดังต่อไปนี้

−	ในฟังก์ชัน merge เรามีตัวแปร <math>i_x \,</math> และ <math>i_y \,</math> เพื่อบอกตำแหน่งของสมาชิกในอะเรย์ <math>x \,</math> และ <math>y \,</math> ที่ยังไม่ได้นำไปใส่อะเรย์ <math>z \,</math> ซึ่งเป็นผลลัพธ์ แต่ในอัลกอริทึมสำหรับการนับอินเวอร์ชันสำคัญ เราจะให้มีตัวแปร <math>i_{2y} \,</math> ซึ่งเราจะนิยามให้เป็นจำนวนเต็มที่มากที่สุดที่ทำให้ <math>x[i_x] > 2y[i_{2y}] \,</math> สังเกตว่า <math>i_{2y}</math> มีค่าเท่ากับจำนวนสมาชิกของอะเรย์ <math>y \,</math> ที่มีค่าน้อยกว่า <math>x[i_x] / 2 \,</math> ด้วยเหตุนี้ เมื่อเรานำสมาชิกจาก <math>x \,</math> ไปใส่ใน </math>z \,</math> เราสามารถนำ <math>i_{2y} \,</math> ไปบวกเข้ากับจำนวนอินเวอร์ชันสำคัญได้ เมื่อทำเช่นนี้ไปจนครบสมาชิกทุกตัวของ <math>x \,</math> เราจะได้จำนวนอินเวอร์ชันสำคัญที่เลขตัวหน้าอยู่ใน <math>x \,</math> และเลขตัวหลังอยู่ใน <math>y \,</math>	+	ในฟังก์ชัน merge เรามีตัวแปร <math>i_x \,</math> และ <math>i_y \,</math> เพื่อบอกตำแหน่งของสมาชิกในอะเรย์ <math>x \,</math> และ <math>y \,</math> ที่ยังไม่ได้นำไปใส่อะเรย์ <math>z \,</math> ซึ่งเป็นผลลัพธ์ แต่ในอัลกอริทึมสำหรับการนับอินเวอร์ชันสำคัญ เราจะให้มีตัวแปร <math>i_{2y} \,</math> ซึ่งเราจะนิยามให้เป็นจำนวนเต็มที่มากที่สุดที่ทำให้ <math>x[i_x] > 2y[i_{2y}] \,</math> สังเกตว่า <math>i_{2y}</math> มีค่าเท่ากับจำนวนสมาชิกของอะเรย์ <math>y \,</math> ที่มีค่าน้อยกว่า <math>x[i_x] / 2 \,</math> ด้วยเหตุนี้ เมื่อเรานำสมาชิกจาก <math>x \,</math> ไปใส่ใน <math>z \,</math> เราสามารถนำ <math>i_{2y} \,</math> ไปบวกเข้ากับจำนวนอินเวอร์ชันสำคัญได้ เมื่อทำเช่นนี้ไปจนครบสมาชิกทุกตัวของ <math>x \,</math> เราจะได้จำนวนอินเวอร์ชันสำคัญที่เลขตัวหน้าอยู่ใน <math>x \,</math> และเลขตัวหลังอยู่ใน <math>y \,</math>