ขั้นตอน อัลกอริทึม

ขั้นตอนวิธี (Algorithm)

          คือกระบวนวิธีการ(procedure)ซึ่งประกอบด้วยกลุ่มของกฎเกณฑ์ ข้อกำหนดเฉพาะที่ไม่สับสน กำหนดถึงลำดับของวิธีการ(operations) ซึ่งให้ผลลัพธ์สำหรับปัญหาต่าง ๆ ในรูปของขั้นตอนที่มีจำนวนจำกัด

คุณสมบัติของขั้นตอนวิธี

·     ขั้นตอนวิธีเป็นกระบวนการที่สร้างขึ้นมาจากกลุ่มของกฎเกณฑ์

·     กฎเกณฑ์ที่สร้างขั้นตอนวิธีจะต้องไม่คลุมเครือ(definiteness)

·     การประมวลผล operations ที่กำหนดโดยกฎเกณฑ์จะต้องเป็นลำดับที่แน่นอน(effectiveness)

·     กระบวนวิธีการต้องให้ผลลัพธ์ตามที่กำหนดในปัญหา โดยออกแบบให้อยู่ในรูปแบบทั่วไป (generality)

·     ขั้นตอนวิธีต้องอยู่ในรูปของขั้นตอนวิธีการที่มีการสิ้นสุดได้(finiteness)

Algorithm 1 Finding the maximum element in a finite sequence

procedure max(a₁, a₂, …, a_n: integers);

max := a₁

for i := 2 to n

      if max < a_i  then max := a_i

{ max is the largest element }

Searching Algorithm

Algorithm2 The linear search algorithm

procedure linear search(x:integer, a₁, a₂, …, a_n: distinct integers)

i := 1

while (i £  n  and x ¹  a_i )

            i  :=  i  + 1

if   i £  n  then  location  := i

else location := 0

{location is the subscript of term that equal x, or is 0 if x is not found}

ตัวอย่าง จงค้นหาค่า 19 จากชุดข้อมูลดังต่อไปนี้

1  2  3  5  6  7  8  10  12  13  15  16  18  19  20  22

1  2  3  5  6  7  8  10                  12  13  15  16  18  19  20  22

12  13  15  16           18  19  20  22

18  19            20  22

18               19

Algorithm 3 The binary search algorithm

procedure binary search(x : integer, a₁, a₂, …, a_n: increasing  integers)

i := 1 { i is the left endpoint of search interval }

j := 1 { j is the right endpoint of search interval }

while (i £  j)

       begin

            m := ë(I + j )/2 û

if   x > a_m  then   i := m + 1

else j  := m

       end

       if   x = a_i  then  location  := i

       else location := 0

{location is the subscript of term that equal to x, or is 0 if x is not found}

 

Outline

1)     การประเมินผลโปรแกรม

2)     เครื่องมือช่วยในการประเมินผลโปรแกรม

3)     ตัวอย่างการเปรียบเทียบประสิทธิภาพ

การประเมินผลโปรแกรม

t = f(n)

s = g(n)

n = Size of the problem

t = Time needed to get the solution

s = Total memory space required by solution

1. การประเมินผลโปรแกรม

การประเมินผลโปรแกรมว่ามีประสิทธิภาพหรือไม่ โดยไม่ขึ้นกับปัจจัยภายนอกอื่นๆ จะใช้เกณฑ์การประเมินผลที่

1.      ความเร็วในการประมวลผล

2.      เนื้อที่ที่ต้องใช้ในหน่วยความจำระหว่างที่มีการประมวลผล

การประมวลผลที่โปรแกรม

เราจะประเมินผลที่โปรแกรมได้จากการวิเคราะห์ความซับซ้อนของ Algorithm ที่ใช้ในโปรแกรมนั้น (Complexity of Algorithm) ดังนี้

ให้ M เป็น Algorithm หนึ่ง และ n เป็นจำนวนข้อมูลดังนั้น เวลาและพื้นที่ ที่ใช้ใน Algorithm M จะเป็นตัววัดประสิทธิภาพของ Algorithm

ความซับซ้อนของ Algorithm M จะอยู่ในรูปของฟังชันก์ f(n) ซึ่งจะให้ค่าของเวลาที่ใช้ และหรือพื้นที่ที่ต้องการใช้ชอง Algorithm ในเทอมของขนาด n ซึ่งเป็นข้อมูล อินพุต

2. เครื่องมือช่วยในการประเมินผลโปรแกรม

O-notation

อัตราการเพิ่มของเวลาหรือพื้นที่หน่วยความจำตามจำนวนของข้อมูล : Rate of Growth

Time and Space Complexity

t   O[f(n)]

s  O[g(n)]

n  =  Size of the problem

f(n)  =  Time complexity

g(n)  =  Space complexity

ใช้วิธีการแทนที่การประมวลผล Algorithm นั้นๆ ด้วย Function  ที่มีค่าประมารค่าหนึ่ง โดยวิธีการหาว่า Function นั้นจะมีค่าประมาณเป็นเท่าใดนั้น ให้ใช้วิธีการแทนที่ปริมาณของปัญหาที่ต้องการให้ Algorithm ทำให้ แล้วสังเกตว่า เกิดการประมวลผลกี่ครั้ง หรือมีการใช้เนื้อที่เป็นจำนวนเท่าใด จากนั้นทำการเปรียบเทียบฟังก์ชันที่ได้นี้กับฟังก์ชันมาตรฐานทางคณิตศาสตร์ เช่น log₂n , n , nlog₂n , n² , n³ , 2ⁿ  เพื่อประเมินว่า Algorithm นั้นมีประสิทธิภาพอย่างไร

ข้อมูลถูกหาพบเมื่อ ITEM = DATA[LOC]

ตัวอย่าง  : Linear Search Algorithm

LOC              DATA                               ITEM

R  T  H                      P   E   U

U

1

2

3

4

5

6

กรณีนี้เรียกว่า " Worst Case " หมายถึง พบข้อมูลที่ขั้นตอนสุดท้ายหรือไม่พบข้อมูลเลย ดังนั้นจะได้ฟังก์ชัน f(n) = n โดย n =  เทอมของจำนวนอินพุต =  6

ข้อมูลถูกหาพบเมื่อ ITEM = DATA[LOC]

ตัวอย่าง  : Linear Search Algorithm

LOC                DATA                               ITEM

U                          T                           H

U

1

		R

 

กรณีนี้เรียกว่า " Best Case " หมายถึง พบข้อมูลที่ขั้นตอนแรกสุดเลย ดังนั้นจะได้ฟังก์ชัน f(n) =  cโดย   n =  เทอมของจำนวนอินพุต =  6

          c =  ค่าคงที่ = 1

Complexity เป็นฟังก์ชันของ n

	Log n	n	nlogn	n2	n3	2n
5 10 100 1000	3 4 7 10	5 10 100 103	15 40 700 104	25 100 104 106	125 103 106 109	32 103 1030 10300

ตารางแสดงอัตราการเจริญเติบโตของฟังก์ชันมาตรฐานตามขนาดของ

Complexity ในรูปของกราฟ

 

กราฟแสดงการเปรียบเทียบการใช้เครื่องมือวัด ระหว่างโปรแกรม 3 โปรแกรม

ตัวอย่าง : Linear Search Algorithm

Average Case

เป็นค่าเฉลี่ยของความน่าจะเป็นที่จะพบข้อมูล ITEM ในตำแหน่งใด ๆ ของอาร์เรย์ DATA

คำนวณได้ดังนี้ f(n) = 1(1/n) + 2(1/n) + 3(1/n) + … + n(1/n)

                        = (1+2+3+…+n)(1/n)

                         = ((n(n+1))/2) (1/n)

                        = (n+1)/2

โดย n    เป็นจำนวนครั้งของการเปรียบเทียบ

       1/n  เป็นความน่าจะเป็นที่จะพบข้อมูลในครั้งนั้น

Complexity

Worst Case

          ค่าสูงสุดของ f(n) สำหรับอินพุตที่กำหนด

Best Case

          ค่าต่ำสุดของ f(n) สำหรับอินพุตที่กำหนด

Average Case

          ค่าโดยประมาณของ f(n)

ตัวอย่าง : การเปรียบเทียบประสิทธิภาพ

*ต้องการเรียงข้อมูล 1,000,000 เรคคอร์ด

1.      Operation สำหรับการเปรียบเทียบการ Index และ Housekeeping รวม ๆ แล้ว เช่น 20 คำสั่งพื้นฐาน

2.      ถ้าใช้คอมพิวเตอร์ที่ความเร่งนาฬิกา 200 MHz: ซึ่งหนึ่งคำสั่งพื้นฐานใช้ 1 สัญญานาฬิกา นั่นคือ 1/(200*10⁶) วินาที

3.      20 คำสั่งใช้ 20/(200*10⁶) = 10^-7 วินาที

4.      สำหรับ Bubble Sort และ Insertion Sort เวลาที่ใช้ประมาณ   n ² ซึ่งจะประเมินโดยใช้ n ² /2

1,000,000*1,000,000*10 ^-7    =  500,000*10 ^-6 *10 ^-7

                                  =  50,000 วินาที

                                  ~= 1,000 นาที

                                  ~= 16.6 ชั่วโมง

5.      สำหรับ Quick sort และ Heap sort เวลาที่ใช้ประมาณ nlog ₂ n ซึ่งจะประเมินโดยใช้ nlog ₂n /2

1,000,000*20*10 ^-7              = 1,000,000*10*10 ^-7

          2                      

= 1 วินาที

อนึ่งสำหรับ Quick sort กรณีเลวร้ายที่สุดจะเป็น ~n ²

สรุป Complexity ที่สำคัญ

Commonly used the terminology for	the complexity of Algorithms.
Complexity	Terminology
O(1)	Constant complexity
O(log n)	Logarithmic complexity
O(n)	Linear complexity
O(n log n)	n log n complexity
O(nb)	Polynomial  complexity
O(bn)   where b > 1	Exponential complexity
O(n!)	Factorial complexity