โครงสร้างข้อมูลและอัลกอริทึมในการเปลี่ยน
นี่คือบทสรุปของการเรียนรู้ของฉันจากหลักสูตร Udemy: "โครงสร้างข้อมูล & Algo ใน Swift"
ความซับซ้อนของเวลา:
- เวลาคงที่
- เวลาเชิงเส้น
- เวลากำลังสอง
- เวลาลอการิทึม - การค้นหาแบบไบนารี
- เวลา quasilinear
โหนด:
- ราก
- เด็ก -> เด็กซ้ายและเด็กขวา
- ใบไม้
รายการที่เชื่อมโยง
องค์ประกอบเชื่อมต่อกันโดยอ้างอิงที่เรียกว่าโหนด
โหนดที่ 1 ในรายการที่เชื่อมโยงเรียกว่า Head
โหนดสุดท้ายเรียกว่าโหนดหาง
การดำเนินการ: - พุช - ผนวก - แทรก - ป๊อป - removelast - ลบ
สแต็ค (LIFO)
คิว (FIFO)
- มองดู
- การปิดการใช้งาน
- ขจัดคราบ
การเรียกซ้ำ
- กรณีฐาน - ซึ่งหยุดการเรียกซ้ำ
- กรณีเรียกซ้ำ
ต้นไม้:
- การสำรวจครั้งแรกในเชิงลึก
- ลำดับการเดินทางระดับ
- ค้นหา
- ต้นไม้ไบนารี (สามารถมีลูกได้สูงสุด: 2 คนเท่านั้น - ซ้ายและขวา)
- ในคำสั่ง traversal -> leftchild -> โหนด -> rightchild
- โพสต์คำสั่ง traversal -> leftchild -> rightchild -> โหนด
- คำสั่งซื้อล่วงหน้า traversal -> โหนด -> leftchild -> rightchild
- แผนผังไบนารี
การค้นหาเชิงเส้น
การค้นหาแบบไบนารี
- จัดเรียงอาร์เรย์
- ดัชนีกลาง - ซ้ายหรือขวา
- เวลาที่ดีที่สุด: O (1)
- เวลาที่เลวร้ายที่สุด: O (log n)
จัดเรียงฟอง
- ไม่ได้เรียงลำดับ
- เวลาที่ดีที่สุด: o (n) (ถ้าเรียงลำดับแล้ว)
- เวลาที่เลวร้ายที่สุด: o (n^2)
การเลือกการเลือก
- สลับองค์ประกอบขั้นต่ำในอาร์เรย์ด้วยดัชนีปัจจุบัน
- ย้ายไปที่ดัชนีถัดไปและทำซ้ำขั้นตอนที่ 1
- เวลาที่ดีที่สุด: o (n^2)
- เวลาที่เลวร้ายที่สุด: o (n^2)
เรียงลำดับ
- ไม่ได้เรียงลำดับ
- เวลาที่ดีที่สุด: o (n)
- เวลาที่เลวร้ายที่สุด: o (n^2)
กราฟ:
ประกอบด้วย
- จุดยอด / จุดสุดยอด
- ขอบ / ขอบ
ประเภทของกราฟ:
- กราฟถ่วงน้ำหนัก
- กราฟกำกับ
- กราฟที่ไม่ได้กำกับ (สองทิศทาง)
รายการ adjacency
- วิธีที่ใช้กันมากที่สุด/ใช้กันอย่างแพร่หลายในการสร้างและแสดงกราฟ
