---
# System prepended metadata

title: Độ phức tạp tính toán của thuật toán

---

Trong các cuộc thi lập trình, chương trình của bạn cần chạy xong trong một khung thời gian nhất định, với quy ước hiện nay mỗi giây máy tính có thể tính được $10^8$ phép tính. Vì vậy việc tối ưu phép tính trong việc giải các bài toán rất quan trọng trong lập trình thi đấu.

## Tính toán độ phức tạp thuật toán
Chúng ta cần biết thuật toán của mình sẽ cần bao nhiêu phép tính để chạy thuật toán. Xét kích thước đầu vào là n. Chúng ta biễu diễn độ phức tạp tính toán tương đối bằng hàm $\mathcal{O}(x)$ (với $x$ là một biểu thức). Ví dụ như $\mathcal{O}(n)$ là cần n phép tính để thực hiện bài toán. Nếu có nhiều đoạn mã rời nhau, thì độ phức tạp thời gian sẽ làm trường hợp xấu nhất trong các đoạn rời nhau đó.


Đoạn mã sau đây là $\mathcal{O}(1)$ vì các đoạn rời nhau này độ phức tạp xấu nhất là $\mathcal{O}(1)$ (một phép tính là $\mathcal{O}(1)$)

```python=
a = 5
b = 7 
c = 4 
d = a + b + c + 153
```

Việc nhập đầu vào và đầu ra cũng được giả định là $\mathcal{O}(1)$, trong các trường hợp sau chúng ta giả sử độ phức tạp tính toán phép tính ở trong là $\mathcal{O}(1)$.

Độ phức tạp thời gian của các vòng lặp là số lần lặp mà vòng lặp chạy. Ví dụ các đoạn mã sau đây đều là $\mathcal{O}(n)$ vì số lần lặp lại của $2$ vòng lặp là $n$ lần.

```python=
for i in range (n):  
	# tính toán trong một phép tính O(1)
```


``` python=
i = 0
while i < n:
	# tính toán trong một phép tính O(1)
	i += 1

```

Chúng ta có thể tìm độ phức tạp tính toán của nhiều vòng lặp bằng cách nhân các độ phức tạp tính toán của mỗi vòng lặp với nhau, trong ví dụ này độ phức tạp tính toán là $\mathcal{O}(n⋅m)$ bởi vì độ phức tạp tính toán của vòng lặp ngoài là $\mathcal{O}(n)$ và vòng lặp trong là $\mathcal{O}(m)$ vậy nên $\mathcal{O}(n)$⋅$\mathcal{O}(m)$ = $\mathcal{O}(n⋅m)$.

```python=
for i in range (n):   
	for j in range (m):  
		# tính toán trong một phép tính O(1)
	

```

Trong ví dụ này, độ phức tạp tính toán vòng lặp ngoài là $\mathcal{O}(n)$ và độ phức tạp tính toán vòng trong là chạy từ mọi vị trí từ 1 đến n cho đến n. Nhưng trong trường hợp xấu nhất là n lần lặp nên độ phức tạp tính toán sẽ là $\mathcal{O}(n)$. Như vậy với đoạn mã này độ phức tạp tính toán sẽ là $\mathcal{O}(n^2)$
```python=
for i in range (n):   
	for j in range (i,m):  
		# tính toán trong một phép tính O(1)
	

```

Nếu thuật toán có nhiều đoạn rời nhau thì độ phức tạp thời gian sẽ là trường hợp xấu nhất trong các đoạn.Trong trường hợp  này độ phức tạp sẽ là $\mathcal{O}(n^2)$ bởi vì ở đoạn trước có độ phức tạp là $\mathcal{O}(n^2)$ còn đoạn sau có độ phức tạp nhỏ hơn là $\mathcal{O}(n)$.

```python=
#đoạn rời thứ nhất
for i in range (n):   
	for j in range (n):  
		# tính toán trong một phép tính O(1)
#đoạn rời thứ hai
for i in range (n): 
       # tính toán trong một phép tính O(1)

```

## Độ phức tạp và Hạn chế chung

**Quy ước chung một số độ phức tạp thời gian:**

- Các công thức toán học chỉ các biến: $\mathcal{O}(1)$
- Đọc đầu vào mảng gồm $n$ phần tử:    $\mathcal{O}(n)$
- Duyệt qua một mảng gồm $n$ phần tử: $\mathcal{O}(n)$
- Các thuật toán tìm kiếm nhị phân: $\mathcal{O}(\log n)$
- ...

----
Bảng sau đây sẽ gợi ý cho chúng ta những độ phức tạp tính toán nên dùng dựa trên giới hạn của đề bài.
| n | độ phức tạp tính toán nên dùng |
|---| -- |
| n ≤ 10 | $\mathcal{O}(n^7)$,$\mathcal{O}(n^6)$,$\mathcal{O}(n!)$|
| n ≤ 20 | $\mathcal{O}(n^5)$,$\mathcal{O}(2^nn)$
| n ≤ 80 | $\mathcal{O}(n^4)$
| n ≤ 400| $\mathcal{O}(n^3)$
| n ≤ 7500| $\mathcal{O}(n^2)$
| n ≤ 7⋅10^4^ | $\mathcal{O}(n\sqrt n)$
| n ≤ 10^5^ |$\mathcal{O}(n⋅\log^2(n))$
| n ≤ 5⋅10^5^ | $\mathcal{O}(n⋅\log(n))$
| n ≤ 5⋅10^6^ | $\mathcal{O}(n)$
| n ≤ 10^18^ |  $\mathcal{O}(\log^2n)$, $\mathcal{O}(\log n)$, $\mathcal{O}(1)$

## Vận dụng
**Trong các trường hợp dưới đây chúng ta hãy cùng đánh giá độ phức tạp nhé:**

**Ví dụ: 1**
```python=
for i in range(n):
    for j in range(n):
        for z in range(n):
            k += i + j + z
    for j in range(n):
        k += i + j

print(k)
```
**Ví dụ: 2**
```python=
for i in range(n): k += 1
for i in range(n - 1, n):
    for j in range(n): k += 2
print(k)
```

**Ví dụ: 3**
```python=

for i in range(n):
    for j in range(n):
        for z in range(n):
            k += i + j + z
    for j in range(n):
        k += i + j

for i in range(n): 
    k += 1
    
for i in range(n - 1, n):
    for j in range(n): 
        k += 2
    
for i in range(n**4):
    k += i*i

print(t)
```