Posted by: algo64 | 2010/06/29

Asymptotic Notation

   สัญลักษณ์ Asymptotic คือ ฟังก์ชันของเวลาที่ใช้ในการประมวลผลอัลกอริทึมหนึ่งๆ โดยพิจารณาค่าเมื่ออัลกอริทึมนั้นมีปริมาณข้อมูลมากๆ โดยสมมติให้ปริมาณข้อมูลมีขนาดอนันต์ (Infinity)  แล้วพิจารณาว่าเวลาที่ใช้ในการประมวลผลมีขอบเขตแนวโน้มการเติบโตทางเวลา (Growth in Run-Time) เป็นอย่างไร  ซึ่งเราจะเขียนออกมาให้อยู่ในรูปของฟังก์ชันทางคณิตศาสตร์

ประโยชน์ที่สำคัญของ Asymptotic

  1. เพื่อใช้ทำนายเวลาที่ต้องใช้ในการประมวลผล (Run-Time) ของอัลกอริทึมนั้นๆ โดยประมาณอย่างคร่าวๆ ได้ ณ ปริมาณข้อมูลต่างๆ
  2. ใช้ในการเปรียบเทียบประสิทธิภาพของอัลกอริทึมที่มีวัตถุประสงค์ในการทำงานชิ้นเดียวกัน แต่มีวิธีการแตกต่างกัน

ชนิดของฟังก์ชันต่างๆ
   ค่าของสัญลักษณ์ Asymptotic จะเขียนออกมาในลักษณะเป็นค่าฟังก์ชันทางคณิตศาสตร์ เพื่ออธิบายพฤติกรรมการเติบโตทางเวลาของอัลกอริทึม เมื่อปริมาณข้อมูลมีขนาดเปลี่ยนแปลงไป ซึ่งชนิดของค่าฟังก์ชันก็มีอยู่หลายชนิด และแต่ละชนิดก็จะมีชื่อที่เรียกแตกต่างกันออกไป เช่น

ฟังก์ชัน (Function) ชื่อ
c ค่าคงที่ (Constant)
\log N Logarithmic
\log^2 N Log-Squared
\sqrt N
N Linear
N \log N Linear-Logarithmic
N^2 Quadratic
N^3 Cubic
N^k Polynomial
2^N, c^N Exponential
N! Factorial

ถ้าเราเรียงตามค่าของฟังก์ชันต่างๆ จากน้อยไปมาก จะได้ตามตารางด้านล่าง

c < \log N < \log^2 N < \sqrt N < N < N \log N
< N^2 < N^3 < \ldots < N^k < 2^N < N!

   แต่ในทางกลับกัน หากต้องการวัดประสิทธิภาพว่าอัลกอริทึมไหนดี หรือไม่ดีนั้น ต้องเปรียบเทียบที่อัตราการเติบโตของฟังก์ชัน โดยการนำค่าฟังก์ชันของอัลกอริทึมมาเปรียบเทียบกัน แล้วถ้าค่าของฟังก์ชันที่ได้ออกมามีค่าน้อย หมายถึง อัลกอริทึมนั้นมีประสิทธิภาพดี ,แต่ถ้าค่าออกมามาก หมายถึง อัลกอริทึมนั้นไม่มีประสิทธิภาพ ดังตารางด้านล่าง

c > \log N > \log^2 N > \sqrt N > N > N \log N
> N^2 > N^3 > \ldots > N^k > 2^N > N!

   ในทางการวิเคราะห์อัลกอริทึม เราจะมีสัญลักษณ์ Asymptotic เป็นตัวชี้วัดอัตราการเติบโตของฟังก์ชัน

สัญลักษณ์ Asymptotic
มีด้วยกันทั้งสิ้น 5 สัญลักษณ์ คือ
   1. Big-Oh \rm O
   2. Little-Oh \rm o
   3. Big-Omega \Omega
   4. Little-Omega \omega
   5. Theta \Theta


Responses

  1. โอวว บังเอิญผ่านมา เป็นบทความที่ดีมากจ๊ะ โตโร่ สู้ๆๆ เผื่อเพื่อน ๆ ด้วย คิคิ

  2. ฟร้าววว โต่โร่ ….


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: