<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;">[___TIP_B&agrave;i n&agrave;y l&agrave; một b&agrave;i đọc th&ecirc;m gi&uacute;p bạn c&oacute; thể hiểu được c&aacute;ch t&iacute;nh độ phức tạp t&iacute;nh to&aacute;n cho c&aacute;c thuật to&aacute;n đệ quy. Bạn ho&agrave;n to&agrave;n c&oacute; thể bỏ qua b&agrave;i n&agrave;y nếu kh&ocirc;ng quan t&acirc;m lắm._TIP___]</p>
<p style="text-align: justify;">Trong b&agrave;i trước, ch&uacute;ng ta đ&atilde; nhắc lại một số vấn đề li&ecirc;n quan đến kỹ thuật đệ quy. Đệ quy rất ngắn gọn v&agrave; hiệu quả tuy nhi&ecirc;n độ phức tạp của n&oacute; lại rất kh&oacute; đ&aacute;nh gi&aacute; một c&aacute;ch ch&iacute;nh x&aacute;c. Để đ&aacute;nh gi&aacute; thuật to&aacute;n đệ quy ch&uacute;ng ta thường ước lượng n&oacute; bằng định l&yacute; thợ (Master Theorem).</p>
<p style="text-align: justify;">Hầu hết c&aacute;c thuật to&aacute;n c&oacute; bản chất l&agrave; đệ quy hay v&ograve;ng lặp, ch&uacute;ng sử dụng chiến lược chia để trị. Thuật to&aacute;n đệ quy sẽ gọi ch&iacute;nh n&oacute; với c&aacute;c đầu v&agrave;o kh&aacute;c nhau. Để giải hệ thức truy hồi trong đệ quy c&oacute; rất nhiều c&aacute;ch bao gồm:</p>
<ul style="text-align: justify;">
<li>Định l&yacute; thợ</li>
<li>Phương ph&aacute;p c&acirc;y lặp</li>
<li>Phương ph&aacute;p thay thế</li>
<li>Phương ph&aacute;p thay đổi biến</li>
</ul>
<p style="text-align: justify;">Trong số tất cả c&aacute;c phương ph&aacute;p n&agrave;y, định l&yacute; thợ l&agrave; phương ph&aacute;p nhanh nhất để t&igrave;m độ phức tạp về thời gian của h&agrave;m. N&oacute; rất dễ hiểu v&agrave; dễ &aacute;p dụng.</p>
<p style="text-align: justify;">Phương thức định l&yacute; thợ l&agrave; một c&ocirc;ng thức để giải quyết c&aacute;c quan hệ lặp c&oacute; dạng như sau:</p>
<pre class="language-cpp"><code>T(n) = aT(n/b) + f(n)</code></pre>
<p style="text-align: justify;">Trong đ&oacute;:</p>
<ul style="text-align: justify;">
<li><code>n</code> l&agrave; k&iacute;ch thước đầu v&agrave;o</li>
<li><code>a</code> l&agrave; số b&agrave;i to&aacute;n con trong đệ quy</li>
<li><code>n/b</code> l&agrave; k&iacute;ch thước của mỗi b&agrave;i to&aacute;n con. Tất cả c&aacute;c b&agrave;i to&aacute;n con đều được giả định để c&oacute; c&ugrave;ng k&iacute;ch thước.</li>
<li><code>f(n)</code> l&agrave; chi ph&iacute; của c&ocirc;ng việc được thực hiện b&ecirc;n ngo&agrave;i lời gọi đệ quy, trong đ&oacute; bao gồm chi ph&iacute; ph&acirc;n chia vấn đề v&agrave; chi ph&iacute; hợp nhất c&aacute;c giải ph&aacute;p</li>
</ul>
<p style="text-align: justify;">Ở đ&acirc;y, <code>a &ge; 1</code> v&agrave; <code>b &gt; 1</code> l&agrave; c&aacute;c hằng số v&agrave; <code>f(n)</code> l&agrave; một h&agrave;m tiệm cận dương. Một h&agrave;m tiệm cận dương c&oacute; nghĩa l&agrave; với một gi&aacute; trị đủ lớn của <code>n</code>, ta c&oacute; <code>f(n)&gt; 0</code>.</p>
<p style="text-align: justify;">Định l&yacute; thợ được sử dụng để t&iacute;nh to&aacute;n độ phức tạp về thời gian của c&aacute;c quan hệ lặp lại (thuật to&aacute;n chia để trị) một c&aacute;ch đơn giản v&agrave; nhanh ch&oacute;ng.</p>
<h2 id="ftoc-heading-1" class="ftwp-heading" style="text-align: justify;">Định l&yacute; thợ (Master Theorem)</h2>
<p style="text-align: justify;">Nếu <code>a &ge; 1</code> v&agrave; <code>b &gt; 1</code> l&agrave; c&aacute;c hằng số v&agrave; <code>f(n)</code> l&agrave; một h&agrave;m tiệm cận dương, th&igrave; độ phức tạp về thời gian của một quan hệ đệ quy được cho bởi.</p>
<pre class="language-cpp"><code>T(n) = aT(n/b) + f(n)</code></pre>
<p style="text-align: justify;">Trong đ&oacute;, <code>T(n)</code> c&oacute; c&aacute;c giới hạn tiệm cận sau:</p>
<ol style="text-align: justify;">
<li>Nếu $f(n) = O(n^{log_b(a - \epsilon)})$ th&igrave; $T(n) = \Theta(n^{log_b(a)})$.</li>
<li>Nếu $f(n) = &nbsp;\Theta(n^{log_b(a)})$ th&igrave; $T(n) = \Theta(n^{log_b(a)} \times log_n)$.</li>
<li>Nếu $f(n) = \Omega(n^{log_b(a + \epsilon)})$ th&igrave; $T(n) = \Theta(f(n))$.</li>
<li>$\epsilon &gt; 0$ l&agrave; hằng số.</li>
</ol>
<div id="urvanov-syntax-highlighter-61076d76755cf179777840" class="urvanov-syntax-highlighter-syntax crayon-theme-classic urvanov-syntax-highlighter-font-monaco urvanov-syntax-highlighter-os-pc print-yes notranslate" data-settings=" minimize scroll-mouseover">
<div class="crayon-toolbar" data-settings=" mouseover overlay hide delay">
<div class="crayon-tools">
<div class="crayon-button urvanov-syntax-highlighter-nums-button crayon-pressed" title="Toggle Line Numbers">
<div class="urvanov-syntax-highlighter-button-icon" style="text-align: justify;">
<p style="text-align: justify;">Mỗi điều kiện tr&ecirc;n c&oacute; thể được hiểu như sau:</p>
<ul style="text-align: justify;">
<li style="text-align: justify;">Nếu chi ph&iacute; giải c&aacute;c b&agrave;i to&aacute;n con ở mỗi cấp tăng l&ecirc;n một hệ số nhất định, gi&aacute; trị của <code>f(n)</code> sẽ trở n&ecirc;n nhỏ hơn $n^{log_ba}$. Do đ&oacute;, độ phức tạp về thời gian bị hạn chế bởi chi ph&iacute; của mức cuối c&ugrave;ng tức l&agrave; $n^{log_ba}$.</li>
<li style="text-align: justify;">Nếu chi ph&iacute; giải b&agrave;i to&aacute;n con ở mỗi cấp l&agrave; gần bằng nhau th&igrave; gi&aacute; trị của <code>f(n)</code> sẽ l&agrave; $n^{log_ba}$. Do đ&oacute;, độ phức tạp về thời gian sẽ gấp<code> f(n)</code> lần tổng số c&aacute;c mức tức l&agrave; $n^{log_ba} \times log(n)$</li>
<li style="text-align: justify;">Nếu chi ph&iacute; giải c&aacute;c b&agrave;i to&aacute;n con ở mỗi cấp giảm đi một hệ số nhất định, gi&aacute; trị của <code>f(n)</code> sẽ trở n&ecirc;n lớn hơn $n^{log_ba}$. Do đ&oacute;, độ phức tạp về thời gian bị hạn chế bởi chi ph&iacute; <code>f(n)</code>.</li>
</ul>
<h2 id="ftoc-heading-2" class="ftwp-heading" style="text-align: justify;">V&iacute; dụ</h2>
<pre class="language-cpp"><code>T(n) = 3T(n/2) + n2</code></pre>
<p style="text-align: justify;">Trong đ&oacute;:</p>
<ul style="text-align: justify;">
<li>$a = 3$</li>
<li>$\frac{n}{b} = \frac{n}{2}$</li>
<li>$f(n) = n^2$</li>
<li>$log_ba = log_23 \approx 1.58 &lt; 2 $</li>
</ul>
<p style="text-align: justify;">Tức l&agrave; $f(n) &lt; n^{log_b(a + \epsilon)}$, trong đ&oacute;,&nbsp; $\epsilon$ l&agrave; một hằng số</p>
<p style="text-align: justify;">Trường hợp 3 được &aacute;p dụng tại đ&acirc;y</p>
<p style="text-align: justify;">V&igrave; vậy, $T(n) = f(n) = \Theta(n^2)$</p>
<h2 id="ftoc-heading-3" class="ftwp-heading" style="text-align: justify;">Giới hạn của định l&yacute; thợ</h2>
<p style="text-align: justify;">Kh&ocirc;ng thể sử dụng định l&yacute; thợ nếu:</p>
<ul style="text-align: justify;">
<li>$T(n)$ &nbsp;kh&ocirc;ng c&oacute; t&iacute;nh đơn điệu. v&iacute; dụ, $T(n) = sin(n)$</li>
<li>$f(n)$ kh&ocirc;ng phải l&agrave; một đa thức. v&iacute; dụ. $f(n) = 2n$</li>
<li>$a$ kh&ocirc;ng phải l&agrave; hằng số. v&iacute; dụ, $a = 2n$</li>
<li>$a &lt; 1$</li>
</ul>
<p style="text-align: justify;">Tr&ecirc;n đ&acirc;y l&agrave; kh&aacute;i niệm v&agrave; v&iacute; dụ cơ bản về định l&yacute; thợ (Master Theorem). N&oacute; được sử dụng để đ&aacute;nh gi&aacute; độ phức tạp cho c&aacute;c giải thuật dạng đệ quy với chiến lược giải hệ thức truy hồi cho b&agrave;i to&aacute;n đệ quy.</p>
</div>
</div>
</div>
</div>
</div>

Ước lượng độ phức tạp của đệ quy bằng định lý thợ (Master Theorem)