Câu hỏi thực hành về phân tích độ phức tạp thời gian trong C++

Độ phức tạp thời gian của bất kỳ thuật toán nào là thời gian mà thuật toán đó cần để hoàn thành. Nó là một chỉ số quan trọng để thể hiện hiệu quả của thuật toán và để phân tích so sánh. Chúng ta xu hướng giảm độ phức tạp thời gian của thuật toán để làm cho nó hiệu quả hơn.

Ví dụ 1

Tìm độ phức tạp thời gian của các đoạn mã sau

for(i= 0 ; i < n; i++){
    cout<< i << " " ;
    i++;
 }

Vòng lặp có giá trị tối đa n nhưng i sẽ được tăng gấp đôi trong vòng lặp for, làm giảm thời gian một nửa. Vì vậy, độ phức tạp thời gian là O(n/2) tương đương với O(n).

Ví dụ 2

Tìm độ phức tạp thời gian của các đoạn mã sau

for(i= 0 ; i < n; i++){
    for(j = 0; j<n ;j++){
        cout<< i << " ";
    }
 }

Vòng lặp bên trong và vòng lặp bên ngoài đều thực thi n lần. Vì vậy, cho một giá trị của i, j lặp n lần, cho n giá trị của i, j sẽ lặp tổng cộng n*n = n^2 lần. Vì vậy, độ phức tạp thời gian là O(n^2).

Ví dụ 3

Tìm độ phức tạp thời gian của các đoạn mã sau

int i = n;
while(i){
    cout << i << " ";
    i = i/2;
 }

Trong trường hợp này, sau mỗi lần lặp, giá trị của i bị giảm một nửa so với giá trị trước. Vì vậy, dãy sẽ như sau: . Vì vậy, độ phức tạp thời gian là O(log n).

Ví dụ 4

Tìm độ phức tạp thời gian của các đoạn mã sau

if(i > j ){
    j>23 ? cout<<j : cout<<i;
 }

Có hai câu lệnh điều kiện trong mã. Mỗi câu lệnh điều kiện có độ phức tạp thời gian = O(1), cho hai câu lệnh là O(2) tương đương với O(1) là hằng số.

Ví dụ 5

Tìm độ phức tạp thời gian của các đoạn mã sau

for(i= 0; i < n; i++){
    for(j = 1; j < n; j = j*2){
        cout << i << " ";
    }
 }

Vòng lặp bên trong thực thi (log n) lần, vòng lặp bên ngoài thực thi n lần. Vì vậy, cho một giá trị của i, j thực thi (log n) lần, cho n giá trị của i, j sẽ lặp tổng cộng n*(log n) = (n log n) lần. Vì vậy, độ phức tạp thời gian là O(n log n).