now

Report
Introduction to Data Structure
and Algorithm
บทที่ 2 ความรู้เบือ้ งต้ นเกี่ยวกับโครงสร้ างข้ อมูล
และขัน้ ตอนวิธี
วัตถุประสงค์ เพือ่
• เข้ าใจหลักนามธรรมที่ม่งุ เน้ นการแก้ ไขปั ญหาด้ วยการตัดทอนสิง่ ซับซ้ อน
ปลีกย่อยที่ไม่จาเป็ นออกไป
• บอกรายละเอียดทัว่ ไปของซูโดโค้ ด รวมถึงสามารถเขียนซูโดโค้ ดที่ครบ
องค์ประกอบได้
• บอกความหมายของชนิดข้ อมูลนามธรรมได้
• เห็นความสาคัญต่อการวิเคราะห์ประสิทธิภาพของอัลกอริ ทมึ
• บอกประสิทธิภาพของลูปชนิดต่างๆ ที่นาไปใช้ งานในโปรแกรมได้
• เข้ าใจความหายของสัญลักษณ์บิ๊กโอ และสามารถนาไปประยุกต์ใช้ เพื่อการ
วิเคราะห์ประสิทธิภาพของอัลกอริ ทมึ
หัวข้ อที่บรรยาย
•
•
•
•
•
•
•
•
•
หลักนามธรรม
อัลกอริ ทมึ กับความเป็ นนามธรรมโดยธรรมชาติ
ซูโดโค้ ด
การสร้ างประโยคคาสัง่
ความรู้เกี่ยวกับชนิดข้ อมูลนามธรรม
การวัดผลอัลกอริ ทมึ
ประสิทธิภาพของอัลกอริ ทมึ
สัญลักษณ์บิ๊กโอ
ตัวอย่างการวิเคราะห์บิ๊กโอ
1. หลักนามธรรม (Abstraction)
หลักนามธรรมจะทาให้ ทกุ สิ่งในโลกแห่งความเป็ นจริ งดูงา่ ยดาย
ขึ ้น ด้ วยการพิจารณาบางสิ่งแยกออกจากความเป็ นจริ งของสิ่งเหล่านัน้
โดยอธิบายว่าสิ่งสิ่งนันท
้ าอะไร ไม่ต้องมุง่ เน้ นในรายละเอียดว่าต้ อง
ทางานอย่างไร
ดังนันการคิ
้
ดด้ วยหลักนามธรรมนี ้ จึงทาให้ เราสามารถคิดวิธีการ
แก้ ไขปั ญหาด้ วยการตัดทอนสิ่งที่ซบั ซ้ อน หรื อรายละเอียดปลีกย่อยที่ไม่
จาเป็ นออกไปได้
Grady Booch กล่าวว่า.. “Abstraction เป็ นหนึง่ ในแนวทางพื ้นฐานของมนุษย์
ที่ใช้ สาหรับจัดการกับความซับซ้ อน”
2. อัลกอริทึมกับความเป็ นนามธรรมโดยธรรมชาติ
• อัลกอริ ทมึ สามารถทาให้ เป็ นรูปธรรมได้ ด้วยการผ่าน “ตัวแทน
(Representation)”
 เรื่ องราวในนวนิยาย ถือเป็ นนามธรรม หรื อแนวคิด
 หนังสือ คือตัวแทนทางกายภาพของนวนิยาย
• อัลกอริ ทมึ ก็คือกระบวนการที่นาไปใช้ สร้ างโปรแกรมเพื่อทางานและแก้ ไข
ปั ญหาตามที่เราต้ องการ
• ตัวแทนก็คือโปรแกรมที่ได้ รับการพัฒนาขึ ้นจากอัลกอริ ทมึ นัน้ หรื อกล่าวอีก
นัยหนึง่ ก็คือ
 โปรแกรม คือตัวแทนของอัลกอริ ทมึ
 โปรเซส คือกิจกรรมที่เอ็กซีคิวต์อลั กอริ ทมึ นัน้
3. ซูโดโค้ ด (Pseudo Code)
• ซูโดโค้ ดมีรูปแบบคล้ ายประโยคภาษาอังกฤษ ที่ใช้ อธิบายรายละเอียด
การพัฒนาอัลกอริทมึ
• ซูโดโค้ ดใช้ สาหรับออกแบบการทางานและตรรกะของโปรแกรมที่สร้ าง
ขึ ้น ดังนันซู
้ โดโค้ ดจึงไม่สามารถนาไปเอ็กซีควิ ต์บนคอมพิวเตอร์ ได้
โดยตรง และจะออกแบบเพื่อนาไปพัฒนาเป็ นโปรแกรมจริงต่อไป
• ซูโดโค้ ดไม่ขึ ้นกับภาษาคอมพิวเตอร์ ภาษาใดภาษาหนึง่ แต่สามารถ
แปลงเป็ นภาษาคอมพิวเตอร์ เช่น ภาษา PASCAL, C++ หรื อ
JAVA ได้ ง่าย
3. ซูโดโค้ ด (Pseudo Code)
• การเขียนซูโดโค้ ดจะเขียนมุง่ เน้ นประโยคกิจกรรมที่ใช้ ในการเอ็กซีคิวต์
โปรแกรมเป็ นสาคัญ โดยสามารถสร้ างประโยคคาสัง่ แบบเรี ยงลาดับ
กาหนดทางเลือก และการทางานเป็ นรอบ
ตัวอย่ างซูโดโค้ ด
Algorithm sample (pageNumber)
This algorithm reads a file and prints a report.
Pre
pageNumber passed by reference
Post
Report Printed
pageNumber contains number of pages in report
Return Number of lines printed
1 Loop (not end of file)
1 read file
2 if (full page)
1 increment page number
2 write page heading
3 end if
4 write report line
5 increment line count
2 end loop
3
return line count
end sample
ส่ วนประกอบของอัลกอริทึม
•
•
•
•
ส่วนหัวของอัลกอริทมึ
จุดประสงค์ เงื่อนไข และการรี เทิร์นค่า
เลขลาดับประโยคคาสัง่
ตัวแปร
ส่ วนหัวของอัลกอริทึม
•
•
•
•
เรี ยกทับศัพท์วา่ เฮดเดอร์ (Header)
กาหนดชื่ออัลกอริทมึ
อธิบายรายละเอียดของพารามิเตอร์ (Parameters)
เงื่อนไขก่อน (Preconditions) และเงื่อนไขหลัง
(Postconditions)
จุดประสงค์ เงือ่ นไข และการรีเทิร์นค่ า
• อธิบายเรื่ องทัว่ ไปของการประมวลในอัลกอริทมึ นัน้ แต่ไม่ได้ อธิบาย
รายละเอียดทังหมดของกระบวนการว่
้
าทางานอย่างไร
• ในกรณีที่ไม่มีเงื่อนไขก่อน สามารถเขียนให้ อยูใ่ นรูปแบบ ดังนี ้
Pre nothing
• ตัวอย่างการกาหนดรายละเอียดในเฮดเดอร์
Algorithm search (list, argument, location)
Search array for specific item and return index location.
Pre
list contains data array to be searched
argument contains data to be located in list
Post
location contains matching index
-or- undetermined if not found
Return true if found, false if not found
เลขลาดับประโยคคาสั่ ง
• ประโยคคาสัง่ จะมีเลขลาดับกากับไว้ ซึง่ จะใช้ เลขทศนิยม ด้ วยการ
ลาดับหมายเลขเพิ่มขึ ้นทีละหนึง่ ภายในโครงสร้ างของบล็อกนันๆ
้
• ตัวอย่าง เช่น จากอัลกอริทมึ Sample
– เลขลาดับ 1.1 คือประโยคคาสัง่ read file
– เลขลาดับ 1.2.2 คือประโยคคาสัง่ write page heading
ตัวแปร (Variables)
• ไม่ควรตังชื
้ ่อตัวแปรด้ วยอักขระเพียงตัวเดียว เช่น A, B, C ยกเว้ นตัว
แปรในการกาหนดลูป ส่วนใหญ่ใช้ ตวั แปร i และ j แต่หากหลีกเลี่ยงได้ ก็
จะดี เช่น
– ต้ องการค้ นหาข้ อมูลในอาร์ เรย์สองมิติ โดยแต่ละแถวใช้ แทนนักศึกษา และแต่ละ
คอลัมน์ใช้ แทนคะแนนทดสอบ ดังนันตั
้ วแปรที่ใช้ แทนตัวชี ้ตาแหน่งแถวและ
คอลัมน์ควรใช้ student และ score จะสื่อความหมายได้ ดีกว่า
• ไม่ควรใช้ คาทัว่ ไปที่มีความหมายเฉพาะ (Generic Names) เช่น
count, sum, total, row, column, file เป็ นต้ น ถ้ าต้ องการ
ตัวแปรที่เก็บจานวนนักศึกษา อาจกาหนดตัวแปรว่า studentCount
หรื อ numberOfStudent ดีกว่าชื่อ count
ตัวแปร (Variables)
• หากจาเป็ นต้ องใช้ คาย่อก็ควรตังชื
้ ่อให้ สื่อความหมายได้ ดี เช่น
stdCnt ใช้ แทน studentCount หรื อ numOfStd ใช้ แทน
numberOfStudent ไม่ควรใช้ noStd เพราะอาจ
ตีความหมายว่า noStudent ที่หมายถึงไม่มีนกั ศึกษา
4. การสร้ างประโยคคาสั่ ง
• แบบเรี ยงลาดับ (Sequence)
• แบบเลือกการทางาน (Selection)
• แบบทางานซ ้า (Repetition/Loop)
ตัวอย่ างผังงาน
ตัวอย่ างผังงาน
ตัวอย่ างอัลกอริทึม
Algorithm deviation
Pre
nothing
Post
average and numbers with their deviation printed
1
loop (not end of file)
1 read number into array
2 add number to total
3 increment count
2
end loop
3
set average to total/count
4
print average
5
loop (not end of array)
1 set devFromAve to array element-average
2 print array element and devFromAve
6
end loop
end deviation
5. ความรู้เกีย่ วกับชนิดข้ อมูลนามธรรม
•
•
•
•
ข้ อมูลเชิงเดี่ยวและข้ อมูลเชิงประกอบ
ชนิดข้ อมูล
โครงสร้ างข้ อมูล
ชนิดข้ อมูลนามธรรม
ข้ อมูลเชิงเดีย่ วและข้ อมูลเชิงประกอบ
• ข้ อมูลเชิงเดี่ยว (Atomic Data) คือข้ อมูลที่ประกอบด้ วยค่าเดียวที่
ไม่สามารถแบ่งส่วนข้ อมูลนี ้ออกไปเพื่อสื่อความหมายได้ อกี เช่น เลข
จานวนเต็ม 4562 เป็ นต้ น
• ข้ อมูลเชิงประกอบ (Composite Data) โดยข้ อมูลเชิงประกอบ
นันสามารถที
้
่จะทาการแตกออกเป็ นฟิ ลด์ยอ่ ย (Subfields) และสิง่
ที่แตกออกไปก็ยงั มีความหมายด้ วย เช่น หมายเลขโทรศัพท์ทเี่ ป็ นตัวเลข
ล้ วนๆ คือ ตัวเลข 3 ตัวแรกเป็ นรหัสจังหวัด ส่วนที่เหลือคือเบอร์
หมายเลข เป็ นต้ น
ชนิดข้ อมูล (Data Type)
Type
Integer
Floating Point
Character
Values
−, … , −2, −1, 0, 1, 2, … , 
−, … , 0.0, … , 
\0, … , ′′ , ′ ′ , … , ′′ , ′′ , … , ~
Operations
∗, +, −, %,/,++, --, …
∗, +, −, %,/, …
<, >, …
โครงสร้ างข้ อมูล (Data Structure)
• โครงสร้ างข้ อมูล คือการรวมกันของข้ อมูลเชิงเดี่ยวและข้ อมูลเชิง
ประกอบเข้ าด้ วยกันเป็ นกลุม่ พร้ อมกับการกาหนดความสัมพันธ์ ซึง่ รวม
ไปถึงวิธีการเพิ่มข้ อมูลใหม่ การนาข้ อมูลที่เก็บไว้ ออก การเดินสารวจ
ข้ อมูลที่เก็บไว้ และการค้ นหาข้ อมูล
• ประเภทของโครงสร้ างข้ อมูลแยกตามการจัดเก็บข้ อมูล
 แบบเชิงเส้ น (Linear)
 แบบไม่เป็ นเชิงเส้ น (Non Linear)
โครงสร้ างข้ อมูลแบบเชิงเส้ น
การจัดเก็บข้ อมูลเรี ยงต่อกันไปทีละตัวในแนวเดียวกัน ให้ ข้อมูล
ทังหมดเรี
้
ยงอยูใ่ นแนวเส้ นตรงเดียวกัน จากข้ อมูลตัวแรกไปถึงข้ อมูลตัว
สุดท้ าย หรื อก็คือ ข้ อมูลแต่ละตัวจะมีข้อมูลที่อยูถ่ ดั ไปเพียง 1 ตัวเท่านัน้
• อาร์ เรย์ (Array)
• สแตค (Stack)
• คิว (Queue)
• ลิงก์ลสิ ต์ (Linked List)
โครงสร้ างข้ อมูลแบบไม่ เชิงเส้ น
• โครงสร้ างข้ อมูลแบบนี ้จะไม่มีข้อจากัดในเรื่ องการนาข้ อมูลเข้ า-ออกจาก
โครงสร้ างข้ อมูล เนื่องจากข้ อมูลไม่ได้ เรี ยงต่อกันเป็ นแนวเดียวกัน ทาให้
สามารถนาข้ อมูลเข้ าและออกจากตาแหน่งใดๆก็ได้
– โครงสร้ างข้ อมูลที่ไม่มีลาดับของข้ อมูล ได้ แก่ เซต ตารางแฮช
– โครงสร้ างข้ อมูลที่มีลาดับของข้ อมูล ได้ แก่ ทรี กราฟ
ชนิดข้ อมูลนามธรรม (ADT : Abstract Data Type)
ADT ไม่ใช่โครงสร้ างข้ อมูล แต่เป็ นระดับแนวคิด ซึง่
เปรี ยบเสมือนกับภาษากลางที่ใช้ นิยามโครงสร้ างข้ อมูลโดยไม่ขึ ้นกับ
สถาปั ตยกรรมใดๆ การนิยามดังกล่าวมีวตั ถุประสงค์เพื่อถ่ายทอดและ
นาเสนอโครงสร้ างข้ อมูลให้ ผ้ อู ื่นเกิดความเข้ าใจตรงกัน ประกอบด้ วย 2
ส่วนที่สาคัญ คือ
 ส่วนที่นิยามโครงสร้ างข้ อมูล
 ส่วนนิยามฟั งก์ชนั่ ที่ใช้ จดั การกับโครงสร้ างข้ อมูล
ความสั มพันธ์ ของชนิดข้ อมูล Logical & Physical
การสร้ าง ADT
• Declaration of data
• Declaration of operations
• Encapsulation of data and operations
พอยน์ เตอร์ ทซี่ ่ อนการทางานอยู่ภายในโครงสร้ าง
ตัวอย่ างโครงสร้ างข้ อมูล Queue ADT
• ดูในเอกสารประกอบ (ไฟล์ประกอบ)
6. การวัดผลอัลกอริทึม
ขนาดของอินพุต (Input Size)
เวลาที่ใช้ ในการทางานเพื่อจัดเรี ยงชุดตัวเลข (Running Time)
10 ตัว
2 วินาที
100 ตัว
2.1 วินาที
1,000 ตัว
1 นาที
10,000 ตัว
15 นาที
T(n) = จานวนเวลาที่ใช้ ในการทางานเพื่อจัดเรี ยงชุดข้ อมูล n ตัว
T(n) = O(n)
กราฟเปรียบเทียบเวลาในการทางาน
Time (T) ms
6
Worst-case
5
Average-case ?
4
3
Best-case
Column1
2
1
0
A
B
C
D
Input (n)
E
F
G
คุณสมบัตขิ องอัลกอริทมึ ทีด่ ี
• อัลกอริทมึ ที่ดีต้องมีความถูกต้ อง (Correctness)
• อัลกอริทมึ ที่ดตี ้ องง่ายต่อการอ่าน (Readability)
• อัลกอริทมึ ที่ดตี ้ องสามารถปรับปรุงได้ ง่ายในอนาคต (Ease of
Modification)
• อัลกอริทมึ ที่ดีสามารถนากลับมาใช้ ใหม่ได้ (Reusability)
• อัลกอริทมึ ที่ดีต้องมีประสิทธิภาพ (Efficiency)
ปัจจัยที่ทาให้ อลั กอริทึมมีประสิ ทธิภาพ
•
•
•
•
เวลาที่ใช้ ในการทางาน (Running Time)
หน่วยความจาที่ใช้ งาน (Memory Requirement)
เวลาที่ใช้ ในการคอมไพล์โปรแกรม (Compile Time)
เวลาที่ใช้ ในการติดต่อสื่อสาร (Communication Time)
ปัจจัยส่ งเสริมอืน่ ๆ
•
•
•
•
•
•
ความเร็วของเครื่ องคอมพิวเตอร์
อัลกอริทมึ ที่ออกแบบเพื่อใช้ งานสาหรับงานนันๆ
้
ประสิทธิภาพของคอมไพเลอร์
มีชดุ คาสัง่ อะไรบ้ างที่สงั่ ให้ คอมพิวเตอร์ ทา
ขนาดของหน่วยความจาในคอมพิวเตอร์
ขนาดของอินพุตมีปริมาณมากน้ อยเพียงไร
7. ประสิ ทธิภาพของอัลกอริทึม
• ประสิทธิภาพของอัลกอริทมึ แทนด้ วยฟั งก์ชนั่
•
•
•
•
•
•
f(n) = efficiency
ลูปแบบเชิงเส้ น
ลูปแบบลอการิธมิค
ลูปแบบซ้ อน
ลูปแบบซ้ อนชนิดลอการิธมิคเชิงเส้ น
ลูปแบบซ้ อนชนิดกาลังสอง
ลูปแบบซ้ อนกาลังสองชนิดขึ ้นต่อกัน
ลูปแบบเชิงเส้ น (Linear Loops)
• เพิ่มค่าด้ วยการบวกหรื อลดค่าด้ วยการลบภายในลูปแบบคงที่
จนกระทัง่ ครบจานวนรอบ
for (i = 0; i < 1000; i++)
application code
• f(n) = n
for (i = 0; i < 1000; i += 2)
application code
• f(n) = n/2
ลูปแบบลอการิธมิค (Logarithmic Loops)
• เพิ่มค่าหรื อลดค่าภายในลูปสองเท่าตัวด้ วยการคูณ (เพิ่มค่าสองเท่า)
หรื อการหาร (ลดค่าสองเท่า)
Multiply Loops
Divide Loops
for (i = 1; i <= 1000; i *= 2)
application code
for (i = 1000; i >= 1; i /= 2)
application code
• multiply 2Iterations <= 1000
• divide 1000/2Iterations >= 1
• f(n) = [logn] หรื อ [log2n]
ลูปแบบซ้ อน (Nested Loops)
• ภายในลูปจะมีลปู ซ้ อนอีกลูปหนึง่
Iterations = outer loop iterations x inner loop iterations
• สามารถแบ่งออกเป็ น 3 รูปแบบย่อย
– Linear Logarithmic
– Quadratic
– Dependent Quadratic
ลูปแบบซ้ อนชนิดลอการิธมิคเชิงเส้ น
(Linear Logarithmic)
• ลูปชันในเพิ
้
่มค่าเป็ นสองเท่าด้ วยการคูณ ในขณะที่ลปู ชันนอกจะเป็
้
น
แบบเชิงเส้ นที่มีการเพิ่มค่าทีละหนึง่ ในลักษณะคงที่
for (i = 0; i < 10; i++)
for (j = 1; j <= 10; j *= 2)
application code
• 10log10
• f(n) = nlogn
ลูปแบบซ้ อนชนิดกาลังสอง (Quadratic)
• แต่ละลูปจะทาการเอ็กซีคิ ้วต์ในจานวนรอบที่เท่ากัน
for (i = 0; i < 10; i++)
for (j = 1; j < 10; j++)
application code
• f(n) = n2
ลูปแบบซ้ อนกาลังสองชนิดขึน้ ต่ อกัน
(Dependent Quadratic)
• จานวนรอบการทางานของลูปชันในจะขึ
้
้นอยูก่ บั ลูปชันนอก
้
for (i = 0; i < 10; i++)
for (j = 0; j < i; j++)
application code
• 1 + 2 + 3 + … + 9 + 10 = 55
•
+1
2
•  =
+1
[ ]
2
8. สั ญลักษณ์ บิ๊กโอ (Big-O Notation)
• อัตราการเติบโตของฟั งก์ชนั่ (Growth Rates) พิจารณาปั จจัย
ของขนาด
• Big-O มาจาก Order of Magnitude
• อัตราการเติบโตของฟั งก์ชนั่ จะนาไปใช้ พิจารณาความซับ
(Complexity) ของอัลกอริทมึ โดยหากจานวนข้ อมูล (n) มี
ปริมาณมากแล้ ว จะส่งผลต่อการเปลี่ยนแปลงด้ านเวลาของอัลกอริทมึ
นันอย่
้ างไร
ตารางแสดงความแตกต่ างของอัตราการเติบโต
ในแต่ ละฟังก์ ชั่น
O(f(n))
f(50)
f(100)
O(logn)
O(n)
O(nlogn)
O(n2)
5.64
50
282
2500
6.64
100
664
10,000
O(n3)
O(2n)
O(n!)
12,500
1.126 x 1015
3.0 x 1064
100,000
1.27 x 1030
9.3 x 10157
ซูโดโค้ ดการคานวณคะแนนเฉลีย่
1 set sum to zero
2 set i to zero
3 dowhile i < n
1 add 1 to i
2 add score(i) to sum
4 enddo
5 compute mean = sum / n
แนวทางในการหาบิ๊กโอ
• พิจารณาเพียงเทอมที่มีคา่ เลขยกกาลังมากที่สดุ (Highest
Exponent) เท่านัน้
• ตัดเทอมส่วนที่เป็ นค่าคงที่และตัวคูณออกไป
• บิก๊ โอไม่ได้ มีจดุ ประสงค์เพื่อวัดเวลาการทางาน
• บิก๊ โอจะใช้ อธิบายขอบเขตของฟั งก์ชนั่ การเติบโตทางเวลา
เกณฑ์ วดั ผลประสิ ทธิภาพของบิ๊กโอกับฟังก์ ชั่นต่ างๆ
Efficiency
Big-O
Logarithmic
O(logn)
Linear
O(n)
Linear Logarithmic O(n(logn))
Quadratic
O(n2)
Polynomial
Exponential
Factorial
O(nk)
O(cn)
O(n!)
Iterations
14
10,000
140,000
10,0002
Running Time
ระดับไมโครวินาที
ระดับวินาที
ระดับวินาที
ระดับนาที
10,000k
210,000
10,000!
ระดับชัว่ โมง
มากจนยากต่อการระบุได้ แน่ชดั
มากจนยากต่อการระบุได้ แน่ชดั
แนวทางในการวัดผลประสิ ทธิภาพ
•
•
•
•
ขนาดของอินพุต
ให้ ละเลยค่าคงที่ที่อยูใ่ นสภาพแวดล้ อมนัน้
สนใจเฉพาะกรณีเลวร้ ายสุดเท่านัน้ (Worst-case)
มองข้ ามขนาดของอินพุตที่มีจานวนน้ อยๆ
9. ตัวอย่ างการวิเคราะห์ บิ๊กโอ
• การบวกแมทริกซ์
– Quadratic Loop
– O(n2)
• การคูณแมทริกซ์
– Cubic Loop
– O(n3)
สรุปท้ ายบทที่ 2
• การคิดด้ วยหลักนามธรรม ทาให้ เราสามารถคิดวิธีการแก้ ไขปั ญหา
ด้ วยการตัดทอนสิง่ ที่ซบั ซ้ อนหรื อรายละเอียดปลีกย่อยทีไ่ ม่จาเป็ นออกไป
ทาให้ ทกุ สิง่ ในโลกแห่งความเป็ นจริงดูง่ายดายขึ ้นด้ วยการอธบายว่าสิง่
สิง่ นันท
้ าอะไร ไม่ต้องมุง่ เน้ นในรายละเอียดว่าต้ องทางานอย่างไร
• ตัวแทนในการนาเสนออัลกอริทมึ มีอยูห่ ลายประเภทด้ วยกัน เช่น ผัง
งาน หรื อซูโดโค้ ด แต่ซโู ดโค้ ดจัดเป็ นหนึง่ ในเครื่ องมือทีน่ ิยมใช้ ในการ
สร้ างอัลกอริทมึ มากกว่า โดยซูโดโค้ ดมีรูปแบบคล้ ายประโยค
ภาษาอังกฤษ มีรูปแบบประโยคที่เป็ นโครงสร้ างเพื่อใช้ อธิบาย
รายละเอียดการพัฒนาอัลกอริทมึ
สรุปท้ ายบทที่ 2
• อัลกอริทมึ คือขันตอนวิ
้
ธีที่ใช้ สาหรับแก้ ไขปั ญหาโดยสามารถสื่อ
ออกมาในรูปแบบของภาษาพูดหรื อภาษาธรรมชาติ
• การสร้ างประโยคคาสั่ง 3 รูปแบบ
• ข้ อมูลเชิงเดี่ยว ไม่สามารถแบ่งส่วนข้ อมูล
• ข้ อมูลประกอบ สามารถแตกออกเป็ นฟิ ลด์ยอ่ ยได้
• ชนิดของข้ อมูล ประกอบด้ วย 2 ส่วน คือ กลุม่ ของข้ อมูล และโอเปอ
เรชัน่
สรุปท้ ายบทที่ 2
• โครงสร้ างข้ อมูล คือการรวมกันของข้ อมูลเชิงเดี่ยวและเชิงประกอบ
เข้ าด้ วยกันเป็ นกลุม่ พร้ อมกับกาหนดความสัมพันธ์
• ชนิดข้ อมูลนามธรรม ประกอบไปด้ วยกลุม่ ประกาศข้ อมูลที่รวมกับตัว
ดาเนินการหรื อโอเปอเรชัน่ เข้ าด้ วยกันทาให้ เกิดเป็ นรูปร่างของโครงสร้ าง
• ประสิทธิภาพของอัลกอริทมึ ปกติโดยทัว่ ไปมักถูกกาหนดมาใน
รูปแบบของฟั งก์ชนั่ ด้ วยการพิจารณาจากจานวนของอิลิเมนต์ที่ถกู
โปรเซสและชนิดของลูปที่ใช้ งาน
สรุปท้ ายบทที่ 2
•
•
•
•
•
•
•
Logarithmic Loop คือ f(n) = logn
Linear Loop คือ f(n) = n
Linear Logarithmic Loop คือ f(n) = logn
Quadratic Loop คือ f(n) = n2
Dependent Quadratic Loop คือ f(n) = n(n+1)/2
Cubic Loop คือ f(n) = n3
ประสิทธิภาพของอัลกอริทมึ สามารถเขียนให้ อยูใ่ นรูปแบบอย่างง่าย
O(logn), O(n), O(n(logn)), O(n2), O(nk), O(cn), O(n!)
Any Questions ?

similar documents