Nếu ngôn ngữ mã hóa đầu tiên của bạn là Javascript, giống như đối với tôi, thì bạn có thể hơi lạc đề về chính tiêu đề đó. Bạn không nghe thấy thuật ngữ 'tĩnh' hay 'động' khi nhắc đến mảng trong Javascript
Vì vậy, chính xác những gì là sự khác biệt giữa hai điều này?
Hãy bắt đầu với việc tìm hiểu mảng tĩnh là gì. Định nghĩa kỹ thuật sẽ là việc triển khai một mảng phân bổ một lượng bộ nhớ cố định được sử dụng để lưu trữ các giá trị của mảng. Với dung lượng bộ nhớ cố định, điều đó có nghĩa là không có khoảng trống để thêm bất kỳ giá trị nào vào cùng một mảng. Thật kỳ lạ, việc thêm các giá trị vào một mảng là một trong những điều phổ biến nhất mà bạn sẽ làm, vậy điều gì sẽ xảy ra? . Điều này nghe có vẻ không đẹp nhưng cũng không hoàn toàn tệ, sẽ nói thêm về điều này sau. Chúng tôi cũng sẽ xem xét điều này có nghĩa là gì đối với Big O
Nếu một mảng tĩnh liên quan đến một lượng bộ nhớ cố định thì bạn có thể tưởng tượng một mảng động thì ngược lại. Ở mức độ chính xác cao, một mảng động phân bổ gấp đôi dung lượng bộ nhớ cần thiết để lưu trữ các giá trị của mảng. Hãy nghĩ về kịch bản tương tự của việc thêm một giá trị vào một mảng trong trường hợp này. Chúng tôi đã phân bổ không gian trong bộ nhớ để thêm các giá trị ngay từ đầu
Học Javascript Tôi đã rất thích thú khi chỉ cần định nghĩa một mảng là một biến và thao tác với nó khi tôi cần. Lý do là Javascript sử dụng mảng động. Ngay cả khi mảng của bạn lấp đầy không gian thừa đó, bạn không cần phải làm bất cứ điều gì. Javascript ngầm sẽ tìm dung lượng trong bộ nhớ, phân bổ gấp đôi dung lượng bộ nhớ bạn cần để lưu trữ giá trị ban đầu cũng như giá trị mới và sao chép các giá trị
Tại thời điểm này, bạn có thể thấy sự khác biệt giữa hai định nghĩa nhưng tại sao bạn lại quan tâm?
Đây là nơi mọi thứ trở nên thực sự tuyệt vời. Hãy đặt một số định nghĩa này thành hình ảnh và xem tất cả điều này thực sự có nghĩa là gì
Dưới đây là một số thao tác bạn sẽ thực hiện với mảng cùng với độ phức tạp về thời gian của chúng
- Truy cập giá trị tại một chỉ mục nhất định. Ô[1]
- Chèn giá trị vào đầu. Trên]
- Cập nhật giá trị tại một chỉ mục nhất định. Ô[1]
Những điều này đúng cho cả mảng tĩnh và động. Điểm khác nhau là khi bạn muốn chèn một giá trị vào cuối một mảng
Hãy xem qua một ví dụ về cách các mảng tĩnh chiếm bộ nhớ. Để đơn giản, mỗi giá trị trong mảng chiếm 1 ô trong bộ nhớ trên biểu đồ này. Bạn có thể nhận được cụ thể và nói về byte bộ nhớ tùy thuộc vào loại dữ liệu của một phần tử nhưng điều đó sẽ làm cho biểu đồ này hơi quá lớn
Trong ví dụ bên dưới, chúng tôi bắt đầu với một mảng chứa các giá trị [ 1, 2 ] mà bạn sẽ thấy màu tím. Chà, tôi muốn thêm một giá trị khác… Tuyệt vời, tất cả những gì máy tính của bạn phải làm là tìm bộ nhớ mới phù hợp với giá trị hiện tại của bạn cộng với giá trị bạn muốn thêm. Và hãy làm lại vì chúng ta cần thêm giá trị 4 ngay bây giờ
Bạn có thể thấy điều đó có thể rắc rối như thế nào và độ phức tạp của thời gian phản ánh điều đó. Mỗi khi chúng ta thêm một giá trị vào một mảng tĩnh, độ phức tạp về thời gian sẽ là O[n]
Khi bạn bắt đầu xây dựng các thuật toán với độ phức tạp về không gian và thời gian, bạn muốn tìm ra cách tốt nhất để làm điều gì đó với độ phức tạp tối ưu nhất
Trước đây tôi đã nói rằng một mảng động phân bổ gấp đôi bộ nhớ, điều này làm cho việc thêm các giá trị trở nên dễ dàng hơn nhiều. Đây là những gì trông giống như
Ở đây chúng ta bắt đầu với cùng một mảng [ 1, 2 ] nhưng khi khởi tạo, nó phân bổ 4 hộp trong bộ nhớ [gấp đôi kích thước của mảng ban đầu]. Bây giờ, khi thêm các giá trị 3 và 4, sẽ chỉ mất O[1] thời gian cho mỗi giá trị và chúng ta không cần tìm thêm bộ nhớ cho đến khi thêm giá trị thứ năm, sau đó là thời gian O[n]. Cụ thể hơn, mảng này có thể thay đổi kích thước mà không cần phải sao chép chính nó mỗi lần miễn là nó nằm trong bộ nhớ được cấp phát. Nếu bạn nghĩ về tần suất bạn thêm các giá trị vào một mảng, bạn có thể tưởng tượng điều này có thể ảnh hưởng đến mọi thứ như thế nào. Sau khi tạo mảng cuối cùng của chúng tôi với các giá trị 1–5, chúng tôi kết thúc bằng bộ nhớ để chiếm 5 giá trị đó nhưng cũng có 5 ô trống chưa được xác định. Bây giờ, mỗi khi chúng tôi thêm một giá trị vào cuối, sẽ mất thời gian O[1] miễn là nó nằm trong không gian được phân bổ
Nói chung, chúng tôi nói về Big O liên quan đến trường hợp xấu nhất và trong trường hợp này, bạn có thể thấy nếu bạn kéo dài điều này ra, bạn sẽ kết thúc với một chuỗi các hoạt động thời gian trong đó hầu hết là O[1] với . Đây chắc chắn là một trường hợp cạnh được chấp nhận rộng rãi và nó được gọi là Độ phức tạp thời gian được khấu hao, cho phép chúng tôi nói rằng việc thêm một giá trị vào cuối một mảng động sẽ mất O[1] thời gian
Hãy xem một hình ảnh nhanh để hiểu O[n] trông như thế nào so với O[1]
Mảng là một trong những cấu trúc dữ liệu tốt nhất mặc dù chúng khá đơn giản. Tôi hy vọng bây giờ bạn đã hiểu rõ hơn một chút về các nguyên tắc cơ bản của chúng và có thể đánh giá cao cách một ngôn ngữ cấp cao như Javascript giúp mọi việc trở nên dễ dàng hơn. Javascript không phải là ngôn ngữ duy nhất làm được điều này, mặc định Python cũng sử dụng mảng động. Các ngôn ngữ như C, C++ và Java giúp bạn tạo mảng đồng thời xác định dung lượng bộ nhớ bạn muốn phân bổ cho nó