ประสิทธิภาพเทียบกับโครงสร้างข้อมูลอื่น ของ แถวลำดับพลวัต

 รายการโยงแถวลำดับรายการ
แถวลำดับ
ต้นไม้
สมดุล
รายการเข้าถึง
ข้อมูลแบบสุ่ม
การเข้าถึงข้อมูลΘ(n)Θ(1)Θ(1)Θ(log n)Θ(log n)
การเพิ่มและลบที่ด้านหน้าΘ(1)N/AΘ(n)Θ(log n)Θ(1)
การเพิ่มและลบที่ปลายΘ(1)N/AΘ(1) ถัวเฉลี่ยΘ(log n)Θ(log n) ในการปรับ
การเพิ่มและลบตรงกลางเวลาค้นหา +
Θ(1)[6][7][8]
N/AΘ(n)Θ(log n)Θ(log n) ในการปรับ
พื้นที่ซึ่งเสียไป (โดยเฉลี่ย)Θ(n)0Θ(n)[9]Θ(n)Θ(n)

แถวลำดับพลวัตมีประสิทธิภาพเหมือนแถวลำดับทุกประการ นอกจากนี้ยังมีความสามารถมากขึ้นด้วยการสามารถเพิ่มหรือลบข้อมูลทางปลายได้เรื่อย ๆ ความสามารถของแถวลำดับพลวัตมีดังนี้

  • การเข้าถึงข้อมูลโดยดัชนี : ใช้เวลาคงที่
  • การวนเข้าถึงสมาชิกทุก ๆ ตัว : ใช้เวลาเชิงเส้น, สามารถแคชข้อมูลได้ (เนื่องจากที่อยู่ของหน่วยความจำในแถวลำดับอยู่ติดกัน จึงสามารถแคชได้)
  • การแทรกหรือลบกลางแถวลำดับพลวัต : ใช้เวลาเชิงเส้น
  • การแทรกหรือลบที่ปลายของแถวลำดับพลวัต : ใช้เวลาถัวเฉลี่ยคงที่

จะเห็นได้ว่าข้อดีทั้งหลายของแถวลำดับพลวัตมาจากข้อดีของแถวลำดับ เช่นการที่สามารถแคชข้อมูล มีความแน่นของข้อมูลมาก (ใช้เนื้อที่น้อย) การเข้าถึงโดยสุ่ม มีเพียงตัวแปรเก็บขนาดและความจุที่ต้องเก็บเพิ่มเท่านั้น ดังนั้นแถวลำดับพลวัตจึงเป็นโครงสร้างข้อมูลที่เหมาะในการทำงานหลาย ๆ อย่าง

เปรียบเทียบกับรายการโยงแล้ว แถวลำดับพลวัตสามารถเข้าถึงข้อมูลแบบสุ่มได้ ในขณะที่รายการโยงต้องใช้เวลาเชิงเส้น นอกจากนี้ยังมีความสามารถในการแคช ต่างจากรายการโยงที่ข้อมูลไม่ได้มีที่อยู่หน่วยความจำติดกัน ทำให้ไม่สามารถแคชข้อมูลได้ อย่างไรก็ตาม ความสามารถในการเพิ่มและลบข้อมูลกลางแถวลำดับพลวัตจะใช้เวลาเชิงเส้นเหมือนแถวลำดับเนื่องจากข้อมูลต้องเลื่อนเป็นจำนวนมาก ในขณะที่รายการโยงสามารถทำได้ในเวลาคงที่ ข้อด้อยนี้อาจใช้บัฟเฟอร์ช่องว่าง, tiered vector ช่วยได้ (อธิบายไว้ข้างล่างในหัวข้อโครงสร้างข้อมูลอื่นที่คล้ายกัน) สำหรับเครื่องที่มีหน่วยความจำน้อยหรือมีความกระจัดกระจายของพื้นที่หน่วยความจำสูง อาจจะไม่สามารถหาพื้นที่ติดกันที่มากพอในการจัดสรรให้แถวลำดับพลวัตได้

สำหรับต้นไม้สมดุล มีความสามารถในการดำเนินการต่าง ๆ ด้วยเวลาที่น้อยมาก เช่นเข้าถึงข้อมูลตัวใด ๆ, เพิ่มและลบข้อมูล ณ ตำแหน่งใด ๆ ในเวลา O ( log ⁡ n ) {\displaystyle O(\log n)} อย่างไรก็ตาม เนื้อที่ที่เก็บข้อมูลในโครงสร้างต้นไม้นั้นไม่ติดกัน จึงทำให้ไม่สามารถแคชได้

แหล่งที่มา

WikiPedia: แถวลำดับพลวัต http://www.cs.uwaterloo.ca/research/tr/1999/09/CS-... http://www.collectionspy.com http://www.cplusplus.com/reference/deque/deque/ http://www.cplusplus.com/reference/vector/vector/ http://www.ddj.com/architect/184409965?pgno=5 http://channel9.msdn.com/Events/GoingNative/GoingN... http://download.oracle.com/javase/7/docs/api/java/... http://kjellkod.wordpress.com/2012/02/25/why-you-s... http://www.juniata.edu/faculty/kruse/cs240/linkedl... http://www.juniata.edu/faculty/kruse/cs240/syllabu...