K&yacute; hiệu Big-O l&agrave; ng&ocirc;n ngữ ch&uacute;ng ta sử dụng để n&oacute;i về thời gian một thuật to&aacute;n thực thi (độ phức tạp về thời gian) hoặc dung lượng bộ nhớ được sử dụng bởi một thuật to&aacute;n (độ phức tạp về kh&ocirc;ng gian). K&yacute; hiệu Big-O c&oacute; thể thể hiện thời gian chạy tốt nhất, xấu nhất v&agrave; trung b&igrave;nh của một thuật to&aacute;n. Với mục đ&iacute;ch trong b&agrave;i viết n&agrave;y, ch&uacute;ng ta sẽ tập trung chủ yếu v&agrave;o độ phức tạp về thời gian.
K&yacute; hiệu Big-O được sử dụng để định lượng thời gian chạy sẽ tăng như thế n&agrave;o khi một thuật to&aacute;n thực thi dựa tr&ecirc;n k&iacute;ch thước đầu v&agrave;o của n&oacute;.
Để t&iacute;nh to&aacute;n Big-O, c&oacute; năm bước ch&uacute;ng ta c&oacute; thể l&agrave;m theo:
<ol style="text-align: justify;">
<li style="font-weight: 400;" aria-level="1">Chia thuật to&aacute;n th&agrave;nh c&aacute;c thao t&aacute;c ri&ecirc;ng lẻ</li>
<li style="font-weight: 400;" aria-level="1">T&iacute;nh to&aacute;n Big-O cho mỗi thao t&aacute;c</li>
<li style="font-weight: 400;" aria-level="1">Cộng Big-O của mỗi thao t&aacute;c với nhau</li>
<li style="font-weight: 400;" aria-level="1">Loại bỏ c&aacute;c gi&aacute; trị hằng số</li>
<li style="font-weight: 400;" aria-level="1">T&igrave;m hệ số lớn nhất</li>
</ol>
Với c&aacute;ch l&agrave;m như vậy, ch&uacute;ng ta h&atilde;y bắt đầu với một v&iacute; dụ đơn giản nh&eacute;.
V&iacute; dụ 1: Giả sử c&oacute; một h&agrave;m được định nghĩa trong C++ như sau.
<pre class="language-cpp"><code>int add (int* arr, int n) {
 int res = 0; // 1
 for (int i = 0; i &lt; n; i++) { // 2
 res += arr[i]; // 3
 }
 return res; // 4
}</code></pre>
Ch&uacute;ng ta muốn tạo một c&ocirc;ng thức để đếm độ phức tạp t&iacute;nh to&aacute;n của h&agrave;m được định nghĩa b&ecirc;n tr&ecirc;n:
<pre class="language-markup"><code>Số lượng c&aacute;c bước = f(N)</code></pre>
V&igrave; vậy, ch&uacute;ng ta c&oacute; f(N), một h&agrave;m để đếm số bước t&iacute;nh to&aacute;n. Đầu v&agrave;o của h&agrave;m l&agrave; k&iacute;ch thước của cấu tr&uacute;c cần xử l&yacute;. C&oacute; nghĩa l&agrave; h&agrave;m n&agrave;y được gọi như sau:
<pre class="language-markup"><code>Số lượng c&aacute;c bước = f(data.length)</code></pre>
Tham số N nhận gi&aacute; trị l&agrave; data.length (độ d&agrave;i của tập dữ liệu). B&acirc;y giờ ch&uacute;ng ta cần định nghĩa thực tế của h&agrave;m f(). Điều n&agrave;y được thực hiện từ m&atilde; nguồn, trong đ&oacute; mỗi d&ograve;ng được đ&aacute;nh số từ 1 đến 4.
C&oacute; nhiều c&aacute;ch để t&iacute;nh Big-O. Ch&uacute;ng ta sẽ giả định rằng mọi c&acirc;u lệnh m&agrave; kh&ocirc;ng phụ thuộc v&agrave;o k&iacute;ch thước của dữ liệu đầu v&agrave;o sẽ thực hiện c&aacute;c bước t&iacute;nh to&aacute;n C kh&ocirc;ng đổi.
Ch&uacute;ng ta sẽ th&ecirc;m số bước ri&ecirc;ng lẻ của h&agrave;m v&agrave; cả khai b&aacute;o biến cục bộ cũng như c&acirc;u lệnh trả về đều kh&ocirc;ng phụ thuộc v&agrave;o k&iacute;ch thước của mảng dữ liệu.
Điều đ&oacute; c&oacute; nghĩa l&agrave; d&ograve;ng 1 v&agrave; 4 c&oacute; gi&aacute; trị hằng số C như sau:
<pre class="language-markup"><code>f(N) = C + ? + C</code></pre>
Phần tiếp theo l&agrave; x&aacute;c định gi&aacute; trị của c&acirc;u lệnh for. H&atilde;y nhớ rằng ch&uacute;ng ta đang đếm số bước t&iacute;nh to&aacute;n, nghĩa l&agrave; phần th&acirc;n của c&acirc;u lệnh for được thực thi N lần. Điều đ&oacute; cũng giống như việc th&ecirc;m gi&aacute; trị hằng số C N lần:
<pre class="language-markup"><code>f(N) = C + (C + C + ... + C) + C = C + N * C + C</code></pre>
Kh&ocirc;ng c&oacute; quy tắc cơ học n&agrave;o để đếm số lần phần th&acirc;n của for được thực thi, bạn cần đếm n&oacute; bằng c&aacute;ch xem đoạn m&atilde; l&agrave;m những g&igrave;. Để đơn giản h&oacute;a c&aacute;c ph&eacute;p t&iacute;nh to&aacute;n, ch&uacute;ng ta bỏ qua phần khởi tạo biến, điều kiện v&agrave; phần tăng th&ecirc;m của c&acirc;u lệnh for.
Để c&oacute; được Big-O, ch&uacute;ng ta cần ph&acirc;n t&iacute;ch tiệm cận của h&agrave;m. Điều n&agrave;y được thực hiện như sau:
<ul style="text-align: justify;">
<li style="font-weight: 400;" aria-level="1">Bỏ đi tất cả c&aacute;c hằng số C.</li>
<li style="font-weight: 400;" aria-level="1">Từ f (), nhận được đa thức ở dạng chuẩn của n&oacute;.</li>
<li style="font-weight: 400;" aria-level="1">Chia c&aacute;c hệ số của đa thức v&agrave; sắp xếp ch&uacute;ng theo mức độ lớn dần.</li>
<li style="font-weight: 400;" aria-level="1">Giữ lại hệ số lớn dần l&ecirc;n khi N tiến đến v&ocirc; c&ugrave;ng.</li>
</ul>
F() của ch&uacute;ng ta c&oacute; hai hệ số:
<pre class="language-markup"><code>f(N) = 2 * C + C * N</code></pre>
Loại bỏ tất cả c&aacute;c hằng số:
<pre class="language-markup"><code>f(N) = N</code></pre>
V&igrave; hệ số N cuối c&ugrave;ng l&agrave; hệ số sẽ gia tăng v&agrave; f() sẽ tiến đến v&ocirc; c&ugrave;ng, như vậy, h&agrave;m sum() được định nghĩa b&ecirc;n tr&ecirc;n c&oacute; độ phức tạp Big-O l&agrave;: O(n)
V&iacute; dụ 2: Giả sử c&oacute; một h&agrave;m C++ như sau.
<pre class="language-cpp"><code>int add(int num1, int num2) {
 int total = num1 + num2;
 return total;
};</code></pre>
Ch&uacute;ng ta h&atilde;y thực hiện chia nhỏ h&agrave;m b&ecirc;n tr&ecirc;n n&agrave;y để đ&aacute;nh gi&aacute; từng thao t&aacute;c.
V&iacute; dụ b&ecirc;n tr&ecirc;n bao gồm 4 thao t&aacute;c kh&aacute;c nhau như sau:
<ol style="text-align: justify;">
<li style="font-weight: 400;" aria-level="1">Nhận v&agrave;o biến num1</li>
<li style="font-weight: 400;" aria-level="1">Nhận v&agrave;o biến num2</li>
<li style="font-weight: 400;" aria-level="1">T&iacute;nh tổng gi&aacute; trị của 2 biến v&agrave; g&aacute;n cho biến total</li>
<li style="font-weight: 400;" aria-level="1">Trả về gi&aacute; trị của biến total</li>
</ol>
B&acirc;y giờ ch&uacute;ng ta đ&atilde; x&aacute;c định c&aacute;c thao t&aacute;c trong h&agrave;m b&ecirc;n tr&ecirc;n, ch&uacute;ng ta sẽ t&iacute;nh to&aacute;n Big-O cho mỗi thao t&aacute;c. Trong v&iacute; dụ b&ecirc;n tr&ecirc;n n&agrave;y, ch&uacute;ng ta xử l&yacute; c&aacute;c ph&eacute;p to&aacute;n kh&aacute; đơn giản, mỗi ph&eacute;p to&aacute;n c&oacute; độ phức tạp về thời gian l&agrave; O(1).
Độ phức tạp thời gian l&agrave; O(1) hoặc thời gian kh&ocirc;ng đổi v&igrave; c&aacute;c thao t&aacute;c chỉ xảy ra một lần v&agrave; ch&uacute;ng kh&ocirc;ng phụ thuộc v&agrave;o k&iacute;ch thước của dữ liệu đầu v&agrave;o khi chương tr&igrave;nh thực thi. Một c&aacute;ch kh&aacute;c để nghĩ về điều n&agrave;y l&agrave; c&aacute;c thao t&aacute;c n&agrave;y sẽ mất c&ugrave;ng một khoảng thời gian để thực thi, bất kể đầu v&agrave;o l&agrave; g&igrave;. Việc thực thi h&agrave;m add(1,2) sẽ mất c&ugrave;ng khoảng thời gian với việc thực thi h&agrave;m add(10436,4783474).
Chuyển sang bước tiếp theo, ch&uacute;ng ta sẽ cộng tất cả lại với nhau.
V&igrave; mỗi thao t&aacute;c c&oacute; thời gian chạy l&agrave; O(1), n&ecirc;n Big-O của thuật to&aacute;n l&agrave; O(1 + 1 + 1 + 1) = O(4), sau đ&oacute;, ch&uacute;ng ta sẽ đơn giản h&oacute;a th&agrave;nh O(1) khi ch&uacute;ng ta t&aacute;ch bỏ c&aacute;c gi&aacute; trị hằng số v&agrave; x&aacute;c định hệ số cao nhất, trong trường hợp n&agrave;y l&agrave; 1.
C&aacute;c bạn h&atilde;y nhớ rằng, cuối c&ugrave;ng, tất cả những g&igrave; ch&uacute;ng ta quan t&acirc;m l&agrave; c&oacute; được hệ số cao nhất của Big-O về c&aacute;ch m&agrave; một thuật to&aacute;n sẽ hoạt động trong trường hợp xấu nhất. Do đ&oacute;, ch&uacute;ng ta đơn giản h&oacute;a k&yacute; hiệu Big-O hết mức c&oacute; thể để đạt được mục ti&ecirc;u đ&oacute;.
<h2 style="text-align: justify;"> 2. Một số h&agrave;m Big-O v&agrave; c&aacute;ch x&aacute;c định</h2>
<h3 style="text-align: justify;"> Thời gian kh&ocirc;ng đổi: O(1)</h3>
Như ch&uacute;ng ta đ&atilde; thảo luận trước đ&oacute;, c&aacute;c thuật to&aacute;n hoặc c&aacute;c thao t&aacute;c được coi l&agrave; c&oacute; độ phức tạp về thời gian kh&ocirc;ng đổi khi ch&uacute;ng kh&ocirc;ng phụ thuộc v&agrave;o k&iacute;ch thước của dữ liệu đầu v&agrave;o v&agrave; thời gian cần thiết để thực thi l&agrave; như nhau.
Ph&eacute;p cộng, ph&eacute;p trừ, ph&eacute;p g&aacute;n v&agrave; hầu hết c&aacute;c dạng thao t&aacute;c cơ bản đều được coi l&agrave; thực thi với thời gian kh&ocirc;ng đổi, v&igrave; vậy khi bạn nh&igrave;n thấy c&aacute;c thao t&aacute;c n&agrave;y, h&atilde;y ghi nhớ nhanh rằng ch&uacute;ng c&oacute; độ phức tạp l&agrave; O(1).
<h3 style="text-align: justify;"> Thời gian tuyến t&iacute;nh: O(n)</h3>
C&aacute;c thuật to&aacute;n hoặc thao t&aacute;c c&oacute; độ phức tạp theo thời gian tuyến t&iacute;nh c&oacute; thể được x&aacute;c định bởi thực tế l&agrave; số lượng thao t&aacute;c tăng l&ecirc;n tuyến t&iacute;nh với k&iacute;ch thước của đầu v&agrave;o.
Điều đ&oacute; c&oacute; nghĩa l&agrave; nếu một thao t&aacute;c phải thực thi 100 lần cho một tập hợp d&agrave;i 100 phần tử, n&oacute; c&oacute; độ phức tạp theo thời gian tuyến t&iacute;nh.
V&ograve;ng lặp for l&agrave; một v&iacute; dụ tuyệt vời về một thao t&aacute;c c&oacute; độ phức tạp thời gian tuyến t&iacute;nh.
<pre class="language-cpp"><code>for (int i = 0; i &lt; examArray.length; i++) {
 printf(&lsquo;%d time`, i);
}</code></pre>
Trong v&iacute; dụ tr&ecirc;n, nếu examArray chỉ c&oacute; 1 phần tử, thuật to&aacute;n của ch&uacute;ng ta sẽ chạy kh&aacute; nhanh. Nhưng điều g&igrave; sẽ xảy ra nếu mảng đ&oacute; được tăng k&iacute;ch thước l&ecirc;n l&agrave; 500 phần tử th&igrave; sao? Sẽ mất nhiều thời gian hơn để thuật to&aacute;n n&agrave;y thực thi. Do đ&oacute;, ch&uacute;ng ta x&aacute;c định thuật to&aacute;n n&agrave;y c&oacute; độ phức tạp theo thời gian tuyến t&iacute;nh để chỉ ra rằng khi k&iacute;ch thước của đầu v&agrave;o tăng l&ecirc;n, lượng thời gian cần thiết để thực thi cũng tăng theo.
<h3 style="text-align: justify;"> Thời gian theo số mũ bậc 2: O(n&sup2;)</h3>
C&aacute;c thuật to&aacute;n hoặc thao t&aacute;c c&oacute; thời gian bậc hai được x&aacute;c định l&agrave; phải thực hiện theo thời gian tuyến t&iacute;nh cho mỗi gi&aacute; trị trong một đầu v&agrave;o, kh&ocirc;ng chỉ cho ch&iacute;nh đầu v&agrave;o đ&oacute;.
C&aacute;c v&ograve;ng lặp lồng nhau l&agrave; một v&iacute; dụ đơn giản về kh&aacute;i niệm n&agrave;y:
<pre class="language-cpp"><code>for (int i = 0; i &lt; examArray.length; i++) {
 for (int y = 0; y &lt; examArray2.length; y++) {
 printf(`Hello!`);
 }
}</code></pre>
Như bạn c&oacute; thể thấy, thời gian chạy của thuật to&aacute;n sẽ tăng gấp đ&ocirc;i v&igrave; ch&uacute;ng ta phải tham chiếu từng phần tử trong đầu v&agrave;o hai lần. Một v&ograve;ng lặp c&oacute; độ phức tạp Big-O l&agrave; O(n), do đ&oacute;, 2 v&ograve;ng lặp thực thi sẽ c&oacute; độ phức tạp l&agrave; O(nxn) v&agrave; bằng O(n^2). T&iacute;nh logic tương tự tiếp tục được &aacute;p dụng nếu bạn tiếp tục lồng nhiều v&ograve;ng lặp hơn.
<h3 style="text-align: justify;"> Thời gian theo logarit: O(log n)</h3>
O(log n) c&oacute; nghĩa l&agrave; thời gian chạy tăng tương ứng với logarit của k&iacute;ch thước đầu v&agrave;o, c&oacute; nghĩa l&agrave; thời gian chạy hầu như kh&ocirc;ng tăng khi tăng đầu v&agrave;o theo cấp số nh&acirc;n.
Lưu &yacute;: O(n log n), thường bị nhầm lẫn với O(log n), c&oacute; nghĩa l&agrave; thời gian chạy của một thuật to&aacute;n l&agrave; tuyến t&iacute;nh, l&agrave; sự kết hợp của độ phức tạp tuyến t&iacute;nh v&agrave; logarit. C&aacute;c thuật to&aacute;n sắp xếp sử dụng chiến lược chia để trị c&oacute; t&iacute;nh tuyến t&iacute;nh v&agrave; logarit, v&iacute; dụ như:
<ol>
<li style="text-align: justify;">Thuật to&aacute;n hợp nhất</li>
<li style="text-align: justify;">Thuật to&aacute;n sắp xếp vun đống</li>
</ol>

Admin

Ký hiệu Big O là gì?

Cùng tác giả

Admin

Có liên quan