---
title
Độ phức tạp thời gian và bộ nhớ (Time complexity and memory)
---

Độ phức tạp thời gian và bộ nhớ (Time complexity and memory)
===

---

###### ✍️ Author: 2School Guideline
###### 📋 Content:
[TOC]

---

# Giới thiệu chung
- Trong tin học, chương trình của chúng ta khi thực thi thì cần tốn một khoảng thời gian và dung lượng bộ nhớ nhất định.
- Trong lập trình thi đấu, mỗi một bài toán sẽ có một **giới hạn thời gian (time limit)** và **giới hạn bộ nhớ (memory limit)** nhất định, nếu chương trình của bạn cho ra được kết quả đúng của bài toán nhưng lại vượt quá giới hạn thời gian hoặc bộ nhớ cho phép **(time/memory limit exceeded)** khi thực thi thì vẫn sẽ **không được tính điểm**. Vì vậy, khi giải một bài toán thì chúng ta luôn cố gắng tìm ra cách giải **đủ tối ưu** - chương trình thực thi trong khoảng thời gian nhỏ hơn giới hạn thời gian và chiếm dụng ít bộ nhớ hơn giới hạn bộ nhớ.
- Vậy làm thế nào để đánh giá hay tính toán/ước lượng một cách nhanh chóng và chính xác thời gian thực thi và dung lượng bộ nhớ chiếm dụng của một chương trình? Câu trả lời sẽ có trong bài viết hôm nay.

## Note: Một số kiến thức toán học
- Logarit: $\log_a{b} = n \Leftrightarrow a^n = b$. Ví dụ: $\log_2{32} = 5 \Leftrightarrow 2^5 = 32$
- Giai thừa: $n! = 1 \cdot 2 \cdot 3 \cdot ... \cdot n$
- Luỹ thừa với số mũ là phân số: $a^\frac{n}{m} = \sqrt[m]{a^n}$. Ví dụ: $n^\frac{1}{2} = \sqrt[2]{n^1} = \sqrt{n}$

# Bộ nhớ (Memory)
## 1. Các đơn vị đo dung lượng bộ nhớ thường gặp
Trong các đơn vị đo lường dung lượng bộ nhớ máy tính, đây là các đơn vị thường gặp trong lập trình thi đấu:

| Tên gọi | Kí hiệu | Kích thước |
| - | - | - |
| bit | b hoặc bit | đơn vị nhỏ nhất |
| byte | B hoặc byte | 1 byte = 8 bits |
| kilobyte | kB | $1$ kB $=$ $2^{10}$ bytes $=$ $1024$ bytes |
| megabyte | MB | $1$ MB $=$ $2^{20}$ bytes $=$ $1048576$ bytes |
| gigabyte | GB | $1$ GB $=$ $2^{30}$ bytes $=$ $1073741824$ bytes|

## 2. Dung lượng bộ nhớ chiếm dụng của các kiểu dữ liệu cơ bản trong C++
Mỗi một biến trong chương trình sẽ chiếm một dung lượng bộ nhớ nhất định, tuỳ thuộc vào kiểu dữ liệu của nó:

| Kiểu dữ liệu | Kích thước |
| - | - |
| bool | 1 byte |
| char | 1 byte |
| int | 4 bytes |
| long long | 8 bytes |
| float | 4 bytes |
| double | 8 bytes |
| long double | 12 bytes |

## 3. Cách tính toán dung lượng bộ nhớ chiếm dụng khi thực thi của chương trình
Với các kiến thức ở trên, ta có thể tính toán được dung lượng bộ nhớ mà chương trình sẽ chiếm dụng khi thực thi theo các quy tắc sau:
1. Đối với mảng **(array)**, ta lấy dung lượng bộ nhớ chiếm dụng của kiểu dữ liệu của mảng đó nhân cho kích thước của mảng đó.
**Ví dụ:** `int arr[50005]` thì sẽ chiếm dụng $4 * 50005 = 200020$ bytes $\approx 195.33$ kB bộ nhớ.
2. Đối với mảng động **(vector)**, ta lấy dung lượng bộ nhớ chiếm dụng của kiểu dữ liệu của mảng động đó hay của nhân cho kích thước tối đa của mảng động đó theo đề bài.
**Ví dụ:** Đề bài cho một dãy số có độ dài tối đa $10^5$ phần tử thì `vector <int> vec` sẽ chiếm dụng xấp xỉ $4 * 10^5 = 400000$ bytes $= 390.625$ kB bộ nhớ.
3. Đối với chuỗi kí tự **(string)**, ta lấy dung lượng bộ nhớ chiếm dụng của kiểu dữ liệu char nhân cho kích thước tối đa của chuỗi kí tự đó theo đề bài.
**Ví dụ:** Đề bài cho một chuỗi kí tự có độ dài tối đa $10^5$ kí tự thì `string str` sẽ chiếm dụng xấp xỉ $1 * 10^5 = 100000$ bytes $= 97,6525$ kB bộ nhớ.
4. Đối với các cấu trúc dữ liệu có sẵn trong các thư viện của C++ thì vì chúng được xây dựng dựa trên những cơ chế phức tạp hơn nên thực sự là khá khó để tính toán chính xác dung lượng bộ nhớ chiếm dụng của chúng.
Tuy nhiên ta biết rằng chúng sẽ chiếm một lượng bộ nhớ ít nhất là bằng với một mảng thường nên ta chỉ cần đảm bảo luôn chừa ra một lượng bộ nhớ nhất định để không bị tràn hoặc vượt quá giới hạn bộ nhớ.
5. **Mỗi lần ta khai báo** biến là chương trình của ta đã **chiếm dụng thêm** lượng bộ nhớ tương ứng, chính vì vậy nên hãy cẩn thận khi khai báo các biến cục bộ trong các hàm hay khai báo các biến trong tham số trong các hàm, vòng lặp (đặc biệt là khai báo các mảng).
6. Một số nguyên nhân thường gặp dẫn đến lỗi **vượt quá giới hạn bộ nhớ (memory limit exceeded)** khi nộp bài:
- Vòng lặp vô hạn.
- Khai báo các mảng trong các vòng lặp hay trong tham số của các hàm đệ quy.
7. Một số nguyên nhân thường gặp dẫn đến **lỗi phân đoạn (segmentation fault)** khi nộp bài:
- Tràn bộ nhớ **(stack overflow)**. Ví dụ: Khi ta khai báo mảng với số lượng $10^8$ phần tử hoặc gọi hàm đệ quy quá nhiều lần sẽ dẫn đến lỗi này.
- Truy cập vào vị trí lớn hơn số lượng phần tử của mảng. Ví dụ: Khai báo mảng `int a[10]` nhưng lại truy cập vào `a[11]`.
9. Các bài toán trong lập trình thi đấu thường có giới hạn bộ nhớ là **$256$ MB** hoặc **$512$ MB** nên thường thì trừ khi bạn gặp phải các trường hợp nêu trên (**6.** và **7.**), chương trình của bạn sẽ khá là khó bị dính lỗi về mặt bộ nhớ hoặc vượt quá giới hạn bộ nhớ khi nộp bài.

# Độ phức tạp thời gian (Time complexity)
## 1. Bài toán ví dụ
### 1.1. Đề bài
Cho $1$ số $n$. Tính $S = 1 + 2 + ... + n$. Giới hạn: $n \le 10^{9}$.

### 1.2. Cách giải 1
Một cách ngây thơ khi giải bài này là chúng ta sẽ sử dụng 1 vòng lặp `for` để duyệt từ $1$ đến $n$ và tính tổng $S$.

long long calc(int n)
{
    long long S = 0;
    for (int i = 1; i <= n; i++) S += i;
    return S;
}

### 1.3. Cách giải 2
Ta sẽ biến đổi biểu thức trên về dạng sau:
$S = 1 + 2 + ...+ (n - 1) + n$
$\Leftrightarrow S = n + (n - 1) + ... + 1$
$\Leftrightarrow 2S = (1 + n) + (2 + n - 1) + ... + (n + 1)$
$\Leftrightarrow 2S = (n + 1) + (n + 1) + ... + (n + 1)$ ($n$ lần)
$\Leftrightarrow 2S = n \cdot (n+1)$
$\Leftrightarrow S = \frac{n \cdot (n+1)}{2}$
Chúng ta sẽ từ công thức này để tính ra kết quả mà không cần phải duyệt qua `for` như **cách giải 1**.

long long calc(long long n)
{
    long long S = n * (n + 1) / 2;
    return S; 
}

### 1.4. Đo và so sánh thời gian chạy của chương trình
Bảng dưới đây là kết quả đo và so sánh thời gian chạy 2 chương trình trên (chỉ mang tính chất tham khảo):

| $n$ | Cách giải 1 | Cách giải 2 |
| -------- | -------- | -------- |
| $100$ | $0.00s$ | $0.00s$ |
| $10000$ | $0.00s$ | $0.00s$ |
| $10000000$ | $0.03s$ | $0.00s$ |
| $100000000$ | $0.28s$ | $0.00s$ |
| $1000000000$ | $2.67s$ | $0.00s$ |

Dựa vào bảng trên ta thấy được rằng **cách giải 2** hiệu quả hơn (thực thi nhanh hơn) **cách giải 1**.

:::success
Sau khi đọc xong bài viết, bạn hãy thử trả lời xem tại sao **cách giải 2** lại thực thi nhanh hơn **cách giải 1**?

:::spoiler Câu trả lời
Độ phức tạp thời gian của **cách giải 2** là $O(1)$ trong khi độ phức tạp thời gian của **cách giải 1** là $O(n)$.
:::

## 2. Cách tính độ phức tạp thời gian
Ta có thể tính được độ phức tạp thời gian bằng cách tính **số lượng phép tính** được thực hiện bởi chương trình. Chương trình thực hiện càng nhiều phép tính thì thời gian chương trình thực thi càng lớn - độ phức tạp thời gian càng cao.

**Ví dụ 1:** Tính số phép tính được thực hiện của chương trình sau:

for (int i = 1; i <= n; i++)
{
    int t = 2*i;
    cout << t << '\n';
}

:::spoiler Lời giải
`int i = 1`: $1$ phép tính
`i <= n`: $n$ phép tính (vòng lặp chạy $n$ lần)
`i++`: $n$ phép tính
`int t = 2*i`: $2 \cdot n$ phép tính (`2*i` -- $n$ phép tính và `int t = ` -- $n$ phép tính)
`cout << t << '\n'`: $2 \cdot n$ phép tính (`cout << t` $n$ phép tính và `cout << '\n'` $n$ phép tính)
**Tổng:** $1 + n + n + 2 \cdot n + 2 \cdot n = 6 \cdot n + 1$ phép tính
:::

Tuy nhiên, các phép tính này thường rất khó để tính toán một cách chính xác nên chúng ta cần một phương pháp tính toán hiệu quả và dễ dàng hơn. Một cách được sử dụng phổ biến hiện nay đó là **BigO notation**.

## 3. BigO notation
### 3.1. Định nghĩa
Gọi $f(n)$ là số lượng phép tính của một chương trình có đầu vào là $n$. Khi đó, $g(n)$ được gọi là $O$ của $f(n)$ ($f(n) = O(g(n)) = O(n)$) nếu tồn tại một hằng số $C$ ($> 0$, không phụ thuộc vào $n$) và $n_0$ sao cho với mọi $n > n_0$, ta luôn có $f(n) \le C \cdot g(n)$.
**Ví dụ 2:** Ta xét lại số phép tính ở **Ví dụ 1** là $f(n) = 6n + 1$, $g(n) = n$ thì tồn tại một hằng số $C$ và $n_0$ sao cho điều kiện trên thoả (lấy $C = 7, n_0 = 1$)


Vậy chúng ta nói rằng, chương trình ở **Ví dụ 1** có độ phức tạp là $O(n)$

### 3.2. Các quy tắc tính độ phức tạp BigO
1. $O(1), O(2), O(3),... = O(1)$
2. $O(n), O(2n), O(3n),... = O(n)$
3. $O(n + 100), O(n + 1000),... = O(n)$
4. $O(\log_2(n)), O(\log_3(n)),... = O(\log(n))$
5. $O(n^{k_1} + n^{k_2} + ...) = O(n^{max(k_1, k_2,...)})$
6. $O(k^{n_1} + k^{n_2} + ...) = O(k^{max(n_1, n_2,...)})$
7. $O(f_1) + O(f_2) = O(f_1 + f_2)$
8. $O(f_1) \cdot O(f_2) = O(f_1 \cdot f_2)$
9. Các lệnh đơn (gán, đọc, xuất, phép tính số học, bit, hỗn hợp,...): có độ phức tạp $O(1)$.
10. Lệnh rẽ nhánh `if condition then f1 else f2`: có độ phức tạp $O(max(f_1, f_2))$.
11. Khối lệnh lặp `for i:=start to end do f`, `while condition do f`: có độ phức tạp $O(E \cdot f)$ với $E$ là số lần lặp của các khối lệnh lặp.

## 4. Một số độ phức tạp thời gian thường gặp
Giới hạn thời gian của các bài toán trong lập trình thi đấu thường là $1$s (tuy nhiên các bài toán phức tạp và nâng cao hơn thì có thể có giới hạn thời gian cao hơn như $2$s, $3$s,...).

Số lượng phép tính một chương trình C++ có thể thực hiện trong $1$s có thể lên đến $10^{8}$.

Dưới đây là bảng các độ phức tạp thời gian thường gặp cũng như kích thước $n$ tham khảo tương ứng (với giới hạn thời gian là $1$s):

| Độ phức tạp thời gian | Tên gọi | Kích thước $n$ tham khảo tương ứng |
| - | - | - |
| $O(1)$ | Hằng số (constant) | Tuỳ yêu cầu bài toán |
| $O(\sqrt{n})$ | | $10^{14}$ |
| $O(n)$ | Tuyến tính (linear) | $10^8$ |
| $O(n\log{n})$ | Linearithmic | $10^6$ |
| $O(n\sqrt{n})$ | | $10^5$ |
| $O(n^2)$ | Bậc 2 (Quadratic) | $5000$ |
| $O(n^3)$ | Bậc 3 (Cubic) | $500$ |
| $O(n^4)$ | Bậc 4 (Quartic) | $100$ |
| $O(2^n)$ | Exponential | $20$ |
| $O(n!)$ | Giai thừa (factorial) | $11$ |


Tuy nhiên, việc có bộ dữ liệu đáp ứng với độ phức tạp như trên thì chưa chắc chạy đủ nhanh trong giới hạn thời gian. Nó còn tuỳ thuộc vào [độ phức tạp của hằng số tự do](#6-Mở-rộng-Hằng-số-tự-do).

## 5. Độ phức tạp thời gian của một số thuật toán cơ bản
Dựa vào các quy tắc trên, ta rút ra được một vài tính chất như sau:

1. Tính số lần lặp tối đa của 1 vòng lặp
2. Nếu có nhiều vòng lặp nối tiếp nhau thì cộng các cận đó với nhau
3. Nếu có nhiều vòng lặp lồng nhau thì nhân các cận đó với nhau.

### Ví dụ 1

for (int i = 1; i <= n; i++)
    cout << i << '\n';
for (int j = 1; j <= n; j++)
    cout << j << '\n';

2 vòng trên có tổng cộng $2 \cdot n$ lệnh xuất nên có độ phức tạp là $O(n)$.

### Ví dụ 2

for (int i = 1; i <= n; i++)
{
    for (int j = 1; j <= n; j++)
        cout << i + j << " ";
    cout << '\n';
}

2 vòng lặp trên lồng nhau. Với mỗi biến $i$, vòng lặp $j$ có độ phức tạp $O(n)$ vậy nên tổng độ phức tạp sẽ là $O(n^2)$.
### Ví dụ 3

int cnt = 0;
for (int i = 1; i <= n; i++)
    for (int j = i; j <= n; j += i) cnt++;

Với đoạn code trên, chúng ta hãy thử tính toán độ phức tạp thuật toán của nó.

- Với mỗi biến $i$, vòng lặp $j$ bên trong sẽ chạy lần lượt như sau: $i, 2 \cdot i, 3 \cdot i,...,\lfloor \frac{n}{i} \rfloor \cdot i$. Vậy vòng lặp $j$ sẽ chạy $\lfloor \frac{n}{i} \rfloor$ lần. Vì thế độ phức tạp sẽ là $O(n \cdot (\frac{1}{1} + \frac{1}{2} + ... + \frac{1}{n})) = O(n \log{n})$ [(Chứng minh)](https://math.stackexchange.com/questions/3367037/sum-of-1-1-2-1-3-1-n)

### Ví dụ 4
Đoạn code dưới dùng thuật toán **tìm kiếm nhị phân** để tìm $target$ trong mảng $a$ và trả về vị trí của nó trong mảng. Nếu không có thì trả về $-1$.

int bsearch(int a[], int n, int target)
{
    int l = 1, r = n;
    while (l <= r)
    {
        int m = (l + r) / 2;
        if (a[m] == target) return m;
        if (a[m] < target) l = m + 1;
        else r = m - 1;
    }
    return -1;
}

Gọi $n$ là độ dài mảng.
Ở mỗi bước, phạm vi tìm kiếm $[l, r]$ sẽ giảm đi một nửa. Sau $\lceil \log_2{n} \rceil$ bước, thì phạm vi tìm kiếm $= 1$ và dừng tìm kiếm. Từ đó, độ phức tạp của thuật toán là $O(\log{n})$.

### Ví dụ 5
Đoạn code dưới sử dụng đệ quy để tính số fibonacci thứ $n$.

int fibo(int n)
{
    if (n == 1 || n == 2) return 1;
    return fibo(n - 1) + fibo(n - 2);
}

Ví dụ với $n = 5$, hãy xem hình sau đây để hình dung về cách hoạt động của hàm đệ quy trên.


Ta thấy rằng ở mỗi hàm $f(i)$ ta lại gọi tới 2 hàm $f(i - 1)$ và $f(i - 2)$. Vậy nên độ phức tạp sẽ là $O(2^n)$.

## 6. Mở rộng: Hằng số tự do
Với hầu hết các thuật toán thường thấy trong thực tế, thường có giá trị hằng số của $O$ khá nhỏ. Nếu một thuật toán có độ phức tạp $O(n^2)$, độ phức tạp chính xác là $10n^2$ chứ không phải $1000n^2$. Nói cách khác, nếu hằng số quá lớn thì thường các hằng số đó liên quan tới các đại lượng có sẵn trong bài. Khi đó, ta cần phải gán một tên gọi cho hằng số đó và thêm vào độ phức tạp, thay vì bỏ qua.
- **Ví dụ:** Thay vì để $O(1000n^2)$, ta có thể gán $C = 1000$ và để là $O(C \cdot n^2)$.
- Xét [các quy tắc trên](#32-Các-quy-tắc-tính-độ-phức-tạp-BigO), $O(10^9)$ thì vẫn là $O(1)$. Thế nhưng điều này chỉ đúng với $n$ cực lớn $(\infty)$
- Trong lập trình thi đấu, với bộ dữ liệu $n \le 10^8$, nên rõ ràng $O(10^9)$ sẽ chạy lâu hơn $O(n)$. Vì thế, ta đặt $C = 10^9$ và kết luận độ phức tạp thuật toán là $O(C)$ là hoàn toàn phù hợp.
- Hai thuật toán có độ phức tạp ngang nhau không đồng nghĩa với việc chúng chạy nhanh như nhau.
- Ví dụ khi ta xét 2 thuật toán cùng có độ phức tạp $O(n\log{n})$ thế nhưng độ phức tạp thuật toán chính xác của thuật toán 1 lại vào khoảng $20 \cdot n\log{n}$, còn thuật toán 2 lại chỉ rơi vào khoảng $2 \cdot n\log{n}$ thì khi đó thuật toán 2 vẫn sẽ chạy nhanh hơn khá nhiều so với thuật toán 1.
- Thuật toán có độ phức tạp bậc cao hơn không đồng nghĩa với việc chúng chạy chậm hơn trong mọi bộ dữ liệu.
- Ví dụ điển hình là hàm `std::sort` trong thư viện `<algorithm>`. Thuật toán chủ yếu là `Quick sort` - $O(n\log{n})$. Và để tối ưu, thì với bộ dữ liệu nhỏ, hàm sẽ sử dụng thuật toán `Insertion sort` - $O(n^2)$. Còn khi chọn phần tử chốt không đẹp, hàm chọn thuật toán `Merge sort` - $O(n\log{n})$
- Vì thế trong từng trường hợp, chúng ta nên chọn thuật toán phù hợp nhất để tối ưu thời gian chạy chương trình. Đối với các thư viện có sẵn, chúng ta nên nắm bắt cách hoạt động cơ bản và tốc độ của các hàm có sẵn đó.

# Nguồn tham khảo
:::info
[[1] https://vnoi.info/wiki/algo/basic/computational-complexity.md](https://vnoi.info/wiki/algo/basic/computational-complexity.md)
[[2] https://usaco.guide/bronze/time-comp?lang=cpp](https://usaco.guide/bronze/time-comp?lang=cpp)
[[3] https://howkteam.vn/course/cau-truc-du-lieu-va-giai-thuat/do-phuc-tap-thoi-gian-bigo-la-gi-4270](https://howkteam.vn/course/cau-truc-du-lieu-va-giai-thuat/do-phuc-tap-thoi-gian-bigo-la-gi-4270)
[[4] https://www.youtube.com/watch?v=2JO7IWOilrk](https://www.youtube.com/watch?v=2JO7IWOilrk)
[[5] https://en.wikipedia.org/wiki/Units_of_information](https://en.wikipedia.org/wiki/Units_of_information)
:::