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

Độ phức tạp về thời gian của bất kỳ thuật toán nào là thời gian thực hiện của thuật toán đó để hoàn thành. Đây là một số liệu 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 tôi có xu hướng giảm độ phức tạp về 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 về 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ị lớn nhất n nhưng i sẽ được tăng lên hai lần trong vòng lặp for, điều này sẽ làm cho thời gian mất một nửa. Vì vậy, độ phức tạp về thời gian là O (n / 2) tương đương với O (n).

Ví dụ 2

Tìm độ phức tạp về 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 << " ";
   }
}

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

Ví dụ 3

Tìm độ phức tạp về 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 được chuyển thành một nửa giá trị trước đó của nó. Vì vậy, bộ truyện sẽ như thế nào:. Vì vậy, độ phức tạp về thời gian là O (log n).

Ví dụ 4

Tìm độ phức tạp về 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 về thời gian =O (1), đối với hai trong số chúng thì O (2) tương đương với O (1) là hằng số .

Ví dụ 5

Tìm độ phức tạp về 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 đang thực thi (log n) lần trong đó vòng lặp bên ngoài đang thực thi n lần. Vì vậy, đối với một giá trị của i, j đang thực hiện (log n) lần, với n giá trị của i, j sẽ lặp lại tổng n * (log n) =(n log n) lần. Vì vậy, độ phức tạp về thời gian là O (n log n).