Tìm hiểu ký hiệu Big O qua JavaScript
Nếu bạn đã từng tìm kiếm một công việc với quyền là một nhà phát triển, chắc chắn bạn đã xem qua cuộc phỏng vấn này của Google tại một thời điểm nào đó và tự hỏi 'họ đang nói về cái quái gì vậy?'. Trong bài viết này, ta sẽ khám phá ý nghĩa của chúng khi xoay quanh các thuật ngữ như 'bậc hai' và 'n log n'.
Trong một số ví dụ này, tôi sẽ đề cập đến hai mảng này, một mảng có 5 mục và một mảng khác có 50. Tôi cũng sẽ sử dụng API hiệu suất tiện dụng của JavaScript để đo lường sự khác biệt về thời gian thực thi.
const smArr = [5, 3, 2, 35, 2]; const bigArr = [5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2]; Ký hiệu Big O là gì?
Ký hiệu Big O chỉ là một cách thể hiện sự tăng trưởng chung về độ khó tính toán của một nhiệm vụ khi bạn tăng tập dữ liệu. Trong khi có các ký hiệu khác, ký hiệu O thường được sử dụng nhiều nhất vì nó tập trung vào trường hợp xấu nhất, dễ định lượng và suy nghĩ hơn. Trường hợp xấu nhất nghĩa là trong đó các thao tác cần thiết nhất để hoàn thành nhiệm vụ; Nếu bạn giải một khối rubik trong một giây, bạn không thể nói rằng bạn là người giỏi nhất nếu bạn chỉ mất một lượt để hoàn thành.
Khi bạn tìm hiểu thêm về các thuật toán, bạn sẽ thấy những biểu thức này được sử dụng rất nhiều bởi vì việc viết mã của bạn trong khi hiểu mối quan hệ này có thể là sự khác biệt giữa một hoạt động gần như tức thời hoặc mất vài phút và lãng phí, đôi khi là số tiền khổng lồ cho các bộ xử lý bên ngoài như Firebase .
Khi bạn tìm hiểu thêm về ký hiệu Big O, bạn có thể sẽ thấy nhiều biến thể khác nhau và tốt hơn của biểu đồ này. Ta muốn giữ độ phức tạp của bạn ở mức thấp và thẳng nhất có thể, lý tưởng nhất là tránh bất kỳ thứ gì trên O (n).
O (1)
Đây là điều lý tưởng, dù có bao nhiêu mục, dù một hay một triệu, thời gian hoàn thành sẽ không đổi. Hầu hết các phép toán thực hiện một phép toán đơn lẻ là O (1). Việc đẩy đến một mảng, nhận một mục tại một index cụ thể, thêm một phần tử con, v.v., tất cả sẽ mất cùng một khoảng thời gian dù độ dài của mảng.
const a1 = performance.now(); smArr.push(27); const a2 = performance.now(); console.log(`Time: ${a2 - a1}`); // Less than 1 Millisecond const b1 = performance.now(); bigArr.push(27); const b2 = performance.now(); console.log(`Time: ${b2 - b1}`); // Less than 1 Millisecond Trên)
Theo mặc định, tất cả các vòng lặp là một ví dụ về tăng trưởng tuyến tính vì có mối quan hệ 1-1 giữa kích thước dữ liệu và thời gian hoàn thành. Vì vậy, một mảng có nhiều hơn 1.000 lần các mục sẽ lâu hơn chính xác 1.000 lần.
const a1 = performance.now(); smArr.forEach(item => console.log(item)); const a2 = performance.now(); console.log(`Time: ${a2 - a1}`); // 3 Milliseconds const b1 = performance.now(); bigArr.forEach(item => console.log(item)); const b2 = performance.now(); console.log(`Time: ${b2 - b1}`); // 13 Milliseconds O (n ^ 2)
Tăng trưởng theo cấp số nhân là một cái bẫy mà tất cả ta đều từng rơi vào ít nhất một lần. Bạn cần tìm một cặp phù hợp cho mỗi mục trong một mảng? Đặt một vòng lặp bên trong một vòng lặp là cách tốt để biến một mảng 1.000 mục thành một triệu thao tác tìm kiếm sẽ đóng băng trình duyệt của bạn. Luôn luôn tốt hơn khi phải thực hiện 2.000 hoạt động trên hai vòng lặp riêng biệt hơn là một triệu với hai vòng lặp lồng nhau.
const a1 = performance.now(); smArr.forEach(() => { arr2.forEach(item => console.log(item)); }); const a2 = performance.now(); console.log(`Time: ${a2 - a1}`); // 8 Milliseconds const b1 = performance.now(); bigArr.forEach(() => { arr2.forEach(item => console.log(item)); }); const b2 = performance.now(); console.log(`Time: ${b2 - b1}`); // 307 Milliseconds O (log n)
Phép loại suy tốt nhất mà tôi đã nghe để hiểu sự tăng trưởng theo lôgarit là tưởng tượng bạn đang tra cứu một từ như 'ký hiệu' trong từ điển. Bạn không thể tìm kiếm hết mục này đến mục nhập khác, thay vào đó bạn tìm phần 'N', sau đó có thể là trang 'OPQ', sau đó tìm kiếm danh sách theo thứ tự bảng chữ cái cho đến khi bạn tìm thấy kết quả phù hợp.
Với cách tiếp cận 'chia để trị' này, lượng thời gian để tìm thứ gì đó sẽ vẫn thay đổi tùy thuộc vào kích thước của từ điển nhưng không bằng tỷ lệ O (n). Bởi vì nó tìm kiếm trong các phần cụ thể hơn mà không cần xem xét hầu hết dữ liệu, việc tìm kiếm qua một nghìn mục có thể mất ít hơn 10 thao tác trong khi một triệu có thể mất ít hơn 20 thao tác, giúp bạn có được nhiều nhất cho khoản tiền của bạn .
Trong ví dụ này, ta có thể làm một động tác nhanh đơn giản.
const sort = arr => { if (arr.length < 2) return arr; let pivot = arr[0]; let left = []; let right = []; for (let i = 1, total = arr.length; i < total; i++) { if (arr[i] < pivot) left.push(arr[i]); else right.push(arr[i]); }; return [ ...sort(left), pivot, ...sort(right) ]; }; sort(smArr); // 0 Milliseconds sort(bigArr); // 1 Millisecond Trên!)
Cuối cùng, một trong những khả năng tồi tệ nhất, tăng trưởng giai thừa. Ví dụ trong sách giáo khoa về vấn đề này là vấn đề người bán hàng đi du lịch . Nếu bạn có một loạt các city với khoảng cách khác nhau, làm thế nào để bạn tìm được con đường ngắn nhất có thể đi giữa tất cả chúng và quay trở lại điểm xuất phát? Phương pháp brute force sẽ là kiểm tra khoảng cách giữa mọi cấu hình có thể có giữa mỗi city , đây sẽ là một giai thừa và nhanh chóng vượt ra khỏi tầm tay.
Vì vấn đề đó trở nên rất phức tạp rất nhanh, ta sẽ chứng minh sự phức tạp này bằng một hàm đệ quy ngắn. Hàm này sẽ nhân một số với hàm riêng của nó lấy chính nó trừ đi một. Mỗi chữ số trong giai thừa của ta sẽ chạy hàm riêng của nó cho đến khi nó đạt đến 0, với mỗi lớp đệ quy sẽ thêm tích của nó vào số ban đầu của ta . Vì vậy, 3 được nhân với 2 mà chạy hàm được nhân với 1 mà chạy lại nó bị dừng lại ở 0, trả về 6. Đệ quy trở nên khó hiểu như thế này khá dễ dàng.
Giai thừa chỉ là tích của mọi số lên đến số đó. Vì vậy, 6! là 1x2x3x4x5x6 = 720.
const factorial = n => { let num = n; if (n === 0) return 1 for (let i = 0; i < n; i++) { num = n * factorial(n - 1); }; return num; }; factorial(1); // 2 Milliseconds factorial(5); // 3 Milliseconds factorial(10); // 85 Milliseconds factorial(12); // 11,942 Milliseconds Thay vào đó, tôi đã định hiển thị factorial(15) nhưng bất kỳ thứ gì trên 12 là quá nhiều và làm hỏng trang, do đó chứng minh chính xác lý do tại sao điều này cần phải tránh.
Bớt tư tưởng
Giữ cho mã của bạn hoạt động hiệu quả nhất có thể có vẻ là một mối quan tâm rõ ràng, nhưng tôi chắc rằng hầu hết mọi nhà phát triển đều đã tạo các vòng lặp lồng nhau gấp đôi hoặc thậm chí gấp ba ít nhất một lần vì 'nó chỉ hoạt động'. Ký hiệu Big O rất cần thiết trong việc thể hiện và suy nghĩ về sự phức tạp là cách mà trước đây ta chưa bao giờ làm được.
Các tin liên quan
Cách sử dụng API BroadcastChannel trong JavaScript2020-01-13
Đa năng hóa chuỗi trong JavaScript bằng Simplur
2020-01-10
Hướng dẫn nhanh về phương pháp đối sánh chuỗi trong JavaScript
2020-01-07
Tham quan API quyền JavaScript
2020-01-05
V8 của V8: Chuỗi liên kết tùy chọn và kết hợp Nullish trong JavaScript
2019-12-29
Phân tích cú pháp, xác thực, thao tác và hiển thị ngày và giờ trong JavaScript với Day.js
2019-12-28
Cách bắt đầu với API hiệu suất JavaScript
2019-12-25
Xem xét tất cả 13 bẫy proxy JavaScript
2019-12-19
Khám phá phương thức indexOf cho chuỗi và mảng trong JavaScript
2019-12-17
Thao tác DOM trong JavaScript với innerText và innerHTML
2019-12-14
