อัลกอริทึม คือ กระบวนการแก้ไขปัญหาตามหลักเหตุและผลที่มีการอธิบายเป็นขั้นเป็นตอนอย่างชัดเจนโดยใช้ทักษะการแก้ปัญหาตามหลักการคิดอย่างมีวิจารณญาณ ตั้งแต่การวิเคราะห์ปัญหาจนไปถึงการวางแผนแก้ไขปัญหาเป็นข้อ ๆ ตามลำดับขั้นตอน
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 Notation คือระยะเวลาในการประมวลผลที่แย่ที่สุด (worst-case complexity) หรือ ใช้พื้นที่และทรัพยากรมากที่สุดในการ compile อัลกอริทึมใดๆ หรือที่เรียกกันว่า ความซับซ้อนของอัลกอริทึม (Algorithm Complexity) ซึ่งนำมาใช้วัดการวัดประสิทธิภาพของ Algorithm นั้นๆได้ว่าเหมาะสมหรือไม่
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