> For the complete documentation index, see [llms.txt](https://www.saladpuk.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://www.saladpuk.com/beginner-1/data-structure-and-algorithm/big-o.md).

# Algorithm Big-O

จากบทความก่อนหน้าหลายคนน่าจะเริ่มเห็นความสำคัญของ Algorithm กันเพิ่มขึ้นละ ดังนั้นในบทความนี้ **ดช.แมวน้ำ** จะยกตัวอย่าง **การบวกเลข** ให้เห็นว่ามันแตกประเด็นไปถึงเรื่องการทำ **Security** ได้ยังงุยกัน (ขอแบ่งเป็น 2 บทนะ)

{% hint style="success" %}
**แนะนำให้อ่าน**\
บทความนี้เป็นส่วนหนึ่งของบทความ [**👶 Data Structure & Algorithm**](https://www.saladpuk.com/beginner-1/data-structure-and-algorithm) หากเพื่อนๆสนใจอยากรู้ว่าเจ้า Algorithm มันคืออะไร คุ้มค่าเวลาชีวิตที่เราจะอ่านไหม  ก็สามารถศึกษาได้จากบทความหลักได้เลยโดยการคลิกที่ชื่อบทความสีฟ้าๆนั่นแหละ
{% endhint %}

## 🥱 บวกเลข ป.3

สมมุติว่าแมวน้ำเขียนโค้ดตามด้านล่าง

```javascript
a = 0.2
b = 0.1
c = a + b
```

คำถามคือ ตัวแปร `c` มีค่าเป็นเท่าหร่ายยยยจ๊ะ ?

เชื่อไหมว่าเพียงคำถามสุดแสนจะง่ายที่ดูปุ๊ปก็ได้คำตอบเลย แต่ถ้าเราเอาไปลองเขียนดูจริงๆเราจะพบว่าคำตอบคือ

> **ผลลัพท์**\
> 0.30000000000000004 😳\
> เฮ้ยมันเกิดบร้าไรขึ้นทำไมมันถึงมีติ่งแปลกๆงอกขึ้นมาดั๊ยยยยย!! ลองไปเขียนดูนะ C#, Java, Javascript, Python บลาๆ 🤪

สาเหตุที่คอมมันได้ผลลัพท์แบบนั้นออกมาก็เพราะว่า **Data Structure & Algorithm** ของตัวเลขมันเป็นแบบนั้นยังไงล่ะ ซึ่งเราจะเห็นว่า **แค่เรื่องพื้นฐานแบบสุดๆ ก็ยังมีเรื่อง Data Structure & Algorithm รวมอยู่ด้วยเสมอ** ดังนั้นไม่ว่าเราจะเขียนโค้ดด๋อยอะไรก็ตามของพวกนี้ก็จะตามเราไปทุกที่ ซึ่งถ้าเราไม่เข้าใจมัน การออกแบบ การทำ performance tuning หรืออะไรก็ตามก็จะมีปัญหาโดยที่เราไม่รู้ตัวนั่นเอง

{% hint style="warning" %}
**ข้อควรระวัง**\
หลายคนพอเห็นว่ามันได้ตัวเลขเพี้ยนๆ ก็จะเบ้ปากแล้วบอกว่างั้นก็ใช้ **decimal** ไปเลยเด๊ปัญหาก็จบแล้ว ซึ่งแมวน้ำก็จะบอกว่า ใช่ครับมันแก้เรื่องตัวเลขเพี้ยนได้ แต่มันจำเป็นไหม? หรือมันเป็นแค่การซ่อนปัญหา?
{% endhint %}

{% hint style="info" %}
**เกร็ดความรู้ (ทศนิยม)**\
สาเหตุที่มันได้คำตอบเป็น 0.30000000000000004 ก็เพราะว่า **Data Structure** ของตัวเลขที่คอมมันเก็บนั้น มันอยู่ในรูปแบบของ **binary** (0/1) นั่นเอง และคอมมันทำงานกับตัวเลขที่เป็นทศนิยมไม่เก่ง เพราะมันจะเก็บค่าที่แท้จริงของทศนิยมไม่ได้ ดังนั้นมันจะเก็บเป็นค่าที่ใกล้เคียงที่สุด ดังนั้นเวลามันนำไปแสดงผลในบางทีมันจะมีปัญหาเรื่องการปัดเศษ ซึ่งเราเรียกปัญหาแบบนี้ว่า [**Round-off error**](https://en.wikipedia.org/wiki/Round-off_error) นั่นเองขอรับ
{% endhint %}

{% hint style="info" %}
**เกร็ดความรู้ (Bitcoin)**\
อย่างที่เกร็ดความรู้แรกบอกไปว่า **คอมทำงานกับทศนิยมไม่เก่ง** ยิ่งทำงานกับเลขทศนิยมมันจะยิ่งช้า ดังนั้นพวก **Bitcoin เลยไม่ทำงานกับทศนิยมตรงๆ แต่จะเก็บเป็นตัวเลขจำนวนเต็มแทน** (ตัวอย่างให้เห็นภาพสมมุตเขาจะเก็บ 1 บาท 25 สตางค์ ก็จะเก็บเป็น 12500) แล้วเมื่อไหร่ที่จะเอาไปแสดงผลก็ค่อยปัดตำแหน่งที่เป็นทศนิยมไปแสดงผลนั่นเอง (ตามตัวอย่างคือ 4 digits สุดท้าย 12500 ก็จะเป็น 1.25 บาท)
{% endhint %}

จากที่เกริ่นมา Data Structure นั้นส่งผลกับการทำงานของซอฟต์แวร์เราโดยตรง ดังนั้นเราเลยจำเป็นต้องรู้ว่า Data Structure แต่ละรูปแบบมันมีจุดเด่นจุดด้อยยังไง เพื่อที่จะเลือกใช้มันได้ถูกตัว

เช่น เราจะทำงานกับ collection แล้วเราจะเลือก Data Structure ตัวไหนล่ะ Array ดีไหม หรือ List ดีหว่า Stack ก็น่าสนใจนะ บลาๆ ซึ่งแน่นอนว่า **Data Structure แต่ละตัวมีจุดเด่นที่ต่างกัน** ซึ่งเราจะเลือกใช้ตัวไหนให้ดูง่ายๆจาก 2 อย่างคือ

**1.รูปแบบของปัญหา** - เช่น ถ้าต้องประมวลผลข้อมูลแบบ FIFO (ทำตามลำดับ) หรือมาแบบ LIFO (มาหลังทำก่อน) การเลือก Data Type ผิดก็ทำให้เราเขียนโค้ดยากขึ้นเยอะ แถมยังช้าอีก

**2.รูปแบบของข้อมูล** - เช่น ถ้าข้อมูลถูกเรียงลำดับมา หรือ ข้อมูลไม่มีลำดับเลย ก็จะมีผลเช่นกัน

 😒 แล้วเราจะรู้ได้ยังไงว่าเมื่อไหร่ควระเลือก Algorithm ตัวไหน? หรือใช้ Data Structure อันไหนดีกว่ากัน? . . . ไม่ต้องเสียเวลาคิดให้มากความ ไปรู้จักกับ **Algorithm Complexity** ในหัวข้อถัดไปกันเบย

## 🤔 Algorithm ช้า/เร็ว ดูไง ?

### 🔥 Algorithms Complexity

สำหรับเพื่อนๆที่เข้าใจ **Big-O** อยู่แล้วก็ให้อ่านข้ามไปอ่านบทความถัดไปได้เลยที่บทความนี้ [👽 **Algorithm P & NP**](https://www.saladpuk.com/beginner-1/data-structure-and-algorithm/p-and-np) ส่วนใครที่อยากทบทวนก็อ่านต่อตรงนี้ละกัน โดยแมวน้ำขออธิบายโดยใช้คำถามง่ายๆด้านล่าง

> **ถ้าเราจะคูณเลข 2 ตัว เรามีวิธีคิดแบบไหนได้บ้าง ?**\
> ตัวอย่าง 12 x 12 เราคิดยังไงให้ได้ผลลัพท์เป็น 144

จากโจทย์ด้านบน เราก็อาจจะคิดง่ายๆได้ 2 วิธีตามด้านล่าง (จะหลายวิธีก็ได้แต่ขอตัดมาแค่นี้พอ)

**1.บวกซ้ำ** - โดยเราก็จะนำ 12 มาบวกกัน 12 รอบ (12+12+12+....) ซึ่งก็จะได้ผลลัพท์เป็น 144 นั่นเอง\
**2.คูณทีละตำแหน่ง** - โดยเราก็จะนำ 12 x 2 ก่อน แล้วค่อยเอาไปบวกกับ 12 x 10 ซึ่งก็ได้ผลลัพท์เป็น 144 เช่นกัน

จากทั้ง 2 วิธี (Algorithm) ที่ว่ามา ถ้าเราลองทำตามดูเราจะพบว่า **จำนวนครั้งที่ทำในแต่ละวิธีมันไม่เท่ากัน**

| วิธี (Algorithm)   | จำนวนครั้งที่ทำ        | ตัวอย่าง                               |
| ------------------ | ---------------------- | -------------------------------------- |
| **บวกซ้ำ**         | ขึ้นอยู่กับตัวคูณ      | 15 x 5,000 ต้องทำซ้ำ 5,000 ครั้ง       |
| **คูณทีละตำแหน่ง** | (หลักของตัวคูณ x 2) -1 | 15 x 5,000 ต้องทำซ้ำ (4x2)-1 = 7 ครั้ง |

จากตารางด้านบนจะเห็นว่า **วิธีบวกซ้ำ** มันมีจำนวนครั้งที่ใช้เยอะกว่า **วิธีคูณทีละตำแหน่ง** ยิ่งตัวคูณเยอะเท่าไหร่ จำนวนครั้งที่ทำก็จะยิ่งเยอะตาม **โดยในทางคอมพิวเตอร์ยิ่งจำนวณครั้งที่ทำสูงเท่าไหร่มันยิ่งช้า** ดังนั้นเวลาที่เราจะเลือก Algorithm ให้เลือกจากจำนวนครั้งที่มันใช้ ซึ่งเราเรียกเจ้าตัวนี้ว่า **`Algorithms Complexity`** ซึ่งโดยปรกติเราจะเขียนมันด้วยสูตรที่เราเรียกมันว่า **`Big-O`** เพื่อเอาไว้บอกว่า Algorithm นั้นๆเร็วหรือช้ายังไง จากรูปด้านล่างจะเป็น Big-O ของแต่ละ Data Structure ของพวก Collection เพื่อช่วยในการตัดสินใจ เช่นจะใช้ Array หรือจะใช้ Stack ดี เราก็สามารถดูตารางด้านล่างเปรียบเทียบได้

![https://www.bigocheatsheet.com](/files/-MDvyjD_5YalxbGufdQO)

![https://www.bigocheatsheet.com](/files/-MDw-1ae0I3d6QCDv0at)

จากที่แมวน้ำมโนมาทั้งหมด สรุปได้ง่ายๆคือ **Algorithm เร็วหรือช้า ไม่ได้ขึ้นอยู่กับ มันซับซ้อนหรือเปล่า** เพราะต่อให้เราพยายามศึกษาแล้วก็ยังไม่เข้าใจมันเลย แต่ถ้าค่า **Big-O ของมันน้อย มันจะทำงานได้เร็วกว่า Algorithm ประเภทเดียวกันที่มี Big-O เยอะๆ**นั่นเอง

### **🍖 ตัวอย่างเพิ่มเติม**

ยังจำเรื่องการหา [**ห.ร.ม. (หารร่วมมาก)**](https://en.wikipedia.org/wiki/Greatest_common_divisor) สมัยประถมกันได้ไหมเอ่ย? ซึ่งโดยปรกติที่เรียนมาเขาก็จะให้จับหารไปเรื่อยๆจนมันหารไม่ได้ แล้วเอาตัวที่หารไม่ได้ที่เหมือนกันไปคูณกันเพื่อได้ให้ผลลัพท์มาชิมิ ซึ่งนั่นก็เป็น 1 ใน Algorithm ที่สามารถทำได้ แต่ถ้าเราลองไปดู [**Euclid's algorithm**](https://en.wikipedia.org/wiki/Greatest_common_divisor#Euclid's_algorithm) เราก็จะพบวิธีการหาเจ้า ห.ร.ม ในอีกรูปแบบที่ลดขั้นตอนลงไปได้เยอะเลยนั่นเอง ลองดูจากรูปด้านล่างก็ได้

![](/files/-MDwZQdSeFHh01GCRWN-)

```csharp
public int GCD(int a, int b)
{
    var x = Math.Max(a, b);
    var y = Math.Min(a, b);
    
    while(y != 0)
    {
        var remain = x % y;
        x = y;
        y = remain;
    }
    
    return x;
}
```

## 🎯 บทสรุป (part 1)

ถึงตรงนี้ **ดช.แมวน้ำ** เชื่อว่าหลายคนน่าจะเข้าใจตรงกันละว่า Algorithm ช้าหรือเร็วขึ้นอยู่กับ **Big-O** หรือพูดอีกแบบคือ **ยิ่ง execute statements เยอะยิ่งช้า** และ **แต่ละ Data Structure มันเก่งคนละด้าน** ดังนั้นอย่าตะบี้ตะบันเอา Solution ที่เจอในเน็ทไปใช้กับงานที่ใช้จริง เพราะมันอาจจะไม่เข้ากับหน้างานเราก็ได้

{% hint style="danger" %}
**ข้อความระวัง**\
แมวน้ำเห็นหลายครั้งที่บรรดาโปรแกรมเมอร์จะชอบเข้าใจผิดว่า **ยิ่งโค้ดสั้นแสดงว่ามันยิ่งเร็ว** ซึ่งถ้าได้อ่านบทความนี้แล้วก็ขอให้หยุดความคิดนั้นไปได้เลย เพราะ **ความเร็วไม่ได้ขึ้นกับจำนวนบรรทัดของโค้ด มันขึ้นอยู่กับค่า Big-O เท่านั้น** และต่อให้โค้ดคุณจะยาวแค่ 1 บรรทัด แต่ถ้า Big-O ของมันโคตรเยอะแบบ O(n!) มันก็จะช้ากว่าโค้ดที่เขียน 1,000 บรรทัดแต่มี Big-O น้อยๆเช่น O(n)
{% endhint %}

{% hint style="success" %}
**แนะนำให้อ่าน**\
สำหรับเพื่อนๆที่สนใจอยากรู้ว่าสิ่งที่โปรแกรมเมอร์มักเข้าใจผิดมีไรบ้าง ก็ไปตามอ่านได้จากบทความนี้เบย [👶 สิ่งที่คนเขียนโค้ดมักเข้าใจผิด](https://www.saladpuk.com/basic/mist)
{% endhint %}

![](/files/-MDwlMDfalAiay4NEMKz)

เดี๋ยวเราลองไปดูบทความถัดไปของ Algorithm ว่ามันไปเกี่ยวข้องกับพวกที่ทำ Security ยังไงกันบ้างดีกั่วกับบทความนี้ [👽 **Algorithm P & NP**](https://www.saladpuk.com/beginner-1/data-structure-and-algorithm/p-and-np)