Độ phức tạp tính toán

<p style="text-align: justify;">Trong b&agrave;i viết n&agrave;y, ta sẽ c&ugrave;ng t&igrave;m hiểu về độ phức tạp t&iacute;nh to&aacute;n của một thuật to&aacute;n. Ta sẽ thực hiện triển khai v&iacute; dụ để đo độ phức tạp t&iacute;nh to&aacute;n của một giải thuật.</p> <p style="text-align: justify;">Cấu tr&uacute;c dữ liệu được thực hiện bằng c&aacute;c thuật to&aacute;n. Thuật to&aacute;n l&agrave; một thủ tục m&agrave; ta c&oacute; thể viết dưới dạng h&agrave;m hoặc chương tr&igrave;nh C hoặc bất kỳ ng&ocirc;n ngữ n&agrave;o kh&aacute;c. Một thuật to&aacute;n chỉ ra r&otilde; c&aacute;ch dữ liệu sẽ được thao t&aacute;c.</p> <p style="text-align: justify;">Sẽ c&oacute; một số thuật to&aacute;n hiệu quả hơn những thuật to&aacute;n kh&aacute;c. Tuy nhi&ecirc;n, ch&uacute;ng ta chắc chắn sẽ muốn chọn một thuật to&aacute;n sao cho hiệu quả nhất, v&igrave; vậy sẽ rất tốt nếu c&oacute; c&aacute;c số liệu để so s&aacute;nh hiệu quả của ch&uacute;ng để từ đ&oacute; ta c&oacute; thể đưa ra lựa chọn ch&iacute;nh x&aacute;c.</p> <p style="text-align: justify;">Giả sử X được coi l&agrave; một thuật to&aacute;n v&agrave; N được coi l&agrave; k&iacute;ch thước của dữ liệu đầu v&agrave;o, thời gian v&agrave; kh&ocirc;ng gian được thực hiện bởi thuật to&aacute;n X sẽ l&agrave; hai yếu tố ch&iacute;nh quyết định hiệu quả của X.</p> <ol style="text-align: justify;"> <li>Hệ số về thời gian: Thời gian được t&iacute;nh to&aacute;n hoặc đo lường bằng c&aacute;ch đếm số lượng c&aacute;c hoạt động ch&iacute;nh như so s&aacute;nh trong thuật to&aacute;n sắp xếp.</li> <li>Hệ số kh&ocirc;ng gian: Kh&ocirc;ng gian được t&iacute;nh to&aacute;n hoặc đo bằng c&aacute;ch đếm kh&ocirc;ng gian bộ nhớ tối đa m&agrave; thuật to&aacute;n y&ecirc;u cầu.</li> </ol> <p style="text-align: justify;">Độ phức tạp của thuật to&aacute;n f(N) sẽ cung cấp th&ocirc;ng tin về thời gian thực thi hoặc kh&ocirc;ng gian lưu trữ cần thiết của thuật to&aacute;n đối với N l&agrave; k&iacute;ch thước của dữ liệu đầu v&agrave;o.</p> <h2 id="ftoc-heading-2" class="ftwp-heading" style="text-align: justify;">1. Độ phức tạp về kh&ocirc;ng gian</h2> <p style="text-align: justify;">Độ phức tạp về kh&ocirc;ng gian của một thuật to&aacute;n biểu thị lượng kh&ocirc;ng gian bộ nhớ cần thiết của thuật to&aacute;n. Kh&ocirc;ng gian cần thiết của một thuật to&aacute;n bằng tổng của hai th&agrave;nh phần sau:</p> <ol> <li style="text-align: justify;">Phần cố định l&agrave; kh&ocirc;ng gian cần thiết để lưu trữ dữ liệu v&agrave; biến nhất định (tức l&agrave; biến v&agrave; hằng số đơn giản, k&iacute;ch thước chương tr&igrave;nh), kh&ocirc;ng phụ thuộc v&agrave;o quy m&ocirc; của b&agrave;i to&aacute;n.</li> <li style="text-align: justify;">Phần biến l&agrave; một kh&ocirc;ng gian được y&ecirc;u cầu bởi c&aacute;c biến, k&iacute;ch thước của n&oacute; ho&agrave;n to&agrave;n phụ thuộc v&agrave;o k&iacute;ch thước của b&agrave;i to&aacute;n. V&iacute; dụ, kh&ocirc;ng gian ngăn xếp đệ quy, cấp ph&aacute;t bộ nhớ động.</li> </ol> <p>Độ phức tạp kh&ocirc;ng gian S(X) của c&aacute;c thuật to&aacute;n X l&agrave;&nbsp;<span id="urvanov-syntax-highlighter-610760f6c4699748038687" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-e">S</span><span class="crayon-sy">(</span><span class="crayon-v">X</span><span class="crayon-sy">)</span><span class="crayon-h">&nbsp;</span><span class="crayon-o">=</span><span class="crayon-h">&nbsp;</span><span class="crayon-v">A</span><span class="crayon-h">&nbsp;</span><span class="crayon-o">+</span><span class="crayon-h">&nbsp;</span><span class="crayon-e">S</span><span class="crayon-sy">(</span><span class="crayon-v">I</span><span class="crayon-sy">)</span></span></span>. Trong đ&oacute; A được coi l&agrave; phần cố định v&agrave; S(I) được coi l&agrave; phần biến của thuật to&aacute;n phụ thuộc v&agrave;o đặc t&iacute;nh c&aacute; thể I.</p> <h2 id="ftoc-heading-3" class="ftwp-heading">2. Độ phức tạp về thời gian</h2> <p>Độ phức tạp về thời gian của một thuật to&aacute;n l&agrave; sự thể hiện lượng thời gian m&agrave; thuật to&aacute;n cần để thực thi cho đến khi ho&agrave;n th&agrave;nh. Y&ecirc;u cầu về thời gian c&oacute; thể được biểu thị hoặc định nghĩa dưới dạng một h&agrave;m số t(N), trong đ&oacute; t(N) c&oacute; thể được đo bằng số bước, trong đ&oacute; mỗi bước c&oacute; thời gian kh&ocirc;ng đổi.</p> <p>V&iacute; dụ, trong trường hợp cộng hai số nguy&ecirc;n n bit, N bước được thực hiện. Do đ&oacute;, tổng thời gian t&iacute;nh to&aacute;n l&agrave; t(N) = c*n, trong đ&oacute; c l&agrave; thời gian d&ugrave;ng để cộng bit. Ở đ&acirc;y, ch&uacute;ng ta nhận thấy rằng t(N) tăng tuyến t&iacute;nh khi k&iacute;ch thước đầu v&agrave;o tăng l&ecirc;n.</p> <p>Độ phức tạp về thời gian của c&aacute;c thuật to&aacute;n thường được biểu thị bằng c&aacute;ch sử dụng k&yacute; hiệu O lớn. Đ&oacute; l&agrave; một k&yacute; hiệu tiệm cận để biểu thị độ phức tạp về thời gian. C&aacute;c bạn c&oacute; thể t&igrave;m hiểu về b&agrave;i viết <a href="../../ky-hieu-big-o-la-gi">k&yacute; hiệu Big O</a>.</p> <p>V&agrave; v&igrave; hiệu suất của thuật to&aacute;n c&oacute; thể thay đổi t&ugrave;y theo c&aacute;c loại dữ liệu đầu v&agrave;o kh&aacute;c nhau, do đ&oacute; đối với một thuật to&aacute;n, ch&uacute;ng ta thường sử dụng độ phức tạp thời gian trong trường hợp xấu nhất của một thuật to&aacute;n v&igrave; đ&oacute; l&agrave; thời gian tối đa cần thiết cho bất kỳ k&iacute;ch thước đầu v&agrave;o n&agrave;o.</p> <p>V&iacute; dụ, giả sử ch&uacute;ng ta muốn đặt một mảng gồm n số thập ph&acirc;n theo thứ tự tăng dần. B&agrave;i to&aacute;n n&agrave;y được gọi l&agrave; b&agrave;i to&aacute;n sắp xếp. Một thuật to&aacute;n đơn giản để sắp xếp l&agrave; sắp xếp lựa chọn (Selection Sort).</p> <p>Ta sẽ để một chỉ số i đi từ 0 đến n-1, đổi phần tử thứ i của mảng với phần tử nhỏ nhất từ i đến n. Dưới đ&acirc;y l&agrave; c&aacute;c lần lặp lại của thuật to&aacute;n sắp xếp lựa chọn được thực hiện tr&ecirc;n chuỗi&nbsp;<span id="urvanov-syntax-highlighter-610760f6c46a3032870348" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-sy">{</span><span class="crayon-cn">4</span><span class="crayon-sy">,</span><span class="crayon-h">&nbsp;</span><span class="crayon-cn">3</span><span class="crayon-sy">,</span><span class="crayon-h">&nbsp;</span><span class="crayon-cn">9</span><span class="crayon-sy">,</span><span class="crayon-h">&nbsp;</span><span class="crayon-cn">6</span><span class="crayon-sy">,</span><span class="crayon-h">&nbsp;</span><span class="crayon-cn">1</span><span class="crayon-sy">,</span><span class="crayon-h">&nbsp;</span><span class="crayon-cn">7</span><span class="crayon-sy">,</span><span class="crayon-h">&nbsp;</span><span class="crayon-cn">0</span><span class="crayon-sy">}</span></span></span>.</p> <table style="border-collapse: collapse; width: 99.9211%;" border="1"> <tbody> <tr> <td style="width: 23.3373%;" width="167">Chỉ số</td> <td style="width: 9.69146%;" width="66">0</td> <td style="width: 9.69146%;" width="66">1</td> <td style="width: 9.69146%;" width="66">2</td> <td style="width: 9.69146%;" width="66">3</td> <td style="width: 9.69146%;" width="66">4</td> <td style="width: 9.69146%;" width="66">5</td> <td style="width: 9.69834%;" width="66">6</td> </tr> <tr> <td style="width: 23.3373%;" width="167">i chưa được khởi tạo, mảng ban đầu</td> <td style="width: 9.69146%;" width="66">4</td> <td style="width: 9.69146%;" width="66">3</td> <td style="width: 9.69146%;" width="66">9</td> <td style="width: 9.69146%;" width="66">6</td> <td style="width: 9.69146%;" width="66">1</td> <td style="width: 9.69146%;" width="66">7</td> <td style="width: 9.69834%;" width="66">0</td> </tr> <tr> <td style="width: 23.3373%;" width="167">i=0</td> <td style="width: 9.69146%;" width="66">0</td> <td style="width: 9.69146%;" width="66">3</td> <td style="width: 9.69146%;" width="66">9</td> <td style="width: 9.69146%;" width="66">6</td> <td style="width: 9.69146%;" width="66">1</td> <td style="width: 9.69146%;" width="66">7</td> <td style="width: 9.69834%;" width="66">4</td> </tr> <tr> <td style="width: 23.3373%;" width="167">i=1</td> <td style="width: 9.69146%;" width="66">0</td> <td style="width: 9.69146%;" width="66">1</td> <td style="width: 9.69146%;" width="66">9</td> <td style="width: 9.69146%;" width="66">6</td> <td style="width: 9.69146%;" width="66">3</td> <td style="width: 9.69146%;" width="66">7</td> <td style="width: 9.69834%;" width="66">4</td> </tr> <tr> <td style="width: 23.3373%;" width="167">i=2</td> <td style="width: 9.69146%;" width="66">0</td> <td style="width: 9.69146%;" width="66">1</td> <td style="width: 9.69146%;" width="66">3</td> <td style="width: 9.69146%;" width="66">6</td> <td style="width: 9.69146%;" width="66">9</td> <td style="width: 9.69146%;" width="66">7</td> <td style="width: 9.69834%;" width="66">4</td> </tr> <tr> <td style="width: 23.3373%;" width="167">i=3</td> <td style="width: 9.69146%;" width="66">0</td> <td style="width: 9.69146%;" width="66">1</td> <td style="width: 9.69146%;" width="66">3</td> <td style="width: 9.69146%;" width="66">4</td> <td style="width: 9.69146%;" width="66">9</td> <td style="width: 9.69146%;" width="66">7</td> <td style="width: 9.69834%;" width="66">6</td> </tr> <tr> <td style="width: 23.3373%;" width="167">i=4</td> <td style="width: 9.69146%;" width="66">0</td> <td style="width: 9.69146%;" width="66">1</td> <td style="width: 9.69146%;" width="66">3</td> <td style="width: 9.69146%;" width="66">4</td> <td style="width: 9.69146%;" width="66">6</td> <td style="width: 9.69146%;" width="66">7</td> <td style="width: 9.69834%;" width="66">9</td> </tr> <tr> <td style="width: 23.3373%;" width="167">i=5</td> <td style="width: 9.69146%;" width="66">0</td> <td style="width: 9.69146%;" width="66">1</td> <td style="width: 9.69146%;" width="66">3</td> <td style="width: 9.69146%;" width="66">4</td> <td style="width: 9.69146%;" width="66">6</td> <td style="width: 9.69146%;" width="66">7</td> <td style="width: 9.69834%;" width="66">9</td> </tr> </tbody> </table> <p>Sau đ&acirc;y l&agrave; đoạn m&atilde; triển khai bằng ng&ocirc;n ngữ lập tr&igrave;nh C.</p> <pre class="language-cpp"><code>int find_min_index (float [], int, int); void swap (float [], int, int); void sort_selection (float v[], int n) { int i; for (i = 0; i &lt; n-1; i++) swap (v, i, find_min_index (v, i, n)); } int find_min_index (float v[], int begin, int end) { int i, mini; mini = begin; for (i = begin + 1; i &lt; end; i++) if (v[i] &lt; v[mini]) mini = i; return mini; } void swap(float v[], int i, int j) { float t; t = v[i]; v[i] = v[j]; v[j] = t; }</code></pre> <p style="text-align: justify;">B&acirc;y giờ ch&uacute;ng ta muốn định lượng hiệu suất của thuật to&aacute;n, tức l&agrave; lượng thời gian v&agrave; kh&ocirc;ng gian được thực hiện theo n. Ch&uacute;ng ta chủ yếu quan t&acirc;m đến việc y&ecirc;u cầu về thời gian v&agrave; kh&ocirc;ng gian thay đổi như thế n&agrave;o khi n dần c&agrave;ng lớn.</p> <p style="text-align: justify;">Đối với v&iacute; dụ n&agrave;y, lượng kh&ocirc;ng gian cần thiết bị chi phối r&otilde; r&agrave;ng bởi bộ nhớ được sử dụng bởi mảng. V&igrave; vậy, ch&uacute;ng ta chủ yếu quan t&acirc;m đến lượng thời gian m&agrave; thuật to&aacute;n thực hiện. Một c&aacute;ch tiếp cận l&agrave; đếm số lượng truy cập mảng được thực hiện trong qu&aacute; tr&igrave;nh thực thi thuật to&aacute;n, v&igrave; mỗi lần truy cập mảng mất một khoảng thời gian nhất định li&ecirc;n quan đến phần cứng, số lượng n&agrave;y tỷ lệ với thời gian thuật to&aacute;n thực hiện.</p> <p style="text-align: justify;">Ch&uacute;ng ta sẽ kết th&uacute;c với một h&agrave;m dựa theo n, cung cấp cho ch&uacute;ng ta số lượng truy cập mảng cho thuật to&aacute;n. Ch&uacute;ng ta sẽ gọi h&agrave;m l&agrave; T(n), cho thời gian.</p> <p style="text-align: justify;">T (n) l&agrave; tổng số lần truy cập được thực hiện từ đầu cho đến khi kết th&uacute;c.</p> <p style="text-align: center;">$T(n) = \sum_{i =0}^{n -2}[A + B(v, i, n)]$</p> <p style="text-align: justify;">Trong đ&oacute;:</p> <ul style="text-align: justify;"> <li>A l&agrave; thời gian để thực hiện ph&eacute;p ho&aacute;n đổi.</li> <li>B l&agrave; thời gian để thực hiện h&agrave;m t&igrave;m gi&aacute; trị min.</li> </ul> <p style="text-align: justify;">(n-2 v&igrave; v&ograve;ng lặp for đi từ 0 trở l&ecirc;n nhưng kh&ocirc;ng bao gồm n-1). H&agrave;m thực hiện ph&eacute;p ho&aacute;n đổi thực hiện bốn quyền truy cập v&agrave;o mảng, v&igrave; vậy h&agrave;m c&oacute; dạng l&agrave;:</p> <p style="text-align: center;">$T(n) = \sum_{i = 0}^{n - 2}[4 + B(v, i, n)]$</p> <p style="text-align: justify;">Nếu ch&uacute;ng ta nh&igrave;n v&agrave;o h&agrave;m t&igrave;m chỉ số nhỏ nhất, ch&uacute;ng ta thấy n&oacute; thực hiện hai truy cập mảng cho mỗi lần lặp th&ocirc;ng qua v&ograve;ng lặp for v&agrave; n&oacute; thực hiện v&ograve;ng lặp for n &ndash; i &ndash; 1 lần:</p> <p style="text-align: center;">$T(n) = \sum_{i = 0}^{n - 2}[4 + 2(n - i -1)]$</p> <p>Với một số thao t&aacute;c to&aacute;n học, ch&uacute;ng ta c&oacute; thể chia n&oacute; th&agrave;nh:</p> <p style="text-align: center;">$T(n) = 4(n - 1) + 2n(n - 1) - 2(n - 1) -2\sum_{i = 0}^{n - 2}i$</p> <p style="text-align: justify;">(Mọi thứ nh&acirc;n với n-1 v&igrave; ch&uacute;ng ta đi từ 0 đến n-2, tức l&agrave; n-1 lần). H&atilde;y nhớ rằng tổng của i khi i đi từ 0 đến n l&agrave; (n(n+1))/2, sau đ&oacute; thay thế v&agrave;o n-2 v&agrave; loại bỏ 2, ta c&oacute;:</p> <p style="text-align: center;">$T(n) = 4(n - 1) + 2n(n - 1) - 2(n - 1) - ((n - 2)(n - 1))$</p> <p style="text-align: left;">R&uacute;t gọn th&agrave;nh:</p> <p style="text-align: center;">$T(n) = n^2 + 3n - 4$</p> <p style="text-align: justify;">V&igrave; vậy, h&agrave;m n&agrave;y cung cấp cho ch&uacute;ng ta số lượng truy cập mảng m&agrave; h&agrave;m sắp xếp chọn tạo ra cho một k&iacute;ch thước mảng nhất định.</p> <table style="border-collapse: collapse; width: 32.253%; height: 440px; margin-left: auto; margin-right: auto;" border="1"> <tbody> <tr style="height: 22px;"> <td style="width: 48.8885%; text-align: center; height: 22px;" width="208">n</td> <td style="width: 48.8885%; text-align: center; height: 22px;" width="208">T(n)</td> </tr> <tr style="height: 22px;"> <td style="width: 48.8885%; text-align: center; height: 22px;" width="208">2</td> <td style="width: 48.8885%; text-align: center; height: 22px;" width="208">6</td> </tr> <tr style="height: 22px;"> <td style="width: 48.8885%; text-align: center; height: 22px;" width="208">3</td> <td style="width: 48.8885%; text-align: center; height: 22px;" width="208">14</td> </tr> <tr style="height: 22px;"> <td style="width: 48.8885%; text-align: center; height: 22px;" width="208">4</td> <td style="width: 48.8885%; text-align: center; height: 22px;" width="208">24</td> </tr> <tr style="height: 22px;"> <td style="width: 48.8885%; text-align: center; height: 22px;" width="208">5</td> <td style="width: 48.8885%; text-align: center; height: 22px;" width="208">36</td> </tr> <tr style="height: 22px;"> <td style="width: 48.8885%; text-align: center; height: 22px;" width="208">6</td> <td style="width: 48.8885%; text-align: center; height: 22px;" width="208">50</td> </tr> <tr style="height: 22px;"> <td style="width: 48.8885%; text-align: center; height: 22px;" width="208">7</td> <td style="width: 48.8885%; text-align: center; height: 22px;" width="208">66</td> </tr> <tr style="height: 22px;"> <td style="width: 48.8885%; text-align: center; height: 22px;" width="208">8</td> <td style="width: 48.8885%; text-align: center; height: 22px;" width="208">84</td> </tr> <tr style="height: 22px;"> <td style="width: 48.8885%; text-align: center; height: 22px;" width="208">9</td> <td style="width: 48.8885%; text-align: center; height: 22px;" width="208">104</td> </tr> <tr style="height: 22px;"> <td style="width: 48.8885%; text-align: center; height: 22px;" width="208">10</td> <td style="width: 48.8885%; text-align: center; height: 22px;" width="208">126</td> </tr> <tr style="height: 22px;"> <td style="width: 48.8885%; text-align: center; height: 22px;" width="208">11</td> <td style="width: 48.8885%; text-align: center; height: 22px;" width="208">150</td> </tr> <tr style="height: 22px;"> <td style="width: 48.8885%; text-align: center; height: 22px;" width="208">12</td> <td style="width: 48.8885%; text-align: center; height: 22px;" width="208">176</td> </tr> <tr style="height: 22px;"> <td style="width: 48.8885%; text-align: center; height: 22px;" width="208">13</td> <td style="width: 48.8885%; text-align: center; height: 22px;" width="208">204</td> </tr> <tr style="height: 22px;"> <td style="width: 48.8885%; text-align: center; height: 22px;" width="208">14</td> <td style="width: 48.8885%; text-align: center; height: 22px;" width="208">234</td> </tr> <tr style="height: 22px;"> <td style="width: 48.8885%; text-align: center; height: 22px;" width="208">15</td> <td style="width: 48.8885%; text-align: center; height: 22px;" width="208">266</td> </tr> <tr style="height: 22px;"> <td style="width: 48.8885%; text-align: center; height: 22px;" width="208">16</td> <td style="width: 48.8885%; text-align: center; height: 22px;" width="208">300</td> </tr> <tr style="height: 22px;"> <td style="width: 48.8885%; text-align: center; height: 22px;" width="208">17</td> <td style="width: 48.8885%; text-align: center; height: 22px;" width="208">336</td> </tr> <tr style="height: 22px;"> <td style="width: 48.8885%; text-align: center; height: 22px;" width="208">18</td> <td style="width: 48.8885%; text-align: center; height: 22px;" width="208">374</td> </tr> <tr style="height: 22px;"> <td style="width: 48.8885%; text-align: center; height: 22px;" width="208">19</td> <td style="width: 48.8885%; text-align: center; height: 22px;" width="208">414</td> </tr> <tr style="height: 22px;"> <td style="width: 48.8885%; text-align: center; height: 22px;" width="208">20</td> <td style="width: 48.8885%; height: 22px; text-align: center;" width="208">456</td> </tr> </tbody> </table> <p style="text-align: justify;">Như vậy, ta c&oacute; thể thấy rằng thời gian thực thi (số lần truy cập v&agrave;o mảng) của giải thuật tăng l&ecirc;n với số phần tử của mảng tăng. Giả sử giải thuật sắp xếp lựa chọn thực hiện tr&ecirc;n mười triệu phần tử cần khoảng 100 ngh&igrave;n tỷ lượt truy cập; nếu mỗi lần truy cập mất mười nano gi&acirc;y th&igrave; sẽ mất 1.000.000 gi&acirc;y hoặc khoảng 11 ng&agrave;y rưỡi để ho&agrave;n th&agrave;nh.</p> <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ề độ phức tạp t&iacute;nh to&aacute;n của một thuật to&aacute;n. Hy vọng mọi người c&oacute; thể nắm được kiến thức cơ bản của phần n&agrave;y. Nếu mọi người c&oacute; đ&oacute;ng g&oacute;p g&igrave; th&ecirc;m th&igrave; c&oacute; thể để c&aacute;c b&igrave;nh luận b&ecirc;n dưới b&agrave;i viết n&agrave;y. Mọi người h&atilde;y tiếp tục theo d&otilde;i c&aacute;c b&agrave;i tiếp theo v&agrave; cập nhật c&aacute;c b&agrave;i mới nhất tr&ecirc;n&nbsp;<a href="../../">tek4</a>&nbsp;nh&eacute;!</p>