ประสิทธิภาพของอัลกอริทึม: ความซับซ้อนด้านเวลาและพื้นที่

แนวคิดในวิทยาการคอมพิวเตอร์

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

แนะนำ Big-O Notation

วัดการเติบโตของเวลาและพื้นที่เมื่อขนาด input เพิ่มขึ้น
ตัวอย่าง: $O(n)$, $O(n^2)$, $O(log\, n)$
'O' ย่อมาจาก 'order' ของการเติบโต เช่น O(n) = linear

ความซับซ้อนด้านเวลา - เปรียบกับงานออฟฟิศ

กราฟแสดงความซับซ้อนของ Big O Notation ประเภทต่างๆ

$O(1)$ - เวลาคงที่ - "มองผ่านๆ" - "constant"
$O(log\,n)$ - เวลาเพิ่มช้า - "แบ่งกอง" - "logarithmic"
$O(n)$ - เพิ่มแบบ linear - "อ่านเอกสาร" - "linear"
$O(n\,log\,n)$ - เวลาเพิ่มเร็วขึ้น - "จัดเรียงกอง" - "linearithmic"
$O(n^2)$ - เวลาเพิ่มแบบ quadratic - "เปรียบเทียบเอกสาร" - "quadratic"

ความซับซ้อนด้านพื้นที่ - เปรียบกับงานออฟฟิศ

กราฟแสดงความซับซ้อนของ Big O Notation ประเภทต่างๆ

$O(1)$ - พื้นที่คงที่ - "พื้นที่โต๊ะ" - "constant"
$O(log\,n)$ - พื้นที่เพิ่มช้า - "จดโน้ตน้อย" - "logarithmic"
$O(n)$ - เพิ่มแบบ linear - "โน้ตกาว" - "linear"
$O(n\,log\,n)$ - พื้นที่เพิ่มเร็วขึ้น - "กองชั่วคราว" - "linearithmic"
$O(n^2)$ - พื้นที่เพิ่มแบบ quadratic - "ตารางเปรียบเทียบ" - "quadratic"

มาฝึกกันเถอะ!

แนวคิดในวิทยาการคอมพิวเตอร์

Preparing Video For Download...