java algorithms collections

อัลกอริทึมและคอลเลกชัน Java

การรวบรวมข้อมูลที่กำหนดเองสำหรับการสัมภาษณ์ทางเทคนิคสำหรับบทบาทนักพัฒนา Java Java

อัลกอริทึม

ดูรายการทั้งหมดที่นี่

สัญลักษณ์ใหญ่ o

• ความซับซ้อนของเวลา : การประมาณจำนวนการดำเนินงานหรือขั้นตอนที่อัลกอริทึมจำเป็นต้องทำงานเป็นฟังก์ชันของขนาดอินพุต
• ความซับซ้อนของพื้นที่ : จำนวนหน่วยความจำเสริมสูงสุดที่อัลกอริทึมจำเป็นต้องจัดสรรหรือใช้ในระหว่างการดำเนินการเป็นฟังก์ชันของขนาดอินพุต
  • พื้นที่เสริม เป็นพื้นที่พิเศษหรือพื้นที่ชั่วคราวที่ใช้โดยอัลกอริทึม

n ในความซับซ้อนของเวลา - จำนวนองค์ประกอบในอินพุต

n ในความซับซ้อนของอวกาศ - ขนาดอินพุตในหน่วยของบิตที่จำเป็นในการแสดงอินพุต

ตารางความซับซ้อนของเวลาขนาดใหญ่

พิมพ์	ชื่อ	คำอธิบาย	สถานะ	ตัวอย่าง
O(1)	เวลาคงที่	อัลกอริทึมจะดำเนินการจำนวนเท่ากันในแต่ละครั้งโดยไม่คำนึงถึงขนาดของอินพุต	ยอดเยี่ยม	ค้นหาในตารางแฮชโดยคีย์
O(log n)	เวลาลอการิทึม	เวลาดำเนินการเพิ่มขึ้นช้ามากเมื่อเทียบกับการเพิ่มขนาดของข้อมูลอินพุต	ยอดเยี่ยม	การค้นหาแบบไบนารี (เฉลี่ย)
O(n)	เวลาเชิงเส้น	เวลาดำเนินการเป็นสัดส่วนเชิงเส้นตรงกับขนาดของข้อมูลอินพุต	ดี	การค้นหากำลังดุร้าย
O(n + k)	เวลารวม/สารเติมแต่ง	ความซับซ้อนรวมของอินพุตสองอินพุตแยกกัน	ดี	การนับการเรียงลำดับ
O(n log n)	เวลา quasilinear	เมื่อขนาดอินพุตเพิ่มขึ้นจำนวนหน่วยงานที่จำเป็นในการแก้ปัญหาจะเพิ่มขึ้นอย่างช้าๆเนื่องจากการเติบโตของลอการิทึม	แย่	การเรียงลำดับการเรียงลำดับกองจัดเรียง
O(n^2)	เวลากำลังสอง	เกี่ยวข้องกับการทำซ้ำหรือการเปรียบเทียบสำหรับแต่ละองค์ประกอบ	น่ากลัว	การเลือกการเลือก
O(2^n)	เวลาทวีคูณ	เกี่ยวข้องกับการค้นหาอย่างละเอียดหรือแจงนับการรวมกันที่เป็นไปได้ทั้งหมดของอินพุตเวลาดำเนินการเพิ่มขึ้นแบบทวีคูณ	น่ากลัว	TSP (การเขียนโปรแกรมแบบไดนามิก)
O(n!)	เวลาแฟคทอเรียล	เกี่ยวข้องกับการค้นหาอย่างละเอียดหรือการแจงนับการรวมกันที่เป็นไปได้ทั้งหมดของอินพุตเวลาดำเนินการเพิ่มขึ้นอย่างเป็นปัจจัย	น่ากลัว	TSP (กำลังเดรัจฉาน)

ตารางความซับซ้อนอวกาศ Big-O

พิมพ์	ชื่อ	คำอธิบาย	สถานะ	ตัวอย่าง
O(1)	พื้นที่คงที่	อัลกอริทึมต้องใช้หน่วยความจำเพิ่มเติมจำนวนคงที่โดยไม่คำนึงถึงขนาดอินพุต	ยอดเยี่ยม	การจัดเรียงกอง
O(log n)	พื้นที่ลอการิทึม	การใช้พื้นที่เพิ่มขึ้นอย่างช้าๆเมื่อเทียบกับการเพิ่มขนาดของข้อมูลอินพุต	ยอดเยี่ยม	จัดเรียงอย่างรวดเร็ว
O(n)	พื้นที่เชิงเส้น	การใช้พื้นที่จะปรับขนาดเป็นเส้นตรงกับขนาดอินพุต	ดี	การเรียงลำดับ
O(n + k)	พื้นที่รวม/สารเติมแต่ง	การใช้พื้นที่จะปรับขนาดเป็นเส้นตรงด้วยผลรวมของ n และ k	แย่	เรียงลำดับ Radix

คำจำกัดความ

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

คลาสคอลเลกชัน Java

• ของสะสม
  • ชุด
    • Hashset
    • linkedhashset
      • ชุด
      • ชุดนำทาง
        • ชุดต้นไม้
  • รายการ
    • ผู้เข้าร่วมงาน
    • LinkedList
    • เวกเตอร์
      • กองซ้อน
  • คิว
    • คิวลำดับความสำคัญ
      • การเดิมพัน
        • อาร์เรย์
• แผนที่
  • แฮช
  • Hashmap
  • LinkedHashMap
    • SortedMap
    • การนำทาง
      • treemap

การเปรียบเทียบประเภทคอลเลกชัน:

พิมพ์	องค์ประกอบที่ซ้ำกัน	ลำดับขององค์ประกอบ	ต้องเพิ่ม/ลบตามลำดับที่เฉพาะเจาะจง
รายการ	อนุญาต	โดยดัชนี	เลขที่
แผนที่	อนุญาตสำหรับค่า	java ใช้ hashcode () ของคีย์เพื่อกำหนดคำสั่งซื้อสำหรับเรามันไม่ได้เรียงลำดับ	เลขที่
คิว	อนุญาต	สืบค้นตามลำดับที่กำหนดไว้	ใช่
ชุด	ต้องห้าม	เฉพาะในชุดต้นไม้	ใช่

คุณลักษณะการรวบรวม:

พิมพ์	ส่วนต่อประสาน	เรียงลำดับ?	โทร hashCode() ?	เรียก compareTo() ?
ผู้เข้าร่วมงาน	รายการ	เลขที่	เลขที่	เลขที่
LinkedList	รายการ deque	เลขที่	เลขที่	เลขที่
อาร์เรย์	คิว, deque	เลขที่	เลขที่	เลขที่
Hashset	ชุด	เลขที่	ใช่	เลขที่
ชุดต้นไม้	ตั้ง, sortedset	ใช่	เลขที่	ใช่
linkedhashset	ชุด	เลขที่	ใช่	เลขที่
Hashmap	แผนที่	เลขที่	ใช่	เลขที่
LinkedHashMap	แผนที่	เลขที่	ใช่	เลขที่
treemap	แผนที่ SortedMap	ใช่	เลขที่	ใช่

โครงสร้างข้อมูลที่เกี่ยวข้องกับการเรียงลำดับไม่อนุญาตให้ค่า NULL