Độ phức tạp về thời gian có thể được định nghĩa là thời gian theo yêu cầu của thuật toán để chạy trường hợp trung bình của nó.
Hãy xem và tính toán độ phức tạp về thời gian của một số hàm cơ bản.
Phương pháp
void counter(int n){
for(int i = 0 ; i < n ; i++){
for(int j = 1 ; j<n ; j += i ){
cout<<i<<” ”<<j;
}
cout<<endl;
}
} Phương thức trên sẽ chạy n / I lần cho tất cả các giá trị của i. tức là n lần cho lần lặp đầu tiên và 1 lần cho lần lặp cuối cùng.
Theo điều này, tổng độ phức tạp về thời gian là
(n/1 + n/2 + n/3 + …. + n/n) = n (1/1 + ½ + ⅓ + …. 1/n)
Bây giờ giá trị của (1/1 + ½ + ⅓ +…. 1 / n) bằng O (log n) .
Độ phức tạp về thời gian của mã này là O (nlogn) .
Phương pháp
void counter(n){
int i , j ;
for(int i = 1 ; i <= n ; i++){
for(j = 1; j <= log(i) ; j++){
cout<<i<<” ”<<j;
}
}
} Tổng độ phức tạp của hàm là O (log 1) + O (log 2) + O (log 3) +…. + O (log n) là O (log n!).