Độ phức tạp thời gian¶

Thời gian chạy có thể phản ánh một cách trực quan và chính xác hiệu suất của một thuật toán. Nếu muốn ước lượng chính xác thời gian chạy của một đoạn mã, chúng ta nên tiến hành như thế nào?

Xác định nền tảng chạy, bao gồm cấu hình phần cứng, ngôn ngữ lập trình, môi trường hệ thống, v.v., vì những yếu tố này đều ảnh hưởng đến hiệu suất thực thi mã.
Đánh giá thời gian chạy cần thiết cho các thao tác tính toán khác nhau, ví dụ: phép cộng + mất 1 ns, phép nhân * mất 10 ns, thao tác in print() mất 5 ns, v.v.
Thống kê tất cả các thao tác tính toán trong mã, và cộng tổng thời gian thực thi của tất cả các thao tác để có được thời gian chạy.

Ví dụ trong đoạn mã dưới đây, kích thước dữ liệu đầu vào là \(n\):

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

# Trên một nền tảng chạy nhất định
def algorithm(n: int):
    a = 2      # 1 ns
    a = a + 1  # 1 ns
    a = a * 2  # 10 ns
    # Lặp n lần
    for _ in range(n):  # 1 ns
        print(0)        # 5 ns

// Trên một nền tảng chạy nhất định
void algorithm(int n) {
    int a = 2;  // 1 ns
    a = a + 1;  // 1 ns
    a = a * 2;  // 10 ns
    // Lặp n lần
    for (int i = 0; i < n; i++) {  // 1 ns
        cout << 0 << endl;         // 5 ns
    }
}

// Trên một nền tảng chạy nhất định
void algorithm(int n) {
    int a = 2;  // 1 ns
    a = a + 1;  // 1 ns
    a = a * 2;  // 10 ns
    // Lặp n lần
    for (int i = 0; i < n; i++) {  // 1 ns
        System.out.println(0);     // 5 ns
    }
}

// Trên một nền tảng chạy nhất định
void Algorithm(int n) {
    int a = 2;  // 1 ns
    a = a + 1;  // 1 ns
    a = a * 2;  // 10 ns
    // Lặp n lần
    for (int i = 0; i < n; i++) {  // 1 ns
        Console.WriteLine(0);      // 5 ns
    }
}

// Trên một nền tảng chạy nhất định
func algorithm(n int) {
    a := 2     // 1 ns
    a = a + 1  // 1 ns
    a = a * 2  // 10 ns
    // Lặp n lần
    for i := 0; i < n; i++ {  // 1 ns
        fmt.Println(a)        // 5 ns
    }
}

// Trên một nền tảng chạy nhất định
func algorithm(n: Int) {
    var a = 2 // 1 ns
    a = a + 1 // 1 ns
    a = a * 2 // 10 ns
    // Lặp n lần
    for _ in 0 ..< n { // 1 ns
        print(0) // 5 ns
    }
}

// Trên một nền tảng chạy nhất định
function algorithm(n) {
    var a = 2; // 1 ns
    a = a + 1; // 1 ns
    a = a * 2; // 10 ns
    // Lặp n lần
    for(let i = 0; i < n; i++) { // 1 ns
        console.log(0); // 5 ns
    }
}

// Trên một nền tảng chạy nhất định
function algorithm(n: number): void {
    var a: number = 2; // 1 ns
    a = a + 1; // 1 ns
    a = a * 2; // 10 ns
    // Lặp n lần
    for(let i = 0; i < n; i++) { // 1 ns
        console.log(0); // 5 ns
    }
}

// Trên một nền tảng chạy nhất định
void algorithm(int n) {
  int a = 2; // 1 ns
  a = a + 1; // 1 ns
  a = a * 2; // 10 ns
  // Lặp n lần
  for (int i = 0; i < n; i++) { // 1 ns
    print(0); // 5 ns
  }
}

// Trên một nền tảng chạy nhất định
fn algorithm(n: i32) {
    let mut a = 2;      // 1 ns
    a = a + 1;          // 1 ns
    a = a * 2;          // 10 ns
    // Lặp n lần
    for _ in 0..n {     // 1 ns
        println!("{}", 0);  // 5 ns
    }
}

// Trên một nền tảng chạy nhất định
void algorithm(int n) {
    int a = 2;  // 1 ns
    a = a + 1;  // 1 ns
    a = a * 2;  // 10 ns
    // Lặp n lần
    for (int i = 0; i < n; i++) {   // 1 ns
        printf("%d", 0);            // 5 ns
    }
}

// Trên một nền tảng chạy nhất định
fun algorithm(n: Int) {
    var a = 2 // 1 ns
    a = a + 1 // 1 ns
    a = a * 2 // 10 ns
    // Lặp n lần
    for (i in 0..<n) {  // 1 ns
        println(0)      // 5 ns
    }
}

# Trên một nền tảng chạy nhất định
def algorithm(n)
    a = 2       # 1 ns
    a = a + 1   # 1 ns
    a = a * 2   # 10 ns
    # Lặp n lần
    (0...n).each do # 1 ns
        puts 0      # 5 ns
    end
end

Theo phương pháp trên, thời gian chạy của thuật toán có thể được tính là \((6n + 12)\) ns:

\[ 1 + 1 + 10 + (1 + 5) \times n = 6n + 12 \]

Tuy nhiên trên thực tế, việc cố gắng thống kê thời gian chạy chính xác của một thuật toán là không thực tế và cũng không khả thi. Thứ nhất, chúng ta không muốn liên kết thời gian ước lượng với nền tảng chạy, bởi vì thuật toán cần chạy trên nhiều nền tảng khác nhau. Thứ hai, rất khó để biết thời gian chạy của từng loại thao tác, điều này khiến cho quá trình ước lượng trở nên vô cùng khó khăn.

Thống kê xu hướng tăng trưởng thời gian¶

Phân tích độ phức tạp thời gian không đếm thời gian chạy của thuật toán, mà là thống kê xu hướng tăng trưởng thời gian chạy của thuật toán khi lượng dữ liệu tăng lên.

Khái niệm "xu hướng tăng trưởng thời gian" khá trừu tượng; chúng ta hãy cùng hiểu nó thông qua một ví dụ. Giả sử kích thước dữ liệu đầu vào là \(n\), và cho ba thuật toán A, B, và C:

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

# Độ phức tạp thời gian của thuật toán A: bậc hằng số
def algorithm_A(n: int):
    print(0)
# Độ phức tạp thời gian của thuật toán B: bậc tuyến tính
def algorithm_B(n: int):
    for _ in range(n):
        print(0)
# Độ phức tạp thời gian của thuật toán C: bậc hằng số
def algorithm_C(n: int):
    for _ in range(1000000):
        print(0)

// Độ phức tạp thời gian của thuật toán A: bậc hằng số
void algorithm_A(int n) {
    cout << 0 << endl;
}
// Độ phức tạp thời gian của thuật toán B: bậc tuyến tính
void algorithm_B(int n) {
    for (int i = 0; i < n; i++) {
        cout << 0 << endl;
    }
}
// Độ phức tạp thời gian của thuật toán C: bậc hằng số
void algorithm_C(int n) {
    for (int i = 0; i < 1000000; i++) {
        cout << 0 << endl;
    }
}

// Độ phức tạp thời gian của thuật toán A: bậc hằng số
void algorithm_A(int n) {
    System.out.println(0);
}
// Độ phức tạp thời gian của thuật toán B: bậc tuyến tính
void algorithm_B(int n) {
    for (int i = 0; i < n; i++) {
        System.out.println(0);
    }
}
// Độ phức tạp thời gian của thuật toán C: bậc hằng số
void algorithm_C(int n) {
    for (int i = 0; i < 1000000; i++) {
        System.out.println(0);
    }
}

// Độ phức tạp thời gian của thuật toán A: bậc hằng số
void AlgorithmA(int n) {
    Console.WriteLine(0);
}
// Độ phức tạp thời gian của thuật toán B: bậc tuyến tính
void AlgorithmB(int n) {
    for (int i = 0; i < n; i++) {
        Console.WriteLine(0);
    }
}
// Độ phức tạp thời gian của thuật toán C: bậc hằng số
void AlgorithmC(int n) {
    for (int i = 0; i < 1000000; i++) {
        Console.WriteLine(0);
    }
}

// Độ phức tạp thời gian của thuật toán A: bậc hằng số
func algorithm_A(n int) {
    fmt.Println(0)
}
// Độ phức tạp thời gian của thuật toán B: bậc tuyến tính
func algorithm_B(n int) {
    for i := 0; i < n; i++ {
        fmt.Println(0)
    }
}
// Độ phức tạp thời gian của thuật toán C: bậc hằng số
func algorithm_C(n int) {
    for i := 0; i < 1000000; i++ {
        fmt.Println(0)
    }
}

// Độ phức tạp thời gian của thuật toán A: bậc hằng số
func algorithmA(n: Int) {
    print(0)
}

// Độ phức tạp thời gian của thuật toán B: bậc tuyến tính
func algorithmB(n: Int) {
    for _ in 0 ..< n {
        print(0)
    }
}

// Độ phức tạp thời gian của thuật toán C: bậc hằng số
func algorithmC(n: Int) {
    for _ in 0 ..< 1_000_000 {
        print(0)
    }
}

// Độ phức tạp thời gian của thuật toán A: bậc hằng số
function algorithm_A(n) {
    console.log(0);
}
// Độ phức tạp thời gian của thuật toán B: bậc tuyến tính
function algorithm_B(n) {
    for (let i = 0; i < n; i++) {
        console.log(0);
    }
}
// Độ phức tạp thời gian của thuật toán C: bậc hằng số
function algorithm_C(n) {
    for (let i = 0; i < 1000000; i++) {
        console.log(0);
    }
}

// Độ phức tạp thời gian của thuật toán A: bậc hằng số
function algorithm_A(n: number): void {
    console.log(0);
}
// Độ phức tạp thời gian của thuật toán B: bậc tuyến tính
function algorithm_B(n: number): void {
    for (let i = 0; i < n; i++) {
        console.log(0);
    }
}
// Độ phức tạp thời gian của thuật toán C: bậc hằng số
function algorithm_C(n: number): void {
    for (let i = 0; i < 1000000; i++) {
        console.log(0);
    }
}

// Độ phức tạp thời gian của thuật toán A: bậc hằng số
void algorithmA(int n) {
  print(0);
}
// Độ phức tạp thời gian của thuật toán B: bậc tuyến tính
void algorithmB(int n) {
  for (int i = 0; i < n; i++) {
    print(0);
  }
}
// Độ phức tạp thời gian của thuật toán C: bậc hằng số
void algorithmC(int n) {
  for (int i = 0; i < 1000000; i++) {
    print(0);
  }
}

// Độ phức tạp thời gian của thuật toán A: bậc hằng số
fn algorithm_A(n: i32) {
    println!("{}", 0);
}
// Độ phức tạp thời gian của thuật toán B: bậc tuyến tính
fn algorithm_B(n: i32) {
    for _ in 0..n {
        println!("{}", 0);
    }
}
// Độ phức tạp thời gian của thuật toán C: bậc hằng số
fn algorithm_C(n: i32) {
    for _ in 0..1000000 {
        println!("{}", 0);
    }
}

// Độ phức tạp thời gian của thuật toán A: bậc hằng số
void algorithm_A(int n) {
    printf("%d", 0);
}
// Độ phức tạp thời gian của thuật toán B: bậc tuyến tính
void algorithm_B(int n) {
    for (int i = 0; i < n; i++) {
        printf("%d", 0);
    }
}
// Độ phức tạp thời gian của thuật toán C: bậc hằng số
void algorithm_C(int n) {
    for (int i = 0; i < 1000000; i++) {
        printf("%d", 0);
    }
}

// Độ phức tạp thời gian của thuật toán A: bậc hằng số
fun algoritm_A(n: Int) {
    println(0)
}
// Độ phức tạp thời gian của thuật toán B: bậc tuyến tính
fun algorithm_B(n: Int) {
    for (i in 0..<n){
        println(0)
    }
}
// Độ phức tạp thời gian của thuật toán C: bậc hằng số
fun algorithm_C(n: Int) {
    for (i in 0..<1000000) {
        println(0)
    }
}

# Độ phức tạp thời gian của thuật toán A: bậc hằng số
def algorithm_A(n)
    puts 0
end

# Độ phức tạp thời gian của thuật toán B: bậc tuyến tính
def algorithm_B(n)
    (0...n).each { puts 0 }
end

# Độ phức tạp thời gian của thuật toán C: bậc hằng số
def algorithm_C(n)
    (0...1_000_000).each { puts 0 }
end

Hình dưới đây thể hiện xu hướng tăng trưởng thời gian của ba hàm thuật toán trên.

Thuật toán A chỉ có \(1\) thao tác in, và thời gian chạy của thuật toán không tăng khi \(n\) tăng. Chúng ta gọi độ phức tạp thời gian của thuật toán này là "bậc hằng số".
Trong thuật toán B, thao tác in cần lặp \(n\) lần, và thời gian chạy của thuật toán tăng tuyến tính khi \(n\) tăng. Độ phức tạp thời gian của thuật toán này được gọi là "bậc tuyến tính".
Trong thuật toán C, thao tác in cần lặp \(1000000\) lần. Mặc dù thời gian chạy rất dài, nhưng nó độc lập với kích thước dữ liệu đầu vào \(n\). Do đó, độ phức tạp thời gian của C giống như A, vẫn là "bậc hằng số".

So với việc đếm trực tiếp thời gian chạy của thuật toán, phân tích độ phức tạp thời gian có những đặc điểm gì?

Độ phức tạp thời gian có thể đánh giá hiệu suất thuật toán một cách hiệu quả. Ví dụ, thời gian chạy của thuật toán B tăng tuyến tính; khi \(n > 1\) nó chậm hơn thuật toán A, và khi \(n > 1000000\) nó chậm hơn thuật toán C. Trên thực tế, chỉ cần kích thước dữ liệu đầu vào \(n\) đủ lớn, thuật toán có độ phức tạp "bậc hằng số" sẽ luôn tốt hơn thuật toán có độ phức tạp "bậc tuyến tính", đó chính là ý nghĩa của xu hướng tăng trưởng thời gian.
Phương pháp suy dẫn độ phức tạp thời gian đơn giản hơn. Rõ ràng, nền tảng chạy và các loại thao tác tính toán đều không liên quan đến xu hướng tăng trưởng thời gian chạy của thuật toán. Do đó, trong phân tích độ phức tạp thời gian, chúng ta có thể coi thời gian thực thi của tất cả các thao tác tính toán như là cùng một "đơn vị thời gian", chuyển từ việc "theo dõi thời gian chạy của từng thao tác" thành "đếm số lượng thao tác", giúp giảm thiểu đáng kể độ khó của việc ước lượng.
Độ phức tạp thời gian cũng có những hạn chế nhất định. Ví dụ, mặc dù thuật toán A và C có cùng độ phức tạp thời gian, nhưng thời gian chạy thực tế của chúng khác biệt rất nhiều. Tương tự, mặc dù thuật toán B có độ phức tạp thời gian cao hơn C, nhưng khi kích thước dữ liệu đầu vào \(n\) nhỏ, thuật toán B rõ ràng là tốt hơn thuật toán C. Trong những trường hợp như vậy, thường rất khó để đánh giá hiệu quả của các thuật toán chỉ dựa trên độ phức tạp thời gian. Tất nhiên, bất chấp những vấn đề trên, phân tích độ phức tạp vẫn là phương pháp hiệu quả nhất và được sử dụng phổ biến nhất để đánh giá hiệu suất thuật toán.

Giới hạn trên tiệm cận của hàm số¶

Cho một hàm số với kích thước đầu vào là \(n\):

Gọi số lượng thao tác của thuật toán là một hàm theo kích thước dữ liệu đầu vào \(n\), ký hiệu là \(T(n)\). Khi đó số lượng thao tác của hàm trên là:

\[ T(n) = 3 + 2n \]

\(T(n)\) là một hàm tuyến tính, biểu thị xu hướng tăng trưởng thời gian chạy của nó là tuyến tính, và do đó độ phức tạp thời gian của nó thuộc bậc tuyến tính.

Chúng ta ký hiệu độ phức tạp thời gian bậc tuyến tính là \(O(n)\). Ký hiệu toán học này được gọi là ký hiệu \(O\) lớn (big-\(O\) notation), đại diện cho giới hạn trên tiệm cận (asymptotic upper bound) của hàm số \(T(n)\).

Phân tích độ phức tạp thời gian về bản chất là tính toán giới hạn trên tiệm cận của "số lượng thao tác \(T(n)\)", điều này có một định nghĩa toán học rõ ràng.

Giới hạn trên tiệm cận của hàm số

Nếu tồn tại các số thực dương \(c\) và \(n_0\) sao cho với mọi \(n > n_0\), ta có \(T(n) \leq c \cdot f(n)\), thì \(f(n)\) có thể được coi là một giới hạn trên tiệm cận của \(T(n)\), ký hiệu là \(T(n) = O(f(n))\).

Như hình dưới đây, việc tính toán giới hạn trên tiệm cận là tìm một hàm \(f(n)\) sao cho khi \(n\) tiến tới vô cực, \(T(n)\) và \(f(n)\) có cùng mức độ tăng trưởng, chỉ khác biệt bởi một hệ số hằng số \(c\).

Phương pháp suy dẫn¶

Khái niệm giới hạn trên tiệm cận mang tính toán học một chút. Nếu bạn cảm thấy chưa hoàn toàn hiểu rõ nó, đừng lo lắng. Chúng ta có thể làm quen với phương pháp suy dẫn trước, rồi dần dần nắm bắt ý nghĩa toán học của nó qua việc thực hành liên tục.

Theo định nghĩa, sau khi xác định được \(f(n)\), chúng ta có thể thu được độ phức tạp thời gian \(O(f(n))\). Vậy làm thế nào để xác định giới hạn trên tiệm cận \(f(n)\)? Nhìn chung, quá trình này được chia thành hai bước: đầu tiên là thống kê số lượng thao tác, sau đó là xác định giới hạn trên tiệm cận.

Bước 1: Thống kê số lượng thao tác¶

Đối với mã nguồn, hãy đếm từ trên xuống dưới theo từng dòng. Tuy nhiên, vì hệ số hằng số \(c\) trong biểu thức \(c \cdot f(n)\) ở trên có thể có kích thước bất kỳ, các hệ số và số hạng tự do (hằng số) trong số lượng thao tác \(T(n)\) đều có thể được bỏ qua. Theo nguyên tắc này, các mẹo đơn giản hóa việc thống kê sau đây có thể được đúc kết:

Bỏ qua các hằng số trong \(T(n)\). Vì chúng đều độc lập với \(n\), nên không ảnh hưởng đến độ phức tạp thời gian.
Lược bỏ tất cả các hệ số. Ví dụ, vòng lặp chạy \(2n\) lần, \(5n + 1\) lần, v.v., đều có thể được đơn giản hóa thành \(n\) lần, vì hệ số đứng trước \(n\) không ảnh hưởng đến độ phức tạp thời gian.
Sử dụng phép nhân cho các vòng lặp lồng nhau. Tổng số lượng thao tác bằng tích số lượng thao tác của vòng lặp ngoài và vòng lặp trong, với mỗi lớp vòng lặp vẫn có thể áp dụng các mẹo 1. và 2. một cách độc lập.

Cho một hàm số, chúng ta có thể sử dụng các mẹo trên để thống kê số lượng thao tác:

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

def algorithm(n: int):
    a = 1      # +0 (Mẹo 1)
    a = a + n  # +0 (Mẹo 1)
    # +n (Mẹo 2)
    for i in range(5 * n + 1):
        print(0)
    # +n*n (Mẹo 3)
    for i in range(2 * n):
        for j in range(n + 1):
            print(0)

void algorithm(int n) {
    int a = 1;  // +0 (Mẹo 1)
    a = a + n;  // +0 (Mẹo 1)
    // +n (Mẹo 2)
    for (int i = 0; i < 5 * n + 1; i++) {
        cout << 0 << endl;
    }
    // +n*n (Mẹo 3)
    for (int i = 0; i < 2 * n; i++) {
        for (int j = 0; j < n + 1; j++) {
            cout << 0 << endl;
        }
    }
}

void algorithm(int n) {
    int a = 1;  // +0 (Mẹo 1)
    a = a + n;  // +0 (Mẹo 1)
    // +n (Mẹo 2)
    for (int i = 0; i < 5 * n + 1; i++) {
        System.out.println(0);
    }
    // +n*n (Mẹo 3)
    for (int i = 0; i < 2 * n; i++) {
        for (int j = 0; j < n + 1; j++) {
            System.out.println(0);
        }
    }
}

void Algorithm(int n) {
    int a = 1;  // +0 (Mẹo 1)
    a = a + n;  // +0 (Mẹo 1)
    // +n (Mẹo 2)
    for (int i = 0; i < 5 * n + 1; i++) {
        Console.WriteLine(0);
    }
    // +n*n (Mẹo 3)
    for (int i = 0; i < 2 * n; i++) {
        for (int j = 0; j < n + 1; j++) {
            Console.WriteLine(0);
        }
    }
}

func algorithm(n int) {
    a := 1     // +0 (Mẹo 1)
    a = a + n  // +0 (Mẹo 1)
    // +n (Mẹo 2)
    for i := 0; i < 5 * n + 1; i++ {
        fmt.Println(0)
    }
    // +n*n (Mẹo 3)
    for i := 0; i < 2 * n; i++ {
        for j := 0; j < n + 1; j++ {
            fmt.Println(0)
        }
    }
}

func algorithm(n: Int) {
    var a = 1 // +0 (Mẹo 1)
    a = a + n // +0 (Mẹo 1)
    // +n (Mẹo 2)
    for _ in 0 ..< (5 * n + 1) {
        print(0)
    }
    // +n*n (Mẹo 3)
    for _ in 0 ..< (2 * n) {
        for _ in 0 ..< (n + 1) {
            print(0)
        }
    }
}

function algorithm(n) {
    let a = 1;  // +0 (Mẹo 1)
    a = a + n;  // +0 (Mẹo 1)
    // +n (Mẹo 2)
    for (let i = 0; i < 5 * n + 1; i++) {
        console.log(0);
    }
    // +n*n (Mẹo 3)
    for (let i = 0; i < 2 * n; i++) {
        for (let j = 0; j < n + 1; j++) {
            console.log(0);
        }
    }
}

function algorithm(n: number): void {
    let a = 1;  // +0 (Mẹo 1)
    a = a + n;  // +0 (Mẹo 1)
    // +n (Mẹo 2)
    for (let i = 0; i < 5 * n + 1; i++) {
        console.log(0);
    }
    // +n*n (Mẹo 3)
    for (let i = 0; i < 2 * n; i++) {
        for (let j = 0; j < n + 1; j++) {
            console.log(0);
        }
    }
}

void algorithm(int n) {
  int a = 1; // +0 (Mẹo 1)
  a = a + n; // +0 (Mẹo 1)
  // +n (Mẹo 2)
  for (int i = 0; i < 5 * n + 1; i++) {
    print(0);
  }
  // +n*n (Mẹo 3)
  for (int i = 0; i < 2 * n; i++) {
    for (int j = 0; j < n + 1; j++) {
      print(0);
    }
  }
}

fn algorithm(n: i32) {
    let mut a = 1;     // +0 (Mẹo 1)
    a = a + n;        // +0 (Mẹo 1)

    // +n (Mẹo 2)
    for i in 0..(5 * n + 1) {
        println!("{}", 0);
    }

    // +n*n (Mẹo 3)
    for i in 0..(2 * n) {
        for j in 0..(n + 1) {
            println!("{}", 0);
        }
    }
}

void algorithm(int n) {
    int a = 1;  // +0 (Mẹo 1)
    a = a + n;  // +0 (Mẹo 1)
    // +n (Mẹo 2)
    for (int i = 0; i < 5 * n + 1; i++) {
        printf("%d", 0);
    }
    // +n*n (Mẹo 3)
    for (int i = 0; i < 2 * n; i++) {
        for (int j = 0; j < n + 1; j++) {
            printf("%d", 0);
        }
    }
}

fun algorithm(n: Int) {
    var a = 1   // +0 (Mẹo 1)
    a = a + n   // +0 (Mẹo 1)
    // +n (Mẹo 2)
    for (i in 0..<5 * n + 1) {
        println(0)
    }
    // +n*n (Mẹo 3)
    for (i in 0..<2 * n) {
        for (j in 0..<n + 1) {
            println(0)
        }
    }
}

def algorithm(n)
    a = 1       # +0 (Mẹo 1)
    a = a + n   # +0 (Mẹo 1)
    # +n (Mẹo 2)
    (0...(5 * n + 1)).each do { puts 0 }
    # +n*n (Mẹo 3)
    (0...(2 * n)).each do
        (0...(n + 1)).each do { puts 0 }
    end
end

Công thức dưới đây thể hiện kết quả thống kê trước và sau khi sử dụng các mẹo trên; cả hai đều suy ra độ phức tạp thời gian là \(O(n^2)\).

\[ \begin{aligned} T(n) & = 2n(n + 1) + (5n + 1) + 2 & \text{Thống kê đầy đủ (-.-|||)} \newline & = 2n^2 + 7n + 3 \newline T(n) & = n^2 + n & \text{Thống kê đơn giản hóa (o.O)} \end{aligned} \]

Bước 2: Xác định giới hạn trên tiệm cận¶

Độ phức tạp thời gian được quyết định bởi số hạng bậc cao nhất trong \(T(n)\). Điều này là do khi \(n\) tiến tới vô cực, số hạng bậc cao nhất sẽ đóng vai trò chủ đạo, và ảnh hưởng của các số hạng khác có thể được bỏ qua.

Bảng dưới đây đưa ra một số ví dụ, trong đó một số giá trị phóng đại được sử dụng để nhấn mạnh kết luận rằng "hệ số không thể làm thay đổi cấp bậc". Khi \(n\) tiến tới vô cực, các hằng số này trở nên không đáng kể.

Bảng Độ phức tạp thời gian tương ứng với số lượng thao tác khác nhau

Số lượng thao tác \(T(n)\)	Độ phức tạp thời gian \(O(f(n))\)
\(100000\)	\(O(1)\)
\(3n + 2\)	\(O(n)\)
\(2n^2 + 3n + 2\)	\(O(n^2)\)
\(n^3 + 10000n^2\)	\(O(n^3)\)
\(2^n + 10000n^{10000}\)	\(O(2^n)\)

Các dạng thường gặp¶

Gọi kích thước dữ liệu đầu vào là \(n\). Các dạng độ phức tạp thời gian phổ biến được thể hiện ở hình dưới đây (sắp xếp theo thứ tự từ thấp đến cao).

\[ \begin{aligned} & O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(2^n) < O(n!) \newline & \text{Hằng số} < \text{Lôgarit} < \text{Tuyến tính} < \text{Tuyến tính - lôgarit} < \text{Bình phương} < \text{Mũ} < \text{Giai thừa} \end{aligned} \]

Bậc hằng số \(O(1)\)¶

Số lượng thao tác thuộc bậc hằng số độc lập với kích thước dữ liệu đầu vào \(n\), nghĩa là nó không thay đổi khi \(n\) thay đổi.

Trong hàm dưới đây, mặc dù giá trị của size có thể rất lớn, nhưng nó độc lập với kích thước dữ liệu đầu vào \(n\), do đó độ phức tạp thời gian vẫn là \(O(1)\):

[file]{time_complexity}-[class]{}-[func]{constant}

Bậc tuyến tính \(O(n)\)¶

Số lượng thao tác thuộc bậc tuyến tính tăng tuyến tính tương đối so với kích thước dữ liệu đầu vào \(n\). Bậc tuyến tính thường xuất hiện trong các vòng lặp đơn (một lớp vòng lặp):

[file]{time_complexity}-[class]{}-[func]{linear}

Các thao tác như duyệt mảng và duyệt danh sách liên kết có độ phức tạp thời gian là \(O(n)\), trong đó \(n\) là độ dài của mảng hoặc danh sách liên kết:

[file]{time_complexity}-[class]{}-[func]{array_traversal}

Cần lưu ý rằng kích thước dữ liệu đầu vào \(n\) nên được xác định tùy theo loại dữ liệu đầu vào. Ví dụ, trong ví dụ đầu tiên, biến \(n\) là kích thước dữ liệu đầu vào; trong ví dụ thứ hai, độ dài mảng \(n\) là kích thước dữ liệu.

Bậc bình phương \(O(n^2)\)¶

Số lượng thao tác thuộc bậc bình phương tăng theo cấp số bình phương tương đối so với kích thước dữ liệu đầu vào \(n\). Bậc bình phương thường xuất hiện trong các vòng lặp lồng nhau, trong đó cả vòng lặp ngoài và vòng lặp trong đều có độ phức tạp thời gian là \(O(n)\), dẫn đến độ phức tạp thời gian tổng thể là \(O(n^2)\):

[file]{time_complexity}-[class]{}-[func]{quadratic}

Hình dưới đây so sánh độ phức tạp thời gian bậc hằng số, bậc tuyến tính và bậc bình phương.

Lấy thuật toán sắp xếp nổi bọt (bubble sort) làm ví dụ, vòng lặp ngoài thực thi \(n - 1\) lần, vòng lặp trong lần lượt thực thi \(n-1\), \(n-2\), \(\dots\), \(2\), \(1\) lần, trung bình là \(n / 2\) lần, dẫn đến độ phức tạp thời gian là \(O((n - 1) n / 2) = O(n^2)\):

[file]{time_complexity}-[class]{}-[func]{bubble_sort}

Bậc mũ \(O(2^n)\)¶

Sự "phân bào" (phân chia tế bào) trong sinh học là một ví dụ điển hình cho sự tăng trưởng theo bậc mũ: trạng thái ban đầu là \(1\) tế bào, sau một vòng phân chia thành \(2\), sau hai vòng thành \(4\), v.v.; sau \(n\) vòng phân chia sẽ có \(2^n\) tế bào.

Hình dưới đây và đoạn mã sau đây mô phỏng quá trình phân chia tế bào, với độ phức tạp thời gian là \(O(2^n)\). Lưu ý rằng đầu vào \(n\) đại diện cho số vòng phân chia, và giá trị trả về count đại diện cho tổng số lượng tế bào sau phân chia.

[file]{time_complexity}-[class]{}-[func]{exponential}

Trong thuật toán thực tế, bậc mũ thường xuất hiện trong các hàm đệ quy. Ví dụ, trong đoạn mã dưới đây, nó đệ quy phân tách làm hai nhánh, dừng lại sau \(n\) lần phân tách:

[file]{time_complexity}-[class]{}-[func]{exp_recur}

Sự tăng trưởng theo bậc mũ rất nhanh chóng và thường thấy trong các phương pháp vét cạn (tìm kiếm thô bạo/brute force, quay lui/backtracking, v.v.). Đối với các bài toán có quy mô dữ liệu lớn, bậc mũ là không thể chấp nhận được và thường đòi hỏi phải sử dụng quy hoạch động (dynamic programming) hoặc thuật toán tham lam (greedy algorithm) để giải quyết.

Bậc lôgarit \(O(\log n)\)¶

Ngược lại với bậc mũ, bậc lôgarit phản ánh tình huống "giảm một nửa sau mỗi vòng". Gọi kích thước dữ liệu đầu vào là \(n\). Vì nó giảm một nửa sau mỗi vòng, số lượng vòng lặp là \(\log_2 n\), đây là hàm ngược của \(2^n\).

Hình dưới đây và đoạn mã sau đây mô phỏng quá trình "giảm một nửa sau mỗi vòng", với độ phức tạp thời gian là \(O(\log_2 n)\), viết tắt là \(O(\log n)\):

[file]{time_complexity}-[class]{}-[func]{logarithmic}

Tương tự như bậc mũ, bậc lôgarit cũng thường xuất hiện trong các hàm đệ quy. Đoạn mã sau tạo ra một cây đệ quy có chiều cao là \(\log_2 n\):

[file]{time_complexity}-[class]{}-[func]{log_recur}

Bậc lôgarit thường xuất hiện trong các thuật toán dựa trên chiến lược chia để trị (divide-and-conquer), phản ánh ý tưởng liên tục chia nhỏ bài toán và đơn giản hóa nó. Nó tăng trưởng rất chậm và là độ phức tạp thời gian lý tưởng chỉ sau bậc hằng số.

Cơ số của \(O(\log n)\) là bao nhiêu?

Nói một cách chính xác, "chia thành \(m\) phần" tương ứng với độ phức tạp thời gian là \(O(\log_m n)\). Và thông qua công thức đổi cơ số lôgarit, chúng ta có thể chứng minh các độ phức tạp thời gian có cơ số khác nhau là tương đương nhau:

\[ O(\log_m n) = O(\log_k n / \log_k m) = O(\log_k n) \]

Nghĩa là cơ số \(m\) có thể được chuyển đổi mà không ảnh hưởng đến độ phức tạp. Do đó, chúng ta thường lược bỏ cơ số \(m\) và ký hiệu bậc lôgarit đơn giản là \(O(\log n)\).

Bậc tuyến tính - lôgarit \(O(n \log n)\)¶

Bậc tuyến tính - lôgarit thường xuất hiện trong các vòng lặp lồng nhau, trong đó độ phức tạp thời gian của hai lớp vòng lặp lần lượt là \(O(\log n)\) và \(O(n)\). Đoạn mã liên quan như sau:

[file]{time_complexity}-[class]{}-[func]{linear_log_recur}

Hình dưới đây cho thấy cách bậc tuyến tính - lôgarit được tạo ra. Mỗi cấp độ của cây nhị phân có tổng cộng \(n\) thao tác, và cây có \(\log_2 n + 1\) cấp độ, dẫn đến độ phức tạp thời gian là \(O(n \log n)\).

Các thuật toán sắp xếp chính thống (phổ biến) thường có độ phức tạp thời gian là \(O(n \log n)\), chẳng hạn như sắp xếp nhanh (quicksort), sắp xếp trộn (merge sort) và sắp xếp vun đống (heap sort).

Bậc giai thừa \(O(n!)\)¶

Bậc giai thừa tương ứng với bài toán "hoán vị" trong toán học. Cho \(n\) phần tử phân biệt, tìm tất cả các phương án sắp xếp có thể; số lượng phương án là:

\[ n! = n \times (n - 1) \times (n - 2) \times \dots \times 2 \times 1 \]

Giai thừa thường được triển khai bằng đệ quy. Như được thể hiện trong hình dưới đây và đoạn mã sau, cấp độ đầu tiên phân tách thành \(n\) nhánh, cấp độ thứ hai phân tách thành \(n - 1\) nhánh, và cứ tiếp tục như vậy cho đến cấp độ thứ \(n\) thì dừng phân tách:

[file]{time_complexity}-[class]{}-[func]{factorial_recur}

Lưu ý rằng vì khi \(n \geq 4\), chúng ta luôn có \(n! > 2^n\), nên bậc giai thừa tăng trưởng nhanh hơn bậc mũ, và cũng là không thể chấp nhận được đối với \(n\) lớn.

Độ phức tạp thời gian trong trường hợp xấu nhất, tốt nhất và trung bình¶

Hiệu suất thời gian của một thuật toán thường không cố định mà liên quan đến sự phân bố của dữ liệu đầu vào. Giả sử chúng ta nhập vào một mảng nums có độ dài \(n\), trong đó nums gồm các số từ \(1\) đến \(n\), mỗi số chỉ xuất hiện một lần nhưng thứ tự phần tử bị xáo trộn ngẫu nhiên. Nhiệm vụ là trả về chỉ số (index) của phần tử \(1\). Chúng ta có thể rút ra các kết luận sau:

Khi nums = [?, ?, ..., 1], tức là khi phần tử cuối cùng là \(1\), thuật toán yêu cầu duyệt qua toàn bộ mảng, đạt đến độ phức tạp thời gian trong trường hợp xấu nhất là \(O(n)\).
Khi nums = [1, ?, ?, ...], tức là khi phần tử đầu tiên là \(1\), bất kể mảng dài bao nhiêu, không cần tiếp tục duyệt nữa, đạt đến độ phức tạp thời gian trong trường hợp tốt nhất là \(\Omega(1)\).

"Độ phức tạp thời gian trong trường hợp xấu nhất" tương ứng với giới hạn trên tiệm cận của hàm số, được ký hiệu bằng ký hiệu \(O\) lớn. Tương ứng, "độ phức tạp thời gian trong trường hợp tốt nhất" tương ứng với giới hạn dưới tiệm cận của hàm số, được ký hiệu bằng ký hiệu \(\Omega\):

[file]{worst_best_time_complexity}-[class]{}-[func]{find_one}

Cần lưu ý rằng chúng ta hiếm khi sử dụng độ phức tạp thời gian trong trường hợp tốt nhất trong thực tế, bởi vì nó thường chỉ đạt được với xác suất rất nhỏ và có thể gây hiểu nhầm ở mức độ nào đó. Độ phức tạp thời gian trong trường hợp xấu nhất thực tế hơn vì nó đưa ra một giá trị an toàn cho hiệu suất, giúp chúng ta yên tâm sử dụng thuật toán.

Từ ví dụ trên, chúng ta có thể thấy rằng cả độ phức tạp thời gian trong trường hợp xấu nhất và tốt nhất đều chỉ phát sinh dưới những phân bố đầu vào cụ thể, điều này có thể xảy ra với xác suất rất thấp và có thể không phản ánh đúng hiệu suất vận hành thực tế của thuật toán. Ngược lại, độ phức tạp thời gian trung bình có thể phản ánh hiệu suất vận hành của thuật toán dưới dữ liệu đầu vào ngẫu nhiên, được ký hiệu bằng ký hiệu \(\Theta\).

Đối với một số thuật toán, chúng ta có thể suy ra trường hợp trung bình dưới sự phân bố dữ liệu ngẫu nhiên một cách đơn giản. Ví dụ, trong ví dụ trên, vì mảng đầu vào bị xáo trộn, xác suất phần tử \(1\) xuất hiện ở bất kỳ chỉ số nào là bằng nhau, do đó số vòng lặp trung bình của thuật toán là một nửa độ dài mảng \(n / 2\), mang lại độ phức tạp thời gian trung bình là \(\Theta(n / 2) = \Theta(n)\).

Nhưng đối với các thuật toán phức tạp hơn, việc tính toán độ phức tạp thời gian trung bình thường khá khó khăn, vì rất khó phân tích kỳ vọng toán học tổng thể dưới phân bố dữ liệu. Trong trường hợp này, chúng ta thường sử dụng độ phức tạp thời gian trong trường hợp xấu nhất làm tiêu chí để đánh giá hiệu quả thuật toán.

Tại sao ký hiệu \(\Theta\) lại hiếm khi được nhìn thấy?

Điều này có thể là do ký hiệu \(O\) quá phổ biến, vì vậy chúng ta thường sử dụng nó để đại diện cho độ phức tạp thời gian trung bình. Nhưng nói một cách nghiêm túc, cách làm này không chuẩn mực. Trong cuốn sách này và các tài liệu khác, nếu bạn bắt gặp các diễn đạt như "độ phức tạp thời gian trung bình là \(O(n)\)", xin vui lòng hiểu trực tiếp đó là \(\Theta(n)\).