当前位置:网站首页>Part I - Chapter 1 Overview

Part I - Chapter 1 Overview

2020-11-08 17:48:04 Li Lihao

Data structure introduction

Three reasons to use data structures : efficiency 、 abstract 、 reusability
Introduction to the algorithm : efficiency 、 abstract 、 reusability
General method of algorithm design : Random method 、 Divide and conquer method 、 Dynamic programming 、 The law of greed 、 Approximate method

General method of algorithm design

Random method

Random methods rely on the statistical properties of random numbers . For example, an example of applying the stochastic method is Quick sort .

Divide and conquer method

Divide and conquer contains 3 A step : decompose 、 solve 、 Merge . An example of divide and conquer is Merge sort

Dynamic programming

Dynamic programming is similar to divide and conquer , All of them decompose the larger problem into subproblems, and finally merge the results .
The difference , In dynamic planning , The way the problem is handled is related to the relationship between the subproblems . In divide and conquer , Each subproblem is independent .
therefore , In divide and conquer, you can use recursion ( The first 3 Chapter ) The way to solve each sub problem , Then merge the results with the results of other subproblems .

The law of greed

The greedy method can always make the best choice at present when solving problems . let me put it another way , It's not about the overall optimum , And it's just a local optimal solution in a sense .

An example of a greedy approach is Huffman coding ( The first 14 Chapter ), It's a data compression algorithm .
The most important part of Huffman coding is to build a Huffman tree ( Also known as the optimal binary tree ).

  • (1) To build a Hoffman tree , From its leaf nodes, from the bottom up . Take each compressed symbol and the number of times they appear in the data ( frequency ) Save together as the root node of the binary tree .
  • (2) Next , Select two root nodes with the minimum frequency as the left and right subtree nodes , Construct a new binary tree , And the frequency value of the new binary tree root node is the sum of the frequency values of the left and right subtree nodes .
  • (3) Then repeat this step , Know to get the only tree , This is the final Hoffman tree .

The root node of the Huffman tree contains the total number of symbols in the data , Leaf nodes contain the original symbols and how often they appear .
Huffman coding is a greedy algorithm , Because every time it selects the most suitable two trees to merge .

Approximate method

The approximate method does not calculate the optimal solution , contrary , It only calculates “ Good enough. ” Solution . The approximate method is usually used to solve the problems that are expensive to calculate and unwilling to give up because of its value .

Salesman problem ( The first 16 Chapter ) It's a problem that is usually solved by approximation .

版权声明
本文为[Li Lihao]所创,转载请带上原文链接,感谢