<p>Ch&agrave;o mừng c&aacute;c bạn đến với kh&oacute;a học "Cấu tr&uacute;c dữ liệu v&agrave; Giải thuật" tại TEK4.VN!</p>
<p>Bạn đ&atilde; bao giờ tự hỏi rằng để trở th&agrave;nh một lập tr&igrave;nh vi&ecirc;n xuất sắc, bạn cần những kiến thức v&agrave; kỹ năng g&igrave;? Kh&oacute;a học n&agrave;y ch&iacute;nh l&agrave; ch&igrave;a kh&oacute;a để mở ra c&aacute;nh cửa của tri thức đ&oacute;. Với nội dung phong ph&uacute; v&agrave; chi tiết, kh&oacute;a học Cấu tr&uacute;c dữ liệu v&agrave; Giải thuật tại TEK4.VN hứa hẹn sẽ gi&uacute;p bạn x&acirc;y dựng nền tảng vững chắc v&agrave; th&agrave;nh thạo trong lập tr&igrave;nh.</p>
<p>Trong kh&oacute;a học n&agrave;y, ch&uacute;ng ta sẽ tập trung v&agrave;o việc kh&aacute;m ph&aacute; v&agrave; hiểu r&otilde; c&aacute;c cấu tr&uacute;c dữ liệu quan trọng như mảng, chuỗi k&yacute; tự, danh s&aacute;ch li&ecirc;n kết, ngăn xếp, h&agrave;ng đợi, bảng băm, tập hợp, c&acirc;y, đồ thị v&agrave; heap. C&aacute;c cấu tr&uacute;c dữ liệu n&agrave;y l&agrave; nền tảng của lập tr&igrave;nh, gi&uacute;p ch&uacute;ng ta giải quyết c&aacute;c vấn đề phức tạp một c&aacute;ch hiệu quả.</p>
<p>Kh&oacute;a học cũng sẽ gi&uacute;p bạn hiểu r&otilde; c&aacute;c thuật to&aacute;n cơ bản v&agrave; n&acirc;ng cao, bao gồm thuật to&aacute;n sắp xếp, thuật to&aacute;n t&igrave;m kiếm, thuật to&aacute;n t&igrave;m kiếm nhị ph&acirc;n, thuật to&aacute;n t&igrave;m kiếm chuỗi k&yacute; tự, giải thuật tham lam, thuật to&aacute;n quay lui v&agrave; quy hoạch động. Bạn sẽ học c&aacute;ch &aacute;p dụng c&aacute;c thuật to&aacute;n n&agrave;y v&agrave;o c&aacute;c vấn đề thực tế, gi&uacute;p tăng cường kỹ năng giải quyết vấn đề của m&igrave;nh.</p>
<p>Ngo&agrave;i ra, ch&uacute;ng m&igrave;nh sẽ chia sẻ một số kinh nghiệm cần thiết cho buổi phỏng vấn, gi&uacute;p bạn chuẩn bị tốt nhất cho c&aacute;c cơ hội nghề nghiệp li&ecirc;n quan đến lập tr&igrave;nh trong tương lai. Bạn sẽ được học c&aacute;ch hiểu r&otilde; y&ecirc;u cầu của người phỏng vấn, thể hiện kỹ năng lập tr&igrave;nh của m&igrave;nh một c&aacute;ch hiệu quả v&agrave; trả lời c&aacute;c c&acirc;u hỏi một c&aacute;ch tr&ocirc;i chảy. Ch&uacute;ng m&igrave;nh tự tin rằng, sau khi bạn ho&agrave;n th&agrave;nh kh&oacute;a học n&agrave;y, bạn sẽ trở n&ecirc;n nhạy b&eacute;n trong tư duy lập tr&igrave;nh hiệu quả.</p>
<p>H&atilde;y tham gia kh&oacute;a học n&agrave;y để t&igrave;m hiểu s&acirc;u hơn về lập tr&igrave;nh v&agrave; mở rộng kỹ năng của bạn. TEK4.VN rất mong được hỗ trợ bạn trong qu&aacute; tr&igrave;nh học tập n&agrave;y.</p>

Cấu trúc dữ liệu và Giải thuật

<p style="text-align: justify;">Như đ&atilde; n&oacute;i ở b&agrave;i trước, cấu tr&uacute;c dữ liệu v&agrave; giải thuật l&agrave; một trong những kh&aacute;i niệm cần thiết m&agrave; c&aacute;c bạn lập tr&igrave;nh vi&ecirc;n cần nắm vững. N&oacute; c&oacute; gi&aacute; trị lớn hơn nhiều việc th&agrave;nh thạo nhiều ng&ocirc;n ngữ lập tr&igrave;nh. Mặc d&ugrave;, về cơ bản c&oacute; thể c&aacute;c bạn vẫn c&oacute; thể đi l&agrave;m b&igrave;nh thường trong c&aacute;c doanh nghiệp v&agrave; vẫn đạt được kết quả tốt trong việc lập tr&igrave;nh m&agrave; kh&ocirc;ng cần phải giỏi cấu tr&uacute;c dữ liệu v&agrave; giải thuật, tuy nhi&ecirc;n, việc c&aacute;c bạn nắm vững trong tay về cấu tr&uacute;c dữ liệu v&agrave; giải thuật sẽ gi&uacute;p tiến xa hơn trong c&ocirc;ng việc sau n&agrave;y. Đ&oacute; l&agrave; l&yacute; do tại sao c&aacute;c c&ocirc;ng ty lớn như Google, Facebook v&agrave; Amazon lại thu&ecirc; c&aacute;c lập tr&igrave;nh vi&ecirc;n đặc biệt giỏi trong việc tối ưu h&oacute;a thuật to&aacute;n. Khi bạn đi l&agrave;m thực tế gần như c&ocirc;ng nghệ v&agrave; ng&ocirc;n ngữ lu&ocirc;n thay đổi chỉ c&oacute; phương ph&aacute;p giải quyết vấn đề kh&ocirc;ng đổi. Đ&oacute; ch&iacute;nh l&agrave; tư duy lập tr&igrave;nh v&agrave; thuật to&aacute;n.</p>
<h2 id="ftoc-heading-2" class="ftwp-heading" style="text-align: justify;"><strong>C&ocirc;ng dụng của cấu tr&uacute;c dữ liệu v&agrave; thuật to&aacute;n</strong></h2>
<h3 id="ftoc-heading-3" class="ftwp-heading" style="text-align: justify;"><strong>Tiết kiệm thời gian</strong></h3>
<p style="text-align: justify;">Giả sử, Alice v&agrave; Bob đang cố gắng giải một b&agrave;i to&aacute;n đơn giản l&agrave; t&igrave;m tổng của $10^{11}$ số tự nhi&ecirc;n đầu ti&ecirc;n.</p>
<h4 style="text-align: justify;"><strong>Thuật to&aacute;n của Bob:</strong></h4>
<ul style="text-align: justify;">
<li>Bước 1: Khởi tạo biến <code>sum = 0.</code></li>
<li>Bước 2: V&ograve;ng lặp <code>for</code> cho mỗi gi&aacute; trị số tự nhi&ecirc;n $n$ trong khoảng $1$ tới $10^{11}$:
<ul>
<li>Cộng $n$ v&agrave;o biến <code>sum.</code></li>
</ul>
</li>
<li>Bước 3: In ra biến <code>sum.</code></li>
</ul>
<p style="text-align: justify;">Đoạn m&atilde; được viết bởi Bob c&oacute; dạng như sau:</p>
<pre class="language-cpp"><code>int findSum() {
    int sum = 0;
    for (int v = 1; v &lt;= 100000000000; v++) {
        sum += v;
    }
    return sum;
}</code></pre>
<p style="text-align: justify;">Sau khi viết xong chương tr&igrave;nh, Bob đang cảm thấy rất phấn kh&iacute;ch v&igrave; đ&atilde; ho&agrave;n th&agrave;nh xuất sắc b&agrave;i tập n&agrave;y. Tuy nhi&ecirc;n, khi thực thi đoạn m&atilde; b&ecirc;n tr&ecirc;n, đ&atilde; c&oacute; một vấn đề xảy ra l&agrave; chương tr&igrave;nh sẽ kh&ocirc;ng hiển thị ra kết quả. Vậy, điều g&igrave; đ&atilde; xảy ra với đoạn m&atilde; đơn giản như vậy?</p>
<p style="text-align: justify;">Hai trong số những t&agrave;i nguy&ecirc;n qu&yacute; gi&aacute; nhất cho một chương tr&igrave;nh m&aacute;y t&iacute;nh l&agrave; thời gian v&agrave; bộ nhớ.</p>
<p style="text-align: justify;">Thời gian m&aacute;y t&iacute;nh thực thi của một đoạn m&atilde; l&agrave;:</p>
<pre class="language-python"><code>Thời gian thực thi = Số lượng c&acirc;u lệnh * Thời gian thực thi cho một c&acirc;u lệnh</code></pre>
<p style="text-align: justify;">Số lượng c&acirc;u lệnh phụ thuộc v&agrave;o đoạn m&atilde; m&agrave; bạn đ&atilde; sử dụng v&agrave; thời gian thực thi cho mỗi c&acirc;u lệnh t&ugrave;y thuộc v&agrave;o m&aacute;y t&iacute;nh v&agrave; tr&igrave;nh bi&ecirc;n dịch của bạn.</p>
<p style="text-align: justify;">Trong trường hợp b&ecirc;n tr&ecirc;n, tổng số c&aacute;c c&acirc;u lệnh được thực thi (giả sử x) l&agrave;:</p>
<ul style="text-align: justify;">
<li style="text-align: left;">$x = 1 + (10^{11} + 1) + 10^{11} + 1$, tương đương l&agrave; $x = 2 \times 10^{11} + 3$</li>
</ul>
<p style="text-align: justify;">Giả sử rằng một m&aacute;y t&iacute;nh c&oacute; thể thực hiện c&aacute;c c&acirc;u lệnh $y = 10^{8}$ trong một gi&acirc;y (n&oacute; c&oacute; thể thay đổi t&ugrave;y theo cấu h&igrave;nh m&aacute;y t&iacute;nh). Thời gian thực hiện để thực thi đoạn m&atilde; tr&ecirc;n l&agrave;:</p>
<ul style="text-align: justify;">
<li>Thời gian thực thi đoạn m&atilde; = $\displaystyle\frac{x}{y} = \displaystyle\frac{3 + 2 \times 10^{11}}{10^{8}}$ (lớn hơn 16 ph&uacute;t)</li>
</ul>
<p style="text-align: justify;">Vậy liệu rằng c&oacute; thể tối ưu h&oacute;a thuật to&aacute;n để Alice v&agrave; Bob kh&ocirc;ng phải đợi 16 ph&uacute;t mỗi khi họ thực thi đoạn m&atilde; b&ecirc;n tr&ecirc;n n&agrave;y hay kh&ocirc;ng? C&acirc;u trả lời l&agrave; ho&agrave;n to&agrave;n c&oacute; thể.</p>
<h4 style="text-align: justify;"><strong>Thuật to&aacute;n của Alice:</strong></h4>
<p style="text-align: justify;">Tổng của $N$ số tự nhi&ecirc;n đầu ti&ecirc;n được cho bởi c&ocirc;ng thức như sau:</p>
<ul style="text-align: justify;">
<li>sum = $\displaystyle\frac{N \times (N + 1)}{2}$</li>
</ul>
<p style="text-align: justify;">Đoạn m&atilde; thực thi c&oacute; dạng như sau:</p>
<pre class="language-cpp"><code>int sum(int N) {
    return N * (N + 1) / 2;
}</code></pre>
<p style="text-align: justify;">Đoạn m&atilde; n&agrave;y thực thi chỉ trong một c&acirc;u lệnh v&agrave; ho&agrave;n th&agrave;nh nhiệm vụ bất kể với gi&aacute; trị l&agrave; bao nhi&ecirc;u. Thời gian cần thiết để giải quyết vấn đề, trong trường hợp n&agrave;y, l&agrave; $\frac{1}{y}$ (l&agrave; 10 nano gi&acirc;y). Một điều th&uacute; vị kh&aacute;c l&agrave; một quả bom nhiệt hạch để xảy ra phản ứng sẽ mất 40-50 ns, điều n&agrave;y c&oacute; nghĩa l&agrave; chương tr&igrave;nh của bạn sẽ ho&agrave;n th&agrave;nh th&agrave;nh c&ocirc;ng ngay cả khi ai đ&oacute; n&eacute;m bom v&agrave;o m&aacute;y t&iacute;nh của bạn c&ugrave;ng l&uacute;c bạn thực thi đoạn m&atilde; của m&igrave;nh.</p>
<h3 id="ftoc-heading-4" class="ftwp-heading" style="text-align: justify;"><strong>Khả năng mở rộng</strong></h3>
<p style="text-align: justify;">Khả năng mở rộng l&agrave; khả năng mở rộng quy m&ocirc;, c&oacute; nghĩa l&agrave; chất lượng của một thuật to&aacute;n hoặc hệ thống để xử l&yacute; vấn đề c&oacute; k&iacute;ch thước lớn hơn.</p>
<p style="text-align: justify;">H&atilde;y xem x&eacute;t vấn đề thiết lập một ph&ograve;ng học c&oacute; 50 học sinh. Một trong những giải ph&aacute;p đơn giản nhất l&agrave; đặt ph&ograve;ng, lấy bảng đen, một v&agrave;i vi&ecirc;n phấn v&agrave; vấn đề đ&atilde; được giải quyết. Nhưng nếu quy m&ocirc; của vấn đề tăng l&ecirc;n th&igrave; sao? Nếu số học sinh tăng l&ecirc;n 200, vấn đề cần giải quyết sẽ ra sao? Giải ph&aacute;p vẫn được duy tr&igrave; nhưng n&oacute; cần nhiều nguồn lực hơn. Trong trường hợp n&agrave;y, bạn c&oacute; thể sẽ cần một căn ph&ograve;ng lớn hơn nhiều (c&oacute; thể l&agrave; rạp chiếu phim), một m&agrave;n h&igrave;nh m&aacute;y chiếu v&agrave; một c&acirc;y b&uacute;t kỹ thuật số. Nhưng điều g&igrave; sẽ xảy ra nếu số học sinh tăng l&ecirc;n 1000?</p>
<p style="text-align: justify;">Giải ph&aacute;p kh&ocirc;ng th&agrave;nh c&ocirc;ng hoặc sử dụng nhiều t&agrave;i nguy&ecirc;n khi quy m&ocirc; của vấn đề tăng l&ecirc;n. Điều n&agrave;y c&oacute; nghĩa l&agrave;, giải ph&aacute;p của bạn kh&ocirc;ng thể mở rộng. Vậy giải ph&aacute;p c&oacute; thể mở rộng l&agrave; g&igrave;?</p>
<p style="text-align: justify;">H&atilde;y xem x&eacute;t một trang Web l&agrave; Video, h&agrave;ng triệu sinh vi&ecirc;n c&oacute; thể xem video, đọc c&acirc;u trả lời c&ugrave;ng một l&uacute;c v&agrave; kh&ocirc;ng cần th&ecirc;m t&agrave;i nguy&ecirc;n. Giải ph&aacute;p n&agrave;y c&oacute; thể giải quyết c&aacute;c vấn đề về k&iacute;ch thước lớn hơn trong điều kiện t&agrave;i nguy&ecirc;n bị hạn chế. Nếu bạn thấy giải ph&aacute;p đầu ti&ecirc;n để t&igrave;m tổng của $N$ số tự nhi&ecirc;n đầu ti&ecirc;n, n&oacute; kh&ocirc;ng thể mở rộng được. Đ&oacute; l&agrave; bởi v&igrave; n&oacute; đ&ograve;i hỏi mức độ tăng dần tuyến t&iacute;nh theo thời gian với sự thay đổi tuyến t&iacute;nh theo quy m&ocirc; của vấn đề. C&aacute;c thuật to&aacute;n như vậy được gọi l&agrave; c&aacute;c thuật to&aacute;n c&oacute; thể mở rộng tuyến t&iacute;nh. Giải ph&aacute;p thứ hai c&oacute; thể mở rộng v&agrave; kh&ocirc;ng cần sử dụng th&ecirc;m thời gian để giải quyết vấn đề c&oacute; k&iacute;ch thước lớn hơn được gọi l&agrave; thuật to&aacute;n thời gian kh&ocirc;ng đổi.</p>
<h3 id="ftoc-heading-5" class="ftwp-heading" style="text-align: justify;"><strong>Tiết kiệm bộ nhớ</strong></h3>
<p style="text-align: justify;">Bộ nhớ kh&ocirc;ng phải l&uacute;c n&agrave;o cũng dồi d&agrave;o. Trong khi xử l&yacute; đoạn m&atilde; hoặc hệ thống đ&ograve;i hỏi bạn phải lưu trữ hoặc tạo ra nhiều dữ liệu, điều quan trọng đối với thuật to&aacute;n của bạn l&agrave; tiết kiệm việc sử dụng bộ nhớ bất cứ khi n&agrave;o c&oacute; thể. V&iacute; dụ, trong khi lưu trữ dữ liệu về mọi người, bạn c&oacute; thể tiết kiệm bộ nhớ bằng c&aacute;ch chỉ lưu trữ ng&agrave;y sinh, kh&ocirc;ng lưu trữ số tuổi của họ.</p>
<h2 id="ftoc-heading-6" class="ftwp-heading" style="text-align: justify;"><strong>V&iacute; dụ về t&iacute;nh hiệu quả của một thuật to&aacute;n</strong></h2>
<p style="text-align: justify;">Sau đ&acirc;y l&agrave; một v&iacute; dụ về những g&igrave; thuật to&aacute;n v&agrave; cấu tr&uacute;c dữ liệu c&oacute; thể gi&uacute;p bạn.</p>
<p style="text-align: justify;">Vấn đề nh&oacute;m tuổi:&nbsp;C&aacute;c vấn đề như t&igrave;m người ở một nh&oacute;m tuổi nhất định c&oacute; thể dễ d&agrave;ng được giải quyết với một dạng sửa đổi một ch&uacute;t của thuật to&aacute;n t&igrave;m kiếm nhị ph&acirc;n (giả sử rằng dữ liệu đ&atilde; được sắp xếp).</p>
<p style="text-align: justify;">Thuật to&aacute;n th&ocirc;ng thường sẽ duyệt qua tất cả từng người một v&agrave; kiểm tra xem người đ&oacute; c&oacute; thuộc nh&oacute;m tuổi nhất định hay kh&ocirc;ng. Trong khi đ&oacute;, t&igrave;m kiếm nhị ph&acirc;n l&agrave; một thuật to&aacute;n c&oacute; thể mở rộng theo dạng đồ thị logarit. Điều n&agrave;y c&oacute; nghĩa l&agrave; nếu k&iacute;ch thước của vấn đề l&agrave; một gi&aacute; trị số b&igrave;nh phương, th&igrave; thời gian cần thiết để giải quyết n&oacute; sẽ tăng l&ecirc;n gấp đ&ocirc;i.</p>
<p style="text-align: justify;">Giả sử, ch&uacute;ng ta sử dụng thuật to&aacute;n th&ocirc;ng thường sẽ mất 1 gi&acirc;y để t&igrave;m tất cả những người ở một độ tuổi nhất định cho một nh&oacute;m 1000. Sau đ&oacute;, với một nh&oacute;m c&oacute; một triệu người, thuật to&aacute;n t&igrave;m kiếm nhị ph&acirc;n sẽ chỉ mất 2 gi&acirc;y để giải quyết vấn đề, thuật to&aacute;n th&ocirc;ng thường c&oacute; thể mất 1 triệu gi&acirc;y, tức khoảng 12 ng&agrave;y.</p>
<h2 id="ftoc-heading-7" class="ftwp-heading" style="text-align: justify;">Kết luận</h2>
<p style="text-align: justify;">Như vậy, ph&aacute;t triển phần mềm li&ecirc;n quan đến việc học c&aacute;c c&ocirc;ng nghệ mới h&agrave;ng ng&agrave;y. Bạn c&oacute; thể t&igrave;m hiểu hầu hết c&aacute;c c&ocirc;ng nghệ n&agrave;y khi sử dụng ch&uacute;ng trong một trong c&aacute;c dự &aacute;n của m&igrave;nh. Tuy nhi&ecirc;n, n&oacute; sẽ kh&ocirc;ng xảy ra với c&aacute;c thuật to&aacute;n. Nếu bạn kh&ocirc;ng biết r&otilde; về c&aacute;c thuật to&aacute;n, bạn sẽ kh&ocirc;ng thể x&aacute;c định được liệu bạn c&oacute; thể tối ưu h&oacute;a đoạn m&atilde; m&agrave; bạn đang viết hay kh&ocirc;ng. Bạn phải biết trước về ch&uacute;ng v&agrave; &aacute;p dụng ch&uacute;ng bất cứ khi n&agrave;o c&oacute; thể. Ch&uacute;ng ta đ&atilde; n&oacute;i về khả năng mở rộng của c&aacute;c thuật to&aacute;n. Một hệ thống phần mềm bao gồm nhiều thuật to&aacute;n, do đ&oacute;, việc tối ưu h&oacute;a bất kỳ một trong số ch&uacute;ng sẽ dẫn đến một hệ thống tốt hơn.</p>
<p style="text-align: justify;">T&oacute;m lại, việc nắm vững c&aacute;c kiến thức về thuật to&aacute;n v&agrave; cấu tr&uacute;c dữ liệu l&agrave; v&ocirc; c&ugrave;ng cần thiết. V&agrave; bạn sẽ c&oacute; thể đạt được điều đ&oacute;, th&ocirc;ng qua kh&oacute;a học n&agrave;y. Trong b&agrave;i tiếp theo, ch&uacute;ng ta sẽ tiếp tục luyện tập với một b&agrave;i tập đơn giản trước khi điểm qua về c&aacute;c nội dung tiếp theo sẽ được tr&igrave;nh b&agrave;y trong kh&oacute;a học.</p>

Tại sao cần học cấu trúc dữ liệu và giải thuật?