3.2 Implicit Dynamic DictionaryThe

3.2 Implicit Dynamic Dictionary
The dynamic dictionary problem is defined as follows.
Given a set D  U, jDj = n, we need to implement efficiently
member(x;D) to determine whether x 2 D and
insert(x;D) that insert x into D. It is a subset of the
incremental sorting problem. Given a monotonic (strictly)
increasing integer function f : Z+ ! Z+, dynamic dictionary
can be implemented implicitly by using an array
A, and be visualized as a 2-level rotated lists. We divide
A into a list of r pairs D = hP0; : : : ; Pri, each pair Pi
consists of a singleton element ei and a sub-array Li of
size f(i) that is used as a rotated list. For an array of size
n, we have n 
Pr
i=1(f(i) + 1). The purpose of having
a monotonic increasing integer function is that the number
of blocks will always be proportional to the array size,
regardless of the number of insertions. This also avoids
amortized runtime cost as it requires no re-dividing when
the array grows. This invariant needs to be guaranteed in
order to have the runtime guarantee as it controls the number
of soft exchanges performed per insertion.

ผลลัพธ์ (ไทย) 1:

3.2 พจนานุกรมนัยแบบไดนามิกปัญหาพจนานุกรมแบบไดนามิกกำหนดไว้ดังนี้ได้รับการตั้งค่า D U, jDj = n เราจำเป็นต้องใช้อย่างมีประสิทธิภาพmember(x;D) เพื่อตรวจสอบว่า x 2 D และinsert(x;D) ที่ใส่ x เข้า d มันคือชุดย่อยของการเพิ่มปัญหาเรียงลำดับ กำหนดแบบ monotonic (อย่างเคร่งครัด)เพิ่มเต็มฟังก์ชัน f: Z + Z + พจนานุกรมแบบไดนามิกสามารถนำมาใช้นัย โดยใช้อาร์เรย์A และจะ visualized เป็นรายการ 2 ระดับหมุน เราแบ่งในรายการคู่ r D A = hP0 : : : ; Pri, Pi แต่ละคู่ei เป็นองค์ประกอบเดี่ยวและลีอาร์เรย์ย่อยของf(i) ขนาดที่ใช้เป็นรายการหมุน สำหรับอาร์เรย์ขนาดn เรามี nประชาสัมพันธ์i=1(f(i) + 1) วัตถุประสงค์ของการมีแบบ monotonic เพิ่มฟังก์ชันจำนวนเต็มคือจำนวนของบล็อกจะเป็นสัดส่วนกับขนาดของแถวลำดับโดยจำนวนต นี้ยังหลีกเลี่ยงรันไทม์ซึ่งตัดจำหน่ายต้นทุน ตามที่มันต้องไม่มีการแบ่งเวลาอาร์เรย์ขยาย บล็อกนี้ต้องสามารถรับประกันในสั่งการควบคุมหมายเลขมีรับประกันการใช้งานจริงแลกเปลี่ยนอ่อนดำเนินต่อแทรก

ผลลัพธ์ (ไทย) 2:

3.2
โดยปริยายพจนานุกรมแบบไดนามิกปัญหาพจนานุกรมแบบไดนามิกที่กำหนดไว้ดังต่อไปนี้.
กำหนดชุด D? U, JDJ n =
เราจำเป็นต้องดำเนินการอย่างมีประสิทธิภาพสมาชิก(x; D) เพื่อตรวจสอบว่า x 2 D
และแทรก(x; D) ที่แทรกเข้ามาใน x
ดีมันเป็นส่วนหนึ่งของการปัญหาการเรียงลำดับที่เพิ่มขึ้น ได้รับการต่อเนื่อง (อย่างเคร่งครัด)
การเพิ่มฟังก์ชั่นจำนวนเต็ม f: Z +! Z +
พจนานุกรมแบบไดนามิกที่สามารถดำเนินการได้โดยปริยายโดยใช้อาร์เรย์
A, และมองเห็นเป็น 2 ระดับรายการหมุน เราแบ่งลงในรายการคู่อา D = HP0 นั้น
:::; Pri
คู่แต่ละชิ้นประกอบด้วยองค์ประกอบเดี่ยวและเนย่อยอาร์เรย์หลี่ขนาด f (i) ที่ใช้เป็นรายการที่หมุน
สำหรับอาร์เรย์ของขนาด
n เรามี n?
Pr
i = 1 (f (i) + 1) วัตถุประสงค์ของการมีฟังก์ชั่นที่เพิ่มขึ้นต่อเนื่องเป็นจำนวนเต็มคือจำนวนของบล็อกจะถูกเสมอสัดส่วนกับขนาดอาร์เรย์คำนึงถึงจำนวนของแทรก นอกจากนี้ยังหลีกเลี่ยงค่าใช้จ่ายตัดจำหน่ายรันไทม์ที่มันไม่จำเป็นต้องแบ่งอีกครั้งเมื่ออาเรย์ที่เติบโตขึ้น ค่าคงที่นี้จะต้องมีการรับประกันในเพื่อที่จะมีการรับประกันเป็นรันไทม์จะควบคุมจำนวนของการแลกเปลี่ยนที่อ่อนนุ่มดำเนินการต่อการแทรก

ผลลัพธ์ (ไทย) 3:

3.2 ระบบพลวัตพจนานุกรม
ปัญหาพจนานุกรมแบบไดนามิกคือดังนี้ .
ได้รับชุด D  U , jdj = n , เราต้องใช้อย่างมีประสิทธิภาพ
สมาชิก ( X ; D ) เพื่อตรวจสอบว่า x 2 D และ
แทรก ( X ; D ) ที่แทรก x เป็น . มันเป็นเซตย่อยของ
เพิ่มการเรียงลำดับปัญหา ให้อย่างเดียว ( อย่างเคร่งครัด )
เพิ่มจำนวนเต็มฟังก์ชัน f : Z ! Z ,
พจนานุกรมแบบไดนามิกสามารถดำเนินการได้โดยการใช้อาร์เรย์
โดยปริยาย และมองเห็นเป็น 2-level หมุนรายการ เราแบ่ง
ในรายการของ R คู่ D = hp0 ; : : : ; องค์ แต่ละคู่ pi
ประกอบด้วยองค์ประกอบย่อยผนังเซลล์ EI และเรย์ลี้
ขนาด F ( i ) ที่ใช้เป็นหมุนรายการ สำหรับ array ของขนาด
n เรามี N

ผม  PR = 1 ( F ( 1 ) วัตถุประสงค์ของการมี
เป็นโมโนโทนิกเพิ่มฟังก์ชันจำนวนเต็มคือหมายเลข
ของบล็อกจะเป็นสัดส่วนกับอาร์เรย์ขนาด
โดยไม่คำนึงถึงจำนวนครั้ง . นี้ยังหลีกเลี่ยง
ของขวัญ Runtime ต้นทุนดังกล่าวต้องไม่มีเรื่องการหารเมื่อ
อาร์เรย์ที่เติบโตขึ้น ค่าคงที่นี้ต้องรับประกันใน
เพื่อให้ runtime รับประกันเป็นการควบคุมหมายเลข
นุ่มแลกเปลี่ยนแสดงต่อการแทรก