ความซับซ้อนของเวลา สามารถกำหนดเป็นเวลาที่อัลกอริธึมเรียกใช้กรณีเฉลี่ยได้
มาดูและคำนวณความซับซ้อนของเวลาของฟังก์ชันพื้นฐานบางอย่างกัน
วิธีการ
void counter(int n){
for(int i = 0 ; i < n ; i++){
for(int j = 1 ; j<n ; j += i ){
cout<<i<<” ”<<j;
}
cout<<endl;
}
} วิธีการข้างต้นจะรัน n/I ครั้งสำหรับค่าทั้งหมดของ i เช่น n ครั้งสำหรับการทำซ้ำครั้งแรกและ 1 ครั้งสำหรับการทำซ้ำครั้งสุดท้าย
ตามนี้ ความซับซ้อนของเวลาทั้งหมดคือ
(n/1 + n/2 + n/3 + …. + n/n) = n (1/1 + ½ + ⅓ + …. 1/n)
ตอนนี้ค่าของ (1/1 + ½ + ⅓ + …. 1/n) เท่ากับ O(log n) .
ความซับซ้อนของเวลาของรหัสนี้คือ O(nlogn) .
วิธีการ
void counter(n){
int i , j ;
for(int i = 1 ; i <= n ; i++){
for(j = 1; j <= log(i) ; j++){
cout<<i<<” ”<<j;
}
}
} ความซับซ้อนทั้งหมดของฟังก์ชันคือ O(log 1) + O(log 2) + O(log 3) + …. + O(log n) ซึ่งก็คือ O(log n!).
