แบบฝึกหัด

6. ให้แสดงการคำนวณเวลาการประมวลของขั้นตอนวิธีต่อไปนี้อย่างละเอียด แล้วเขียนในรูปสัญลักษณ์บิ๊กโอ

6.1 sum = 0 ;

       for ( i = 0 ; i < N ; i++ )

                      for ( j = 0 ; j < N * N ; j++ )

                                    sum++ ;

คำตอบ  บรรทัดที่ 1  จากคำสั่ง  for  สำหรับลูปนอกให้ทำซ้ำ 
              บรรทัดที่ 2  n ครั้ง  และคำสั่ง for สำหรับลูปในให้ทำซ้ำ 
              บรรทัดที่  3  n ครั้ง เวลาที่ใช้เท่ากับ n*n =n( n กำลังสอง) 
              บรรทัดที่ 4  เขียนในรูปสัญลักษณ์บิ๊กโอ  คือ 0 n (n กำลังสอง)

6.2 int  factr ( int n )
 
                        int  t , answer ;

                        answer = 1

                         for ( t = 1 ; t <=  n ; t++ ) 

                                  answer = answer * t ;

                          return ( answer ) ;  

คำตอบ   1. บรรทัด 1 กำหนดค้าเริ่มต้นให้ตัวแปร  และบรรทัด 4  return   ผลลัพธ์ นับบรรทัดละ 1 หน่วยเวลา รวม 2 หน่วยเวลา
               2. บรรทัด 2 นับ 2n+2 หน่วยเวลา  คำสั่งบรรทัดนี้ประกอบด้วยการกำหนดค่าเริ่มต้นตัวแปร t นับ 1 หน่วยเวลา  การทดสอบเงื่อนไข t <= n ต้องทำซ้ำ n=1 นับ n + 1 หน่วยเวลา ส่วนคำสั่ง  increment  t++ ต้องทำซ้ำ n ครั้ง นับ n หน่วยเวลา จึงใช้เสลาทั้งหมด 2n+2 หน่วยเวลา 
               3. บรรทัด 3 นับ 2n หน่วยเวลา คำสั่งนี้ใช้เวลาเท่ากับ 2 หน่วยเวลา ประกอบด้วยการคูณ 1 ครั้ง และการกำหนดค่า 1 ครั้ง ถูกทำซ้ำ n ครั้ง รวมใช้เวลา 2n หน่วยเวลา
               4. รวมเวลาทั้งหมด 2+2n+2+2n  = 4n +4 เขียนฟังก์ชันในรูปสัญลักษณ์บิ๊กโอ คือ 0(n)