How to design an algorithm? Introduction to common algorithm paradigms

How to design an algorithm? The following article will analyze common algorithm paradigms for you. It has certain reference value. Friends in need can refer to it. I hope it will be helpful to everyone.

First clarify three concepts:

Algorithm:The process of solving problems step by step.

Paradigm:A model for thinking about problems.

Algorithmic paradigm:A general approach to building efficient solutions to problems.

This article discusses some commonly used algorithm paradigms, such as

• Divide and Conquer Algorithm
• Dynamic Programming
• Greedy Algorithm
• Backtracking Algorithm

Divide and Conquer Method

Among the sorting algorithms, the common point between the two algorithms, merge and quick sort, is the divide and conquer algorithm.

Divide and Conqueris a common algorithm design. Its idea is to decompose the problem into smaller sub-problems that are similar to the original problem. Subproblems are usually solved recursively and the solutions to the subproblems are combined to solve the original problem.

The logic of the divide-and-conquer method can be divided into three steps:

1. Divide the original problem into smaller sub-problems.
2. Solve the sub-problem recursively and return the solution to the sub-problem after the solution is completed.
3. Merge solutions to subproblems into solutions to the original problem.

Example of divide-and-conquer method: binary search

The following is a binary search implemented using divide-and-conquer.

function binarySearchRecursive(array, value, low, high) { if (low <= high) { const mid = Math.floor((low + high) / 2); const element = array[mid]; if (element < value) { return binarySearchRecursive(array, value, mid + 1, high); } else if (element > value) { return binarySearchRecursive(array, value, low, mid - 1); } else { return mid; } } return null; } export function binarySearch(array, value) { const sortedArray = quickSort(array); const low = 0; const high = sortedArray.length - 1; return binarySearchRecursive(array, value, low, high); }

Please note that thebinarySearchfunction above is for others to call, whilebinarySearchRecursiveis where the divide and conquer method is implemented.

Dynamic programming method

Dynamic programmingis an optimization technique used to solve complex problems by decomposing them into smaller sub-problems. It looks a lot like divide and conquer, but instead of decomposing the problem into independent sub-problems and then combining them together, dynamic programming only decomposes the problem intoindependentsub-problems.

The algorithm logic is divided into three steps:

1. Define sub-problems.
2. Repeat to solve sub-problems.
3. Identify and resolve basic issues.

Dynamic Programming Case: Minimum Coin Change Problem

This is a common interview question called the coin change problem. The coin change problem is a way of finding how many specific numbers of coins can be used to make change, given the amount of change. The minimum coin change problem is simply finding the minimum number of coins required to use a given denomination of money. For example, if you need change for 37 cents, you would use 1 2 cent, 1 5 cent, 1 1 dime, and 1 2 cent.

function minCoinChange(coins, amount) { const cache = []; const makeChange = (value) => { if (!value) { return []; } if (cache[value]) { return cache[value]; } let min = []; let newMin; let newAmount; for (let i = 0; i < coins.length; i++) { const coin = coins[i]; newAmount = value - coin; if (newAmount >= 0) { newMin = makeChange(newAmount); } if (newAmount >= 0 && (newMin.length < min.length - 1 || !min.length) && (newMin.length || !newAmount)) { min = [coin].concat(newMin); } } return (cache[value] = min); } return makeChange(amount); }

In the above code, the parametercoinsrepresents the denomination ([1, 2, 5, 10, 20, 50] in RMB). In order to prevent double calculation, acacheis used. ThemakeChangefunction is implemented recursively, it is an internal function and has access tocache.

console.log(minCoinChange([1, 2, 5 10, 20], 37)); // => [2, 5, 10, 20] console.log(minCoinChange([1, 3, 4], 6)) // => [3, 3]

Greedy Algorithm

Greedy Algorithmis related to the current optimal solution and tries to find a global optimal solution. Unlike dynamic programming, it does not consider the overall situation. Greedy algorithms tend to be simple and intuitive, but may not be the overall optimal solution.

Greedy Algorithm Case: Minimum Coin Change Problem

The coin problem solved by dynamic programming above can also be solved by the greedy algorithm. Whether this solution is optimal or not depends on the denomination used.

function minCoinChange(coins, amount) { const change = []; let total = 0; for (let i = coins.length; i>= 0; i--) { const coin = coins[i]; while (total + coin <= amount) { change.push(coin); total += coin; } } return change; }

It can be seen that the greedy algorithm is much simpler than the dynamic programming solution. Let's take a look at the same solution case to understand the difference between the two:

console.log(minCoinChange([1, 2, 5 10, 20], 37)); // => [2, 5, 10, 20] console.log(minCoinChange([1, 3, 4], 6)) // => [4, 1, 1]

The greedy algorithm gives the optimal solution to the first problem, but the second one is not the optimal solution (it should be[3,3]).

The greedy algorithm is simpler and faster than the dynamic programming algorithm, but the solution obtained may not be the optimal solution.

Backtracking algorithm

Backtracking algorithmis great for finding and building solutions step by step.

1. Try to solve the problem one way.
2. If it doesn't work, backtrack and repeat step 1 until you find a suitable solution.

For the backtracking algorithm, I will write another article to introduce more complex algorithms. I haven't figured out what to write yet. Maybe it's to write a program for solving Sudoku. If you are interested in this, please follow my official account!

Algorithms are never-ending. I hope this article can help you understand some common algorithm paradigms.

Related free learning recommendations:js video tutorial

The above is the detailed content of How to design an algorithm? Introduction to common algorithm paradigms. For more information, please follow other related articles on the PHP Chinese website!