---
title: 'Giới thiệu độ phức tạp của thuật toán Big O'
date: '2021-05-04'
lastmod: '2021-05-04'
tags: ['dsa']
summary: 'Giới thiệu về độ phức tạp của thuật toán Big O'
images: ['/static/blog/bigO/fig-1.png']
authors: ['hoangndst']
---

### 1. Giới thiệu
Tại sao phải tối ưu hóa độ phức tạp của thuật toán?
<div style={{ textAlign: "center" }}>
    <img
        id="figure-1"
        src="/static/blog/bigO/fig-1.png"
        alt="Big O"
        style={{ width: "100%", display: "block", margin: "0 auto" }}
    />
    <p style={{ textAlign: "center" }}>Figure 1: Big O</p>
</div>

Đơn giản vì độ phức tạp thấp thì sản phẩm của bạn sẽ chạy mượt mà hơn.

Độ phức tạp của thuật toán phụ thuộc vào mối quan hệ giữa số lượng phép tính cần thực hiện và số lượng đầu vào của hàm số.

### 2. Ví dụ
<div id="time-complexity">
```python:bigO.py caption="bigO.py" showLineNumbers
import time
start = time.time()
i = 0
n = 1000000

while i < n:
    print(i)
    i += 1

print("time: " +  str(time.time() - start))
```
</div>

Đối với đoạn code trên thì $P(n)=3n+2 \sim O(n)$

Tại sao lại tính được như vậy?

<div id="time-complexity-explain">
```python:bigO_2.py caption="bigO_2.py" showLineNumbers
import time
start = time.time()
i = 0 # phep gan +1
n = 1000000 # phep gan +1

while i < n: # phep so sanh +1
    print(i) # +1
    i += 1   # +1

# while n buoc -> (1+1+1)xn = 3n -> 3n + 2

print("time: " +  str(time.time() - start))
```
</div>
Thật dễ để hiểu đúng không?

Đến với vị dụ tiếp theo:
<div id="time-complexity-2">
```python:bigO_3.py caption="bigO_3.py" showLineNumbers
n = 10
x = 1
y = 2
# +3
for i in range(n): # phep so sanh i < n ? va phep i++ => +2
    for j in range(n): # phep so sanh j < n ? va phep j++ => +2
        x = x + 1 # +1
        y = y + 1 # +1
        # => 4n + 2
# => (4n + 2)xn
# => P(n) = 4n^2 + 2n + 3
# => O(n^2)
```
</div>
- $P(n) = 4n^2 + 2n + 3 \sim O(n^2)$

Đối với đoạn `code` dưới đây thì sao?
<div id="time-complexity-3">
```python:bigO_4.py caption="bigO_4.py" showLineNumbers
n = 10
x = 1
y = 2
i = 1
# +4
while i < n: # phep so sanh +1 
    x = x + 1 # +1
    i *= 2 # +1
    print(x)
```
</div>
- Do `i *= 2` nên vòng `while` không duyệt $n$ lần mà duyệt $log_2(n)$
- $P(n) = 3\log_{2}(n) + 4 \sim O(log_2(n))$

> [!NOTE]
> To be updated