คำถามฝึกหัดเกี่ยวกับการวิเคราะห์ Time Complexity ใน C++

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

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

หา time complexity ของโค้ดสนิปเพทต่อไปนี้

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

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

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

หา time complexity ของโค้ดสนิปเพทต่อไปนี้

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

Inner loop และ outer loop ทั้งคู่ execute n ครั้ง ดังนั้นสำหรับค่า i เดียว j จะลูป n ครั้ง สำหรับ n ค่าของ i j จะลูปรวม n*n = n² ครั้ง ดังนั้น time complexity คือ O(n²)

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

หา time complexity ของโค้ดสนิปเพทต่อไปนี้

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

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

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

หา time complexity ของโค้ดสนิปเพทต่อไปนี้

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

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

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

หา time complexity ของโค้ดสนิปเพทต่อไปนี้

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

Inner loop execute (log n) ครั้ง ในขณะที่ outer execute n ครั้ง ดังนั้นสำหรับค่า i เดียว j จะ execute (log n) ครั้ง สำหรับ n ค่าของ i j จะลูปรวม n*(log n) = (n log n) ครั้ง ดังนั้น time complexity คือ O(n log n)