ช่วยโจทย์เรื่อง ฟังก์ชั่น หน่อยครับ
T(n) = 3T(n/2)+C
โดยที่ c เป็นค่าคงตัว ให้ หา T(n) ที่ไม่ติดฟังก์ชั่น T :) |
อยากรู้ก็เมล์ไปถาม อ.ซึง สิ
|
พอดีเห็นคุณ <เสริม> พูดถึงอ.ซึง เลยนึกขึ้นได้ไปค้นๆมา เห็นแต่ที่คล้ายๆนะครับ
ความสัมพันธ์ recurrence ของ Binary search เป้นดังนี้ T(n)=T(n/2)+C2 ให้ T(1)=C1 solving the recuurence relation ดังนี้ T(n) = C2+T(n/2) = C2+ C2 +T(n/4) = C2+ C2+ C2T(n/8) ... ลองแทนความสัมพันธ์ไปเรื่อยๆจะได้หน้าตาแบบนี้ T(n)=i C2 +T(n/2i) เมื่อ 2i=n จะได้ว่า i=log2n แทนค่า i ลงไปจะได้ว่า T(n)=(log2n)C2 +T(1)=C2(log2n)+C1 เป็นปัญหาด้านคอมพิวเตอร์นะครับอยู่ในส่วน Alglorithm |
ต้องบอกโดเมนกับเรนจ์มาด้วยครับ. เช่น จาก จำนวนจริง ฎจำนวนจริง, จำนวนนับ ฎ จำนวนนับ เป็นต้น.
|
อ๊ากกก ขั้อนี้คิดไม่ออกเลย คิดได้ไงเนี่ยยยย
|
อ่า ก็ ไปดูในหนังสือมาอ่ะ ไม่ได้คิดเองเหมือนกัน ยังไมได้เรียนเรื่อง recurence relation เลย อยู่ใน discrete math อ่ะ
|
ถ้าเลียนแบบวิธีที่น้อง M@pie แสดงมาก็จะได้ ดังนี้ครับ. ถ้าให้ T(1) = C จะได้ว่า T(n) = [ (C1 + 2C)3log2n - C1 ] /2
note : ใช้สูตรอนุกรมเรขาคณิตด้วย (หลักสูตรเก่าจะอยู่ใน ม.6 เทอม 1 บทแรก เรื่องลำดับและอนุกรม) |
เวลาที่แสดงทั้งหมด เป็นเวลาที่ประเทศไทย (GMT +7) ขณะนี้เป็นเวลา 22:19 |
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Modified by Jetsada Karnpracha