คำถามฝึกหัดเกี่ยวกับการวิเคราะห์ความซับซ้อนของเวลาใน C ++

ความซับซ้อนของเวลา ของอัลกอริธึมใด ๆ เป็นเวลาที่อัลกอริธึมใช้ในการทำให้เสร็จ เป็นตัวชี้วัดที่สำคัญในการแสดงประสิทธิภาพของอัลกอริธึมและสำหรับการวิเคราะห์เปรียบเทียบ เรามักจะลดความซับซ้อนของเวลาของอัลกอริทึมซึ่งทำให้มีประสิทธิภาพมากขึ้น

ตัวอย่างที่ 1

ค้นหาความซับซ้อนของเวลาของข้อมูลโค้ดต่อไปนี้

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

ลูปมีค่าสูงสุด n แต่ i จะเพิ่มขึ้นสองครั้งในลูป for ซึ่งจะทำให้เวลาใช้เวลาครึ่งหนึ่ง ดังนั้นความซับซ้อนของเวลาคือ O(n/2) ซึ่งเทียบเท่ากับ O(n)

ตัวอย่างที่ 2

ค้นหาความซับซ้อนของเวลาของข้อมูลโค้ดต่อไปนี้

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

วงในและวงนอกทั้งคู่กำลังดำเนินการ n ครั้ง ดังนั้นสำหรับค่าเดียวของ i j จะวนซ้ำ n ครั้ง สำหรับค่า n ของ i j จะวนซ้ำทั้งหมด n*n =n 2 ครั้ง ดังนั้นความซับซ้อนของเวลาคือ O(n 2 )

ตัวอย่างที่ 3

ค้นหาความซับซ้อนของเวลาของข้อมูลโค้ดต่อไปนี้

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

ในกรณีนี้ หลังจากการวนซ้ำแต่ละครั้ง ค่าของ i จะกลายเป็นครึ่งหนึ่งของค่าก่อนหน้า ดังนั้นซีรีย์จะเป็นเช่น:. ดังนั้นความซับซ้อนของเวลาคือ O(log n)

ตัวอย่างที่ 4

ค้นหาความซับซ้อนของเวลาของข้อมูลโค้ดต่อไปนี้

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

มีคำสั่งเงื่อนไขสองคำสั่งในรหัส คำสั่งแบบมีเงื่อนไขแต่ละรายการมีความซับซ้อนของเวลา =O(1) สำหรับสองคำสั่งคือ O(2) ซึ่งเทียบเท่ากับ O(1) ซึ่งก็คือ ค่าคงที่ .

ตัวอย่างที่ 5

ค้นหาความซับซ้อนของเวลาของข้อมูลโค้ดต่อไปนี้

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

วงในกำลังดำเนินการ (log n) ครั้งที่ด้านนอกกำลังดำเนินการ n ครั้ง ดังนั้นสำหรับค่าเดียวของ i j กำลังดำเนินการ (log n) ครั้ง สำหรับค่า n ของ i j จะวนซ้ำทั้งหมด n*(log n) =(n log n) ครั้ง ดังนั้นความซับซ้อนของเวลาคือ O(n log n)