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

Cardcaptor: /* ข้อย่อย 3 */

2009-08-04T08:12:22Z

ข้อย่อย 3

158.108.183.136: /* ข้อย่อย 3 */

2009-08-04T08:11:57Z

ข้อย่อย 3

158.108.183.136: /* ข้อย่อย 3 */

2009-08-04T08:09:14Z

ข้อย่อย 3

158.108.183.136: /* ข้อย่อย 3 */

2009-08-04T08:08:57Z

ข้อย่อย 3

Cardcaptor: /* ข้อย่อย 3 */

2009-08-02T15:11:03Z

ข้อย่อย 3

Cardcaptor: /* ข้อย่อย 2 */

2009-08-02T15:08:36Z

ข้อย่อย 2

Aoy เมื่อ 08:44, 1 สิงหาคม 2552

2009-08-01T08:44:51Z

Aoy: /* ข้อย่อย 5 */

2009-08-01T08:40:10Z

ข้อย่อย 5

Aoy: /* ข้อย่อย 5 */

2009-08-01T08:39:19Z

ข้อย่อย 5

Aoy: /* ข้อย่อย 5 */

2009-08-01T08:38:11Z

ข้อย่อย 5

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 08:12, 4 สิงหาคม 2552
แถว 11:		แถว 11:

	== ข้อย่อย 3 ==		== ข้อย่อย 3 ==
		+	ข้อความนี้ไม่เป็นจริง
		+
	ให้ <math>f(n) = 2n \,</math> เราได้ว่า <math>f(n) = O(n) \,</math> แต่ <math>2^{f(n)} = 2^{2n} = 4^n \neq O(2^n) \,</math>		ให้ <math>f(n) = 2n \,</math> เราได้ว่า <math>f(n) = O(n) \,</math> แต่ <math>2^{f(n)} = 2^{2n} = 4^n \neq O(2^n) \,</math>

@@ แถว 11: / แถว 11: @@
 == ข้อย่อย 3 ==
-สมมติให้ <math>f(n) = O(g(n)) \,</math> แสดงว่ามีค่าคงที่ <math>c' > 0 \,</math> และ <math>n'_0 \,</math> ที่ทำให้ถ้า <math>n \geq n'_0 \,</math> แล้ว <math>f(n) \leq c' g(n) \,</math> ซึ่งหมายความว่า <math>2^{f(n)} \leq 2^{c' g(n)} = {2^{c'}}^{g(n)} \,</math> ด้วยเหตุนี้ <math>2^{f(n)} = O(2^{g(n)})</math> ด้วยเนื่องจากเราสามารถเลือก <math>c = 2^{c'} \,</math> และ <math>n_0 = n'_0 \,</math> ได้
+ให้ <math>f(n) = 2n \,</math> เราได้ว่า <math>f(n) = O(n) \,</math> แต่ <math>2^{f(n)} = 2^{2n} = 4^n \neq O(2^n) \,</math>
 == ข้อย่อย 4 ==

@@ แถว 11: / แถว 11: @@
 == ข้อย่อย 3 ==
-สมมติให้ <math>f(n) = O(g(n)) \,</math> แสดงว่ามีค่าคงที่ <math>c' > 0 \,</math> และ <math>n'_0 \,</math> ที่ทำให้ถ้า <math>n \geq n'_0 \,</math> แล้ว <math>f(n) \leq c' g(n) \,</math> ซึ่งหมายความว่า <math>2^{f(n)} \leq 2^{c' g(n)} = {2^{c'}}^{2^{g(n)}} \,</math> ด้วยเหตุนี้ <math>2^{f(n)} = O(2^{g(n)})</math> ด้วยเนื่องจากเราสามารถเลือก <math>c = 2^{c'} \,</math> และ <math>n_0 = n'_0 \,</math> ได้
+สมมติให้ <math>f(n) = O(g(n)) \,</math> แสดงว่ามีค่าคงที่ <math>c' > 0 \,</math> และ <math>n'_0 \,</math> ที่ทำให้ถ้า <math>n \geq n'_0 \,</math> แล้ว <math>f(n) \leq c' g(n) \,</math> ซึ่งหมายความว่า <math>2^{f(n)} \leq 2^{c' g(n)} = {2^{c'}}^{g(n)} \,</math> ด้วยเหตุนี้ <math>2^{f(n)} = O(2^{g(n)})</math> ด้วยเนื่องจากเราสามารถเลือก <math>c = 2^{c'} \,</math> และ <math>n_0 = n'_0 \,</math> ได้
 == ข้อย่อย 4 ==

@@ แถว 11: / แถว 11: @@
 == ข้อย่อย 3 ==
-สมมติให้ <math>f(n) = O(g(n)) \,</math> แสดงว่ามีค่าคงที่ <math>c' > 0 \,</math> และ <math>n'_0 \,</math> ที่ทำให้ถ้า <math>n \geq n'_0 \,</math> แล้ว <math>f(n) \leq c' g(n) \,</math> ซึ่งหมายความว่า <math>2^{f(n)} \leq 2^{c' g(n)} = 2^{c'} \cdot 2^{g(n)} \,</math> ด้วยเหตุนี้ <math>2^{f(n)} = O(2^{g(n)})</math> ด้วยเนื่องจากเราสามารถเลือก <math>c = 2^{c'} \,</math> และ <math>n_0 = n'_0 \,</math> ได้
+สมมติให้ <math>f(n) = O(g(n)) \,</math> แสดงว่ามีค่าคงที่ <math>c' > 0 \,</math> และ <math>n'_0 \,</math> ที่ทำให้ถ้า <math>n \geq n'_0 \,</math> แล้ว <math>f(n) \leq c' g(n) \,</math> ซึ่งหมายความว่า <math>2^{f(n)} \leq 2^{c' g(n)} = {2^{c'}}^{2^{g(n)}} \,</math> ด้วยเหตุนี้ <math>2^{f(n)} = O(2^{g(n)})</math> ด้วยเนื่องจากเราสามารถเลือก <math>c = 2^{c'} \,</math> และ <math>n_0 = n'_0 \,</math> ได้
 == ข้อย่อย 4 ==

@@ แถว 11: / แถว 11: @@
 == ข้อย่อย 3 ==
-สมมติให้ <math>f(n) = O(g(n)) \,</math> แสดงว่ามีค่าคงที่ <math>c > 0 \,</math> และ <math>n_0 \,</math> ที่ทำให้ถ้า <math>n \geq n_0 \,</math> แล้ว <math>f(n) \leq c g(n) \,</math> ซึ่งหมายความว่า <math>2^{f(n)} < 2^{c g(n)} = 2^c \cdot 2^{g(n)} \,</math>
+สมมติให้ <math>f(n) = O(g(n)) \,</math> แสดงว่ามีค่าคงที่ <math>c' > 0 \,</math> และ <math>n'_0 \,</math> ที่ทำให้ถ้า <math>n \geq n'_0 \,</math> แล้ว <math>f(n) \leq c' g(n) \,</math> ซึ่งหมายความว่า <math>2^{f(n)} \leq 2^{c' g(n)} = 2^{c'} \cdot 2^{g(n)} \,</math> ด้วยเหตุนี้ <math>2^{f(n)} = O(2^{g(n)})</math> ด้วยเนื่องจากเราสามารถเลือก <math>c = 2^{c'} \,</math> และ <math>n_0 = n'_0 \,</math> ได้
 == ข้อย่อย 4 ==

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 15:08, 2 สิงหาคม 2552
แถว 9:		แถว 9:

	จะได้ว่า <math> f(n)+ g(n) </math> คือ <math> n+n^2=O(n^2)</math>		จะได้ว่า <math> f(n)+ g(n) </math> คือ <math> n+n^2=O(n^2)</math>
		+
		+	== ข้อย่อย 3 ==
		+	สมมติให้ <math>f(n) = O(g(n)) \,</math> แสดงว่ามีค่าคงที่ <math>c > 0 \,</math> และ <math>n_0 \,</math> ที่ทำให้ถ้า <math>n \geq n_0 \,</math> แล้ว <math>f(n) \leq c g(n) \,</math> ซึ่งหมายความว่า <math>2^{f(n)} < 2^{c g(n)} = 2^c \cdot 2^{g(n)} \,</math>

	== ข้อย่อย 4 ==		== ข้อย่อย 4 ==

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 08:44, 1 สิงหาคม 2552
แถว 23:		แถว 23:

	จากข้างต้นจะให้ <math> c_2 = 1/c_1, n_2 = n_1 </math> ก็จะได้ว่า <math> g(n) = \Omega(f(n)) </math> เป็นจริง		จากข้างต้นจะให้ <math> c_2 = 1/c_1, n_2 = n_1 </math> ก็จะได้ว่า <math> g(n) = \Omega(f(n)) </math> เป็นจริง
		+
		+	== ข้อย่อย 6 ==
		+	ข้อความนี้ไม่เป็นจริง จะแสดงตัวอย่างขัดแย้ง ให้ <math> f(n)= 2^n </math> จะได้ว่า <math> f(n/2)=2^{n/2}=2^{(1/2)n} </math>
		+
		+	ซึ่ง <math> 2^n \neq \Theta (2^{(1/2)n}) </math>

@@ แถว 20: / แถว 20: @@
 จากที่รู้ว่า <math> f(n) = O(g(n)) </math> เป็นจริง นั่นคือ สำหรับจำนวนเต็มบวก <math> c_1, n_1 </math> บางตัว แล้ว <math> 0 \leq f(n) \leq (c_1(g(n))</math> จะเป็นจริง สำหรับทุก ๆ <math> n > n_1 </math>
-ต้องการแสดงว่า <math> g(n) = \Omega(f(n)) </math> นั่นคือต้องการจำนวนเต็มบวก <math> c_2, n_2 </math> บางตัว ที่ทำให้ <math> 0 \leq (c_2(f(n)) \leq g(n)</math> จะเป็นจริง สำหรับทุก ๆ <math> n > n_2 </math>
+ต้องการแสดงว่า <math> g(n) = \Omega(f(n)) </math> นั่นคือต้องการจำนวนเต็มบวก <math> c_2, n_2 </math> บางตัว ที่ทำให้ <math> 0 \leq (c_2(f(n)) \leq g(n)</math> เป็นจริง สำหรับทุก ๆ <math> n > n_2 </math>
 จากข้างต้นจะให้ <math> c_2 = 1/c_1, n_2 = n_1  </math> ก็จะได้ว่า <math> g(n) = \Omega(f(n)) </math> เป็นจริง

@@ แถว 18: / แถว 18: @@
 ข้อความนี้เป็นจริง จะทำการพิสูจน์
-จากที่รู้ว่า <math> f(n) = O(g(n)) </math> เป็นจริง นั่นคือ สำหรับจำนวนเต็มบวก <math> c_1, n_0^' </math> บางตัว แล้ว <math> 0 \leq f(n) \leq (c_1(g(n))</math> จะเป็นจริง สำหรับทุก ๆ <math> n > n_0^' </math>
+จากที่รู้ว่า <math> f(n) = O(g(n)) </math> เป็นจริง นั่นคือ สำหรับจำนวนเต็มบวก <math> c_1, n_1 </math> บางตัว แล้ว <math> 0 \leq f(n) \leq (c_1(g(n))</math> จะเป็นจริง สำหรับทุก ๆ <math> n > n_1 </math>
-ต้องการแสดงว่า <math> g(n) = \Omega(f(n)) </math> นั่นคือต้องการจำนวนเต็มบวก <math> c_2, n_0^'' </math> บางตัว ที่ทำให้ <math> 0 \leq (c_2(f(n)) \leq g(n)</math> จะเป็นจริง สำหรับทุก ๆ <math> n > n_0^'' </math>
+ต้องการแสดงว่า <math> g(n) = \Omega(f(n)) </math> นั่นคือต้องการจำนวนเต็มบวก <math> c_2, n_2 </math> บางตัว ที่ทำให้ <math> 0 \leq (c_2(f(n)) \leq g(n)</math> จะเป็นจริง สำหรับทุก ๆ <math> n > n_2 </math>
-จากข้างต้นจะให้ <math> c_2 = 1/c_1, n_0^'' = n_0^'  </math> ก็จะได้ว่า <math> g(n) = \Omega(f(n)) </math> เป็นจริง
+จากข้างต้นจะให้ <math> c_2 = 1/c_1, n_2 = n_1  </math> ก็จะได้ว่า <math> g(n) = \Omega(f(n)) </math> เป็นจริง

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 08:38, 1 สิงหาคม 2552
แถว 16:		แถว 16:

	== ข้อย่อย 5 ==		== ข้อย่อย 5 ==
−	~~อ.วัฒนา~~	+	ข้อความนี้เป็นจริง จะทำการพิสูจน์
		+
		+	จากที่รู้ว่า <math> f(n) = O(g(n)) </math> เป็นจริง นั่นคือ สำหรับจำนวนเต็มบวก <math> c_1, n_0^' </math> บางตัว แล้ว <math> 0 \leq f(n) \leq (c_1(g(n))</math> จะเป็นจริง สำหรับทุก ๆ <math> n > n_0^' </math>
		+
		+	ต้องการแสดงว่า <math> g(n) = \Omega(f(n)) </math> นั่นคือต้องการจำนวนเต็มบวก <math> c_2, n_0^'' </math> บางตัว ที่ทำให้ <math> 0 \leq (c_2(f(n)) \leq g(n)</math> จะเป็นจริง สำหรับทุก ๆ <math> n > n_0^'' </math>
		+
		+	จากข้างต้นจะให้ <math> c_2 = 1/c_1, n_0^'' = n_0^' </math> ก็จะได้ว่า <math> g(n) = \Omega(f(n)) </math> เป็นจริง