Posted by: algo64 | 2010/07/02

สัญลักษณ์ Asymptotic แต่ละชนิด

ถ้าเราจะนิยามสัญลักษณ์ Asymptotic แต่ละชนิด จะได้ดังนี้ คือ

  1. Big-Oh (O)
    O(g(n)) = \{ f(n) | f(n) \preceq g(n) \}
    ผลลัพธ์ที่ได้คือ เซ็ตของฟังก์ชันที่มีค่าอัตราการเติบโตต่ำกว่าหรือเท่ากับ g(n)

    เช่น ถ้ากำหนดให้ O(g(n)) = N^2

    ดังนั้น เซ็ตของคำตอบก็คือ \{ N, \log N, N \log N, \frac{N^2}{2}, \dots \}
  2. Little-Oh (o)
    O(g(n)) = \{ f(n) | f(n) \prec g(n) \}
    ผลลัพธ์ที่ได้จะเหมือนกับ Big-Oh แต่จะต่างกันนิดเดียวคือ ฟังก์ชัน f(n) ต้องมีอัตราการเติบโตต่ำกว่าฟังก์ชัน g(n)
    เช่น กำหนดให้ o(g(n)) = N^2
    ดังนั้น \frac{N^2}{2} จะไม่อยู่ในเซ็ตของคำตอบ เพราะมีอัตราการเติบโตเท่ากัน
  3. Big-Omega (\Omega)
    O(g(n)) = \{ f(n) | f(n) \succeq g(n) \}

    ผลลัพธ์ที่ได้คือ เซ็ตของฟังก์ชันที่มีค่าอัตราการเติบโตสูงกว่าหรือเท่ากับ g(n)
  4. Little-Omega(\omega)

    O(g(n)) = \{ f(n) | f(n) \succ g(n) \}

    ผลลัพธ์ที่ได้คือ เซ็ตของฟังก์ชันที่มีค่าอัตราการเติบโตสูงกว่า g(n)
  5. Theta(\Theta)
    O(g(n)) = \{ f(n) | f(n) \succeq \Omega(g(n)) \ \cap\  f(n) \preceq O(g(n)) \}

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: