Ví dụ phân tích độ phức tạp thuật toán

Bài viết này sẽ giúp bạn hiểu cách phân tích độ phức tạp thông qua các ví dụ cụ thể với lời giải chi tiết từng bước.

Ví dụ 1: Tính tổng các số từ 1 đến n

Bài toán

Tính tổng 1 + 2 + 3 + ... + n

Cách 1: Vòng lặp

Python


def sum_1_to_n(n):
    total = 0           # 1 phép gán
    for i in range(1, n + 1):  # Lặp n lần
        total += i      # 1 phép cộng + 1 phép gán
    return total        # 1 phép return

Kotlin


fun sum1ToN(n: Int): Int {
    var total = 0           // 1 phép gán
    for (i in 1..n) {       // Lặp n lần
        total += i          // 1 phép cộng + 1 phép gán
    }
    return total            // 1 phép return
}

Dart


int sum1ToN(int n) {
  int total = 0;           // 1 phép gán
  for (int i = 1; i <= n; i++) {  // Lặp n lần
    total += i;            // 1 phép cộng + 1 phép gán
  }
  return total;            // 1 phép return
}

Swift


func sum1ToN(_ n: Int) -> Int {
    var total = 0           // 1 phép gán
    for i in 1...n {        // Lặp n lần
        total += i          // 1 phép cộng + 1 phép gán
    }
    return total            // 1 phép return
}

Java


int sum1ToN(int n) {
    int total = 0;          // 1 phép gán
    for (int i = 1; i <= n; i++) {  // Lặp n lần
        total += i;         // 1 phép cộng + 1 phép gán
    }
    return total;           // 1 phép return
}

Phân tích:

Khởi tạo total: 1 phép
Vòng lặp chạy n lần, mỗi lần 2 phép (cộng và gán)
Return: 1 phép

Tổng: 1 + 2n + 1 = 2n + 2 → O(n)

Cách 2: Công thức toán học

Python


def sum_1_to_n_formula(n):
    return n * (n + 1) // 2  # 3 phép: nhân, cộng, chia

Kotlin


fun sum1ToNFormula(n: Int): Int {
    return n * (n + 1) / 2  // 3 phép: nhân, cộng, chia
}

Dart


int sum1ToNFormula(int n) {
  return n * (n + 1) ~/ 2;  // 3 phép: nhân, cộng, chia
}

Swift


func sum1ToNFormula(_ n: Int) -> Int {
    return n * (n + 1) / 2  // 3 phép: nhân, cộng, chia
}

Java


int sum1ToNFormula(int n) {
    return n * (n + 1) / 2;  // 3 phép: nhân, cộng, chia
}

Phân tích:

Chỉ có 3 phép cố định (dù n lớn đến đâu)

Tổng: 3 → O(1)

💡

Cùng một bài toán nhưng thuật toán khác nhau có độ phức tạp khác nhau: O(n) vs O(1)!

Ví dụ 2: Tìm số lớn nhất trong mảng

Bài toán

Cho mảng n số nguyên, tìm số lớn nhất.

Python


def find_max(arr):
    max_val = arr[0]        # 1 phép
    for i in range(1, len(arr)):  # Lặp n-1 lần
        if arr[i] > max_val:      # 1 so sánh
            max_val = arr[i]      # 1 gán (có thể không chạy)
    return max_val          # 1 phép

Kotlin


fun findMax(arr: IntArray): Int {
    var maxVal = arr[0]         // 1 phép
    for (i in 1 until arr.size) {  // Lặp n-1 lần
        if (arr[i] > maxVal) {     // 1 so sánh
            maxVal = arr[i]        // 1 gán
        }
    }
    return maxVal               // 1 phép
}

Dart


int findMax(List<int> arr) {
  int maxVal = arr[0];          // 1 phép
  for (int i = 1; i < arr.length; i++) {  // Lặp n-1 lần
    if (arr[i] > maxVal) {      // 1 so sánh
      maxVal = arr[i];          // 1 gán
    }
  }
  return maxVal;                // 1 phép
}

Swift


func findMax(_ arr: [Int]) -> Int {
    var maxVal = arr[0]         // 1 phép
    for i in 1..<arr.count {    // Lặp n-1 lần
        if arr[i] > maxVal {    // 1 so sánh
            maxVal = arr[i]     // 1 gán
        }
    }
    return maxVal               // 1 phép
}

Java


int findMax(int[] arr) {
    int maxVal = arr[0];        // 1 phép
    for (int i = 1; i < arr.length; i++) {  // Lặp n-1 lần
        if (arr[i] > maxVal) {  // 1 so sánh
            maxVal = arr[i];    // 1 gán
        }
    }
    return maxVal;              // 1 phép
}

Phân tích:

Khởi tạo: 1 phép
Vòng lặp: (n-1) lần × 1-2 phép mỗi lần
Return: 1 phép

Best case: Phần tử đầu là max → (n-1) so sánh, 0 gán Worst case: Mảng tăng dần → (n-1) so sánh, (n-1) gán

Tổng: ~ n phép → O(n)

Ví dụ 3: Kiểm tra số có trùng lặp

Bài toán

Cho mảng n số, kiểm tra xem có phần tử nào xuất hiện 2 lần không?

Cách 1: So sánh từng cặp (Brute Force)

Python


def has_duplicate_slow(arr):
    n = len(arr)
    for i in range(n):           # Vòng 1: n lần
        for j in range(i + 1, n):  # Vòng 2: trung bình n/2 lần
            if arr[i] == arr[j]:   # 1 so sánh
                return True
    return False

Kotlin


fun hasDuplicateSlow(arr: IntArray): Boolean {
    val n = arr.size
    for (i in 0 until n) {           // Vòng 1: n lần
        for (j in i + 1 until n) {   // Vòng 2
            if (arr[i] == arr[j]) {  // 1 so sánh
                return true
            }
        }
    }
    return false
}

Dart


bool hasDuplicateSlow(List<int> arr) {
  int n = arr.length;
  for (int i = 0; i < n; i++) {           // Vòng 1: n lần
    for (int j = i + 1; j < n; j++) {     // Vòng 2
      if (arr[i] == arr[j]) {             // 1 so sánh
        return true;
      }
    }
  }
  return false;
}

Swift


func hasDuplicateSlow(_ arr: [Int]) -> Bool {
    let n = arr.count
    for i in 0..<n {                // Vòng 1: n lần
        for j in (i + 1)..<n {      // Vòng 2
            if arr[i] == arr[j] {   // 1 so sánh
                return true
            }
        }
    }
    return false
}

Java


boolean hasDuplicateSlow(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n; i++) {           // Vòng 1: n lần
        for (int j = i + 1; j < n; j++) {   // Vòng 2
            if (arr[i] == arr[j]) {         // 1 so sánh
                return true;
            }
        }
    }
    return false;
}

Phân tích:

i=0: so sánh n-1 lần
i=1: so sánh n-2 lần
…
i=n-2: so sánh 1 lần

Tổng: (n-1) + (n-2) + … + 1 = n(n-1)/2 ≈ n²/2 → O(n²)

Cách 2: Dùng Set (Hash Table)

Python


def has_duplicate_fast(arr):
    seen = set()          # O(1)
    for num in arr:       # n lần
        if num in seen:   # O(1) trung bình
            return True
        seen.add(num)     # O(1) trung bình
    return False

Kotlin


fun hasDuplicateFast(arr: IntArray): Boolean {
    val seen = mutableSetOf<Int>()  // O(1)
    for (num in arr) {              // n lần
        if (num in seen) {          // O(1) trung bình
            return true
        }
        seen.add(num)               // O(1) trung bình
    }
    return false
}

Dart


bool hasDuplicateFast(List<int> arr) {
  Set<int> seen = {};         // O(1)
  for (int num in arr) {      // n lần
    if (seen.contains(num)) { // O(1) trung bình
      return true;
    }
    seen.add(num);            // O(1) trung bình
  }
  return false;
}

Swift


func hasDuplicateFast(_ arr: [Int]) -> Bool {
    var seen = Set<Int>()     // O(1)
    for num in arr {          // n lần
        if seen.contains(num) { // O(1) trung bình
            return true
        }
        seen.insert(num)      // O(1) trung bình
    }
    return false
}

Java


boolean hasDuplicateFast(int[] arr) {
    Set<Integer> seen = new HashSet<>();  // O(1)
    for (int num : arr) {                 // n lần
        if (seen.contains(num)) {         // O(1) trung bình
            return true;
        }
        seen.add(num);                    // O(1) trung bình
    }
    return false;
}

Phân tích:

Vòng lặp: n lần
Mỗi lần: O(1) cho contains và add

Tổng: n × O(1) = O(n)

⚠️

Space-time tradeoff: Cách 2 nhanh hơn O(n) nhưng cần thêm O(n) bộ nhớ cho Set!

Ví dụ 4: Binary Search

Bài toán

Tìm vị trí của target trong mảng đã sắp xếp.

Python


def binary_search(arr, target):
    left, right = 0, len(arr) - 1  # O(1)
    
    while left <= right:           # Lặp bao nhiêu lần?
        mid = (left + right) // 2  # O(1)
        if arr[mid] == target:     # O(1)
            return mid
        elif arr[mid] < target:    # O(1)
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

Kotlin


fun binarySearch(arr: IntArray, target: Int): Int {
    var left = 0
    var right = arr.size - 1
    
    while (left <= right) {         // Lặp bao nhiêu lần?
        val mid = (left + right) / 2
        when {
            arr[mid] == target -> return mid
            arr[mid] < target -> left = mid + 1
            else -> right = mid - 1
        }
    }
    return -1
}

Dart


int binarySearch(List<int> arr, int target) {
  int left = 0, right = arr.length - 1;
  
  while (left <= right) {           // Lặp bao nhiêu lần?
    int mid = (left + right) ~/ 2;
    if (arr[mid] == target) return mid;
    else if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

Swift


func binarySearch(_ arr: [Int], _ target: Int) -> Int {
    var left = 0, right = arr.count - 1
    
    while left <= right {           // Lặp bao nhiêu lần?
        let mid = (left + right) / 2
        if arr[mid] == target { return mid }
        else if arr[mid] < target { left = mid + 1 }
        else { right = mid - 1 }
    }
    return -1
}

Java


int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    
    while (left <= right) {         // Lặp bao nhiêu lần?
        int mid = (left + right) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

Phân tích số lần lặp:

Lần lặp	Kích thước vùng tìm kiếm
1	n
2	n/2
3	n/4
k	n/2^(k-1)

Dừng khi: n/2^(k-1) = 1 → k = log₂n + 1

Tổng: O(log n)

Ví dụ 5: Nested Loops Analysis

Bài toán

Phân tích các dạng vòng lặp lồng nhau khác nhau.

Dạng 1: Hai vòng lặp độc lập

Python


def example_1(n):
    for i in range(n):      # n lần
        print(i)
    
    for j in range(n):      # n lần
        print(j)

Kotlin


fun example1(n: Int) {
    for (i in 0 until n) {  // n lần
        println(i)
    }
    for (j in 0 until n) {  // n lần
        println(j)
    }
}

Dart


void example1(int n) {
  for (int i = 0; i < n; i++) {  // n lần
    print(i);
  }
  for (int j = 0; j < n; j++) {  // n lần
    print(j);
  }
}

Swift


func example1(_ n: Int) {
    for i in 0..<n {        // n lần
        print(i)
    }
    for j in 0..<n {        // n lần
        print(j)
    }
}

Java


void example1(int n) {
    for (int i = 0; i < n; i++) {  // n lần
        System.out.println(i);
    }
    for (int j = 0; j < n; j++) {  // n lần
        System.out.println(j);
    }
}

Phân tích: n + n = 2n → O(n)

Dạng 2: Hai vòng lặp lồng nhau

Python


def example_2(n):
    for i in range(n):          # n lần
        for j in range(n):      # n lần cho mỗi i
            print(i, j)

Kotlin


fun example2(n: Int) {
    for (i in 0 until n) {      // n lần
        for (j in 0 until n) {  // n lần
            println("$i $j")
        }
    }
}

Dart


void example2(int n) {
  for (int i = 0; i < n; i++) {      // n lần
    for (int j = 0; j < n; j++) {    // n lần
      print("$i $j");
    }
  }
}

Swift


func example2(_ n: Int) {
    for i in 0..<n {            // n lần
        for j in 0..<n {        // n lần
            print("\(i) \(j)")
        }
    }
}

Java


void example2(int n) {
    for (int i = 0; i < n; i++) {      // n lần
        for (int j = 0; j < n; j++) {  // n lần
            System.out.println(i + " " + j);
        }
    }
}

Phân tích: n × n = n² → O(n²)

Dạng 3: Vòng lặp giảm dần

Python


def example_3(n):
    for i in range(n):              # i từ 0 đến n-1
        for j in range(i, n):       # j từ i đến n-1
            print(i, j)

Kotlin


fun example3(n: Int) {
    for (i in 0 until n) {
        for (j in i until n) {
            println("$i $j")
        }
    }
}

Dart


void example3(int n) {
  for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
      print("$i $j");
    }
  }
}

Swift


func example3(_ n: Int) {
    for i in 0..<n {
        for j in i..<n {
            print("\(i) \(j)")
        }
    }
}

Java


void example3(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            System.out.println(i + " " + j);
        }
    }
}

Phân tích:

i=0: n lần
i=1: n-1 lần
…
i=n-1: 1 lần

Tổng: n + (n-1) + … + 1 = n(n+1)/2 → O(n²)

Bảng tóm tắt

Ví dụ	Thuật toán	Time	Space
Tổng 1-n	Vòng lặp	O(n)	O(1)
Tổng 1-n	Công thức	O(1)	O(1)
Tìm max	Duyệt	O(n)	O(1)
Kiểm tra trùng	Brute force	O(n²)	O(1)
Kiểm tra trùng	Set	O(n)	O(n)
Binary Search	Chia đôi	O(log n)	O(1)
2 vòng lặp	Độc lập	O(n)	O(1)
2 vòng lặp	Lồng nhau	O(n²)	O(1)

Tiếp theo: Mảng (Array)