Skip to content

Algorithms and Code complexity that Devs should know by Tapat Toungsakul

Notifications You must be signed in to change notification settings

Txpxt-xuto/Algorithm-Complexity

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

53 Commits
 
 

Repository files navigation

Algorithm 🤖

อัลกอริทึม คือ กระบวนการแก้ไขปัญหาตามหลักเหตุและผลที่มีการอธิบายเป็นขั้นเป็นตอนอย่างชัดเจนโดยใช้ทักษะการแก้ปัญหาตามหลักการคิดอย่างมีวิจารณญาณ ตั้งแต่การวิเคราะห์ปัญหาจนไปถึงการวางแผนแก้ไขปัญหาเป็นข้อ ๆ ตามลำดับขั้นตอน

Algorithms ที่สาย problem solving ทุกคนควรรู้ by Tapat Toungsakul

1.Sorting Algorithms :

Bubble Sort
Insertion Sort
Selection Sort
Merge Sort
Quick Sort
Heap Sort

2.Searching Algorithms :

Linear Search
Binary Search
Depth-First Search (DFS)
Breadth-First Search (BFS)

3.Graph Algorithms :

Dijkstra's Algorithm
Bellman-Ford Algorithm
Kruskal's Algorithm
Prim's Algorithm

4.Dynamic Programming :

Fibonacci Sequence using Dynamic Programming
Longest Common Subsequence (LCS)
Knapsack Problem
Shortest Path in a Graph

5.Tree Algorithms :

Depth-First Traversal of a Tree
Breadth-First Traversal of a Tree
Binary Search Tree (BST) Operations

6.String Algorithms :

String Matching Algorithms
Longest Common Substring

7.Sorting and Searching on Data Structures:

Binary Search on Arrays and Trees
Hashing and Hash Tables

8.Divide and Conquer Algorithms:

Closest Pair of Points
Matrix Multiplication

9.Greedy Algorithms :

Huffman Coding
Kruskal's Algorithm

10.Backtracking Algorithms :

N-Queens Problem
Sudoku Solver

11.Mathematical Algorithms:

Euclidean Algorithm for Greatest Common Divisor (GCD)
Sieve of Eratosthenes for Prime Numbers

12.Machine Learning Algorithms:

Linear Regression
k-Nearest Neighbors (kNN)
Decision Trees
k-Means Clustering

Big O คืออะไร

Big O หรือ Big O Notation คือระยะเวลาในการประมวลผลที่แย่ที่สุด (worst-case complexity) หรือ ใช้พื้นที่และทรัพยากรมากที่สุดในการ compile อัลกอริทึมใดๆ หรือที่เรียกกันว่า ความซับซ้อนของอัลกอริทึม (Algorithm Complexity) ซึ่งนำมาใช้วัดการวัดประสิทธิภาพของ Algorithm นั้นๆได้ว่าเหมาะสมหรือไม่


รูปภาพโดย https://www.bigocheatsheet.com/

ประเภทของ Big O

O(1) - Constant Time : เป็น Big O ที่ใช้ทรัพยากรน้อยที่สุด โดยการทำงานจะเป็นลักษณะคงที่ แม้ Input จะมากหรือน้อย เช่น Arithmetic operations


O(log n) - Logarithmic Time : การทำงานของอัลกอริทึมนี้จะลดจำนวนลูปครึ่งนึงทุกครั้งที่มีการทำงานสำเร็จ เช่น Binary Search


O(n) - Linear Time : การทำงานของอัลกอริทึมนี้จะทำงานตามจำนวน Input ถ้ารับมาก ก็ทำมาก รับน้อย ทำน้อย เช่น loop, Finding min/max


O(n log n) - Linearithmic Time : การทำงานแบบซ้อนลูปที่ตัดข้อมูลที่ไม่ได้ใช้งานออกทีละครึ่ง เช่น merge sort, quick sort, LIS


O(n^2) - Quadratic Time : การทำงานแบบซ้อนลูปที่ไม่ได้ตัดข้อมูล เช่น bubble sort, selection sort, LCS


O(2^n) - Exponential Time : การทำงานแบบคำนวณทุกรูปแบบ เช่น Finding the exact solution of Traveling salesman problem


O(n!) - Factorial Time : เป็น Big O ที่ใช้เวลา พื้นที่และทรัพยากรมากที่สุด เช่น Permutation


About

Algorithms and Code complexity that Devs should know by Tapat Toungsakul

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published