ช่วยโจทย์เรื่อง ฟังก์ชั่น หน่อยครับ

[Pich]

T(n) = 3T(n/2)+C
โดยที่ c เป็นค่าคงตัว
ให้ หา T(n) ที่ไม่ติดฟังก์ชั่น T

อยากรู้ก็เมล์ไปถาม อ.ซึง สิ

[M@gpie]

พอดีเห็นคุณ <เสริม> พูดถึงอ.ซึง เลยนึกขึ้นได้ไปค้นๆมา เห็นแต่ที่คล้ายๆนะครับ
ความสัมพันธ์ recurrence ของ Binary search เป้นดังนี้
T(n)=T(n/2)+C₂
ให้ T(1)=C₁
solving the recuurence relation ดังนี้
T(n)
= C₂+T(n/2)
= C₂+ C₂ +T(n/4)
= C₂+ C₂+ C₂T(n/8)
... ลองแทนความสัมพันธ์ไปเรื่อยๆจะได้หน้าตาแบบนี้
T(n)=i C₂ +T(n/2ⁱ)
เมื่อ 2ⁱ=n จะได้ว่า i=log₂n
แทนค่า i ลงไปจะได้ว่า
T(n)=(log₂n)C₂ +T(1)=C₂(log₂n)+C₁
เป็นปัญหาด้านคอมพิวเตอร์นะครับอยู่ในส่วน Alglorithm

[gon]

ต้องบอกโดเมนกับเรนจ์มาด้วยครับ. เช่น จาก จำนวนจริง ฎจำนวนจริง, จำนวนนับ ฎ จำนวนนับ เป็นต้น.

[alpha]

อ๊ากกก ขั้อนี้คิดไม่ออกเลย คิดได้ไงเนี่ยยยย

[M@gpie]

อ่า ก็ ไปดูในหนังสือมาอ่ะ ไม่ได้คิดเองเหมือนกัน ยังไมได้เรียนเรื่อง recurence relation เลย อยู่ใน discrete math อ่ะ

[gon]

ถ้าเลียนแบบวิธีที่น้อง M@pie แสดงมาก็จะได้ ดังนี้ครับ. ถ้าให้ T(1) = C จะได้ว่า T(n) = [ (C₁ + 2C)3^log₂n - C₁ ] /2
note : ใช้สูตรอนุกรมเรขาคณิตด้วย (หลักสูตรเก่าจะอยู่ใน ม.6 เทอม 1 บทแรก เรื่องลำดับและอนุกรม)