[DSA] Phân tích độ phức tạp của một số bài toán

1. Bài toán kiểm tra số Palindrome

Độ phức tạp thời gian của thuật toán này là O(n/2), đơn giản hóa thành O(n) trong ký hiệu Big O. Điều này là do thuật toán lặp qua một nửa độ dài chuỗi để so sánh ký tự đầu tiên và ký tự cuối cùng, điều này yêu cầu n/2 lần lặp lại trong trường hợp xấu nhất. Do đó, độ phức tạp thời gian của thuật toán này là tuyến tính.

int isPalindrome(char *str) {

int i, j;

int len = strlen(str);

for (i = 0, j = len - 1; i < j; i++, j--) {

if (str[i] != str[j]) {

return 0; // not a palindrome

}

}

return 1; // is a palindrome

}

2. Bài toán tính lũy thừa của một số đã cho bằng cách sử dụng đệ quy

Độ phức tạp thời gian của hàm power có thể được phân tích như sau:

• Trong trường hợp tốt nhất, khi số mũ bằng 0, hàm sẽ trả về ngay lập tức mà không thực hiện bất kỳ lời gọi đệ quy nào. Do đó, trường hợp tốt nhất về độ phức tạp thời gian là O(1).Đây là phép toán có thời gian không đổi nên có thể coi là O(1).
• Độ phức tạp thời gian trong trường hợp xấu nhất của hàm lũy thừa là O(exponent). Vì trong trường hợp xấu nhất, hàm sẽ cần thực hiện các lệnh gọi đệ quy lũy thừa trước khi đến trường hợp cơ sở có số mũ bằng 0.

Ví dụ: nếu chúng ta gọi power(2, 5), hàm sẽ thực hiện các lệnh gọi đệ quy sau:

• power(2, 4)
• power(2, 3)
• power(2, 2)
• power(2, 1)
• power(2, 0)

Vì vậy, trong trường hợp xấu nhất, hàm thực hiện các cuộc gọi đệ quy theo cấp số nhân, điều này mang lại độ phức tạp về thời gian là O(exponent). Nhìn chung, độ phức tạp về thời gian của chương trình bị chi phối bởi độ phức tạp về thời gian của hàm lũy thừa, là O(exponent).

int power(int base, int exponent) {

if (exponent == 0) {

return 1;

} else {

return base * power(base, exponent-1);

}

}

3. Bài toán tính tổng các phần tử của mảng số nguyên dùng đệ quy

int sum(int arr[], int size) {

// base case: empty array

if (size == 0) {

return 0;

}

// recursive case: add first element and sum of remaining elements

else {

return arr[0] + sum(arr+1, size-1);

}

}

 Hàm sum() cộng đệ quy phần tử đầu tiên của mảng với tổng của các phần tử còn lại, cho đến khi gặp trường hợp cơ sở là khi mảng trống (nghĩa là kích thước bằng 0). Độ phức tạp thời gian của hàm này là O(n), trong đó n là kích thước của mảng. Điều này là do hàm cần cộng từng phần tử trong mảng để tính tổng, việc này yêu cầu n thao tác. Độ phức tạp của không gian là O(n), do hàm tự gọi n lần đệ quy, mỗi lần tạo một khung ngăn xếp mới (new stack frame).

4. Bài toán tìm ước chung lớn nhất dùng thuật toán Euclidean

// function to calculate GCD using Euclidean algorithm

int gcd(int a, int b) {

if (b == 0) {

return a;

}

return gcd(b, a % b);

}

Độ phức tạp về thời gian trong trường hợp xấu nhất của hàm gcd là O(log(min(a, b))) và độ phức tạp về thời gian trong trường hợp tốt nhất là O(1).

• Trong trường hợp xấu nhất, khi a và b nguyên tố cùng nhau, hàm sẽ thực hiện các lệnh gọi đệ quy log(min(a, b)) để đạt được trường hợp cơ sở. Điều này là do trong mỗi lệnh gọi đệ quy, hàm giảm kích thước bài toán bằng cách lấy modulo của số lớn hơn với số nhỏ hơn và trong trường hợp xấu nhất, số nhỏ hơn sẽ bằng một nửa kích thước của số lớn hơn.
• Trong trường hợp tốt nhất, khi a và b bằng nhau, hàm sẽ đạt đến trường hợp cơ sở trong một lệnh gọi đệ quy duy nhất, trả về giá trị của a. Vì đây là hoạt động thời gian không đổi nên độ phức tạp thời gian là O(1).

5. Tính giai thừa

// Recursive function to calculate the factorial of a given number

int factorial(int n)

{

// Base case: if n is 0 or 1, return 1

if (n == 0 || n == 1) {

return 1;

}

// Recursive case: calculate the factorial of (n-1) and multiply by n

else {

return n * factorial(n-1);

}

}

Độ phức tạp thời gian của hàm giai thừa có thể được phân tích bằng ký hiệu Big O. Trong trường hợp này, mỗi lệnh gọi đệ quy đến hàm ở phiên bản nhỏ hơn có ít hơn một phép nhân, cho đến khi đạt đến trường hợp cơ sở. Do đó, số lượng thao tác cần thiết tỷ lệ thuận với giá trị của n, dẫn đến độ phức tạp thời gian là O(n).

Độ phức tạp thời gian của hàm giai thừa là O(n) vì nó thực hiện việc gọi đệ quy cho mỗi số nguyên từ 1 đến n, do đó số lượng gọi đệ quy tỷ lệ thuận với n. Câu lệnh if có độ phức tạp thời gian không đổi là O(1) vì nó chỉ kiểm tra giá trị của n. Do đó, độ phức tạp thời gian chung của hàm là O(n * 1) = O(n).

Lưu ý rằng số lượng thao tác thực tế cần thiết để tính giai thừa của một số đã cho bằng cách sử dụng đệ quy có thể cao hơn nhiều so với sử dụng phương pháp lặp, do chi phí thực hiện nhiều lệnh gọi hàm. Do đó, trong thực tế, cách tiếp cận lặp lại có thể hiệu quả hơn để tính giai thừa của số lớn.

6. Tính tổng của các chữ số của số nguyên n cho trước

int sum_of_digits(int n) {

if (n == 0) {

return 0;

} else {

return n % 10 + sum_of_digits(n / 10);

}

}

Trong chương trình này, chúng ta định nghĩa một hàm sum_of_digits lấy một số nguyên n làm đầu vào (ví dụ n = 23782) và trả về tổng các chữ số của nó (2+3+7+8+2) bằng cách sử dụng đệ quy. 

• Trường hợp cơ bản là khi n = 0, thì hàm trả về 0. 
• Ngược lại, chúng ta cộng chữ số cuối cùng (tức là n % 10) vào tổng của các chữ số còn lại (tức là sum_of_digits(n / 10)).

Độ phức tạp về thời gian của hàm này có thể được phân tích bằng ký hiệu Big O như sau:

• Số lần gọi đệ quy phụ thuộc vào số chữ số của số nguyên n.
• Mỗi cuộc gọi đệ quy liên quan đến một lượng công việc không đổi (tức là lấy mô đun và chia cho 10).
• Do đó, độ phức tạp về thời gian của sum_of_digits là O(d), trong đó d là số chữ số trong n.

Nhìn chung, độ phức tạp về thời gian của chương trình bị chi phối bởi độ phức tạp về thời gian của hàm sum_of_digits.

7. Tính số chính phương (perfectSquare)

int isPerfectSquare(int n) {

int i = 1;

while (i*i <= n) {

if (i*i == n) {

return 1;

}

i++;

}

return 0;

}

Độ phức tạp về thời gian của hàm là O(sqrt(n)), bởi vì vòng lặp lặp đi lặp lại cho đến khi i đạt đến căn bậc hai của n, là sqrt(n). Tại mỗi lần lặp lại, một phép toán so sánh và nhân được thực hiện, mất thời gian không đổi. Do đó, độ phức tạp thời gian chung của hàm là O(sqrt(n)).

8. Đếm số kí tự ch xuất hiện trong 1 chuỗi

int countChar(char* str, char ch) {

if (*str == '\0') {

return 0; // Trường hợp đệ quy cơ bản: chuỗi rỗng

}

if (*str == ch) {

return 1 + countChar(str + 1, ch); // Ký tự đầu tiên trong chuỗi bằng ký tự cần đếm

}

return countChar(str + 1, ch); // Ký tự đầu tiên trong chuỗi không bằng ký tự cần đếm

}

Độ phức tạp của hàm countChar là O(n), với n là độ dài của chuỗi đầu vào.

• Trong trường hợp tốt nhất, khi ký tự cần đếm không xuất hiện trong chuỗi, hàm chỉ cần duyệt qua từng ký tự của chuỗi một lần và trả về giá trị 0.
• Trong trường hợp xấu nhất, khi tất cả các ký tự trong chuỗi đều bằng ký tự cần đếm, hàm sẽ phải duyệt qua từng ký tự của chuỗi và gọi đệ quy để xử lý các ký tự tiếp theo. Vì vậy, số lần gọi đệ quy sẽ bằng độ dài của chuỗi và độ phức tạp của hàm sẽ là O(n).

9. Tổng n phần tử đầu tiên

int sum(int n) {

if (n == 0) { // điều kiện dừng

return 0;

} else {

return n + sum(n-1); // đệ quy

}

}

Độ phức tạp của hàm sum là O(n), với n là đối số đầu vào.

• Trong trường hợp tốt nhất, khi n = 0, hàm chỉ cần trả về giá trị 0 và không thực hiện bất kỳ phép tính nào, nên độ phức tạp là O(1).
• Trong trường hợp xấu nhất, khi n là một số rất lớn, hàm sẽ phải gọi đệ quy n lần để tính tổng số tự nhiên đầu tiên. Vì vậy, số lần gọi đệ quy sẽ bằng n và độ phức tạp của hàm sẽ là O(n).

10. Kiểm tra xem một mảng đã cho có được sắp xếp theo thứ tự không giảm hay không

int isNonDecreasing(int arr[], int n) {

if (n == 1) { // Trường hợp đệ quy cơ bản: mảng chỉ có 1 phần tử

return 1;

}

if (arr[n-2] > arr[n-1]) { // Kiểm tra phần tử cuối cùng và phần tử liền trước của mảng

return 0;

}

return isNonDecreasing(arr, n-1); // Gọi đệ quy với mảng trừ đi phần tử cuối cùng

}

Độ phức tạp của hàm này là O(n), với n là số lượng phần tử trong mảng.

• Trong trường hợp tốt nhất, độ phức tạp của hàm isNonDecreasing là O(1) khi mảng đầu vào chỉ chứa một phần tử, bởi vì hàm này trực tiếp trả về 1 mà không có bất kỳ lệnh gọi đệ quy hoặc so sánh nào.
• Trong trường hợp xấu nhất, độ phức tạp của hàm isNonDecreasing là O(n) khi mảng đầu vào theo thứ tự giảm dần và nó cần duyệt qua tất cả n phần tử để xác định rằng mảng không phải là không giảm. Trong trường hợp này, hàm sẽ thực hiện n-1 lệnh gọi đệ quy trước khi đạt đến trường hợp cơ bản trong đó n bằng 1.
  

11. Đếm số từ trong chuỗi

int countWords(char* str) {

if (*str == '\0') {

return 0; // Trường hợp đệ quy cơ bản: chuỗi rỗng

}

if (*str == ' ' && *(str + 1) != ' ') {

return 1 + countWords(str + 1); // Đếm từ mới nếu ký tự hiện tại là dấu cách và ký tự tiếp theo khác dấu cách

}

return countWords(str + 1); // Không phải dấu cách hoặc ký tự tiếp theo cũng là dấu cách

}

Độ phức tạp của hàm này là O(n), với n là độ dài của chuỗi đầu vào. Hàm đệ quy sẽ duyệt qua từng ký tự của chuỗi, nên độ phức tạp của hàm là tuyến tính theo độ dài của chuỗi.