当前位置:网站首页>Part I - Chapter 1 Overview
Part I - Chapter 1 Overview
2020-11-08 17:48:00 【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]所创,转载请带上原文链接,感谢
边栏推荐
- Build simple business monitoring Kanban based on Alibaba cloud log service
- Flink系列(0)——准备篇(流处理基础)
- 不是程序员,代码也不能太丑!python官方书写规范:任何人都该了解的 pep8
- net.sf.json . jsonobject's format processing of time stamp
- 我用 Python 找出了删除我微信的所有人并将他们自动化删除了
- Express框架
- .NET 大数据量并发解决方案
- Use markdown
- Your random IO hard disk
- [elastic search technology sharing] - ten pictures to show you the principle of ES! Understand why to say: ES is quasi real time!
猜你喜欢
Not a programmer, code can't be too ugly! The official writing standard of Python: pep8 everyone should know
Express框架
[elastic search technology sharing] - ten pictures to show you the principle of ES! Understand why to say: ES is quasi real time!
One minute comprehensive understanding of forsage smart contract global shared Ethereum matrix plan
VirtualBox install centos7
[开源] .Net 使用 ORM 访问 华为GaussDB数据库
Introduction to latex
MongoDB数据库
Liteos message queuing
Dynamic ReLU:微软推出提点神器,可能是最好的ReLU改进 | ECCV 2020
随机推荐
接口测试用例思路总结
Dynamic relu: Microsoft's refreshing device may be the best relu improvement | ECCV 2020
Interesting article sharing: what is the difference between C language and C + +, C?
聊聊Go代码覆盖率技术与最佳实践
Chapter 5 programming
Summary of interface test case ideas
. net large data concurrency solution
Opencv solves the problem of ippicv download failure_ 2019_ lnx_ intel64_ general_ 20180723.tgz offline Download
experiment
Elasticsearch 学习一(基础入门).
Recurrence of Apache kylin Remote Code Execution Vulnerability (cve-2020-1956)
Awk implements SQL like join operation
Use markdown
Gopherchina 2020 Conference
框架-SPI四种模式+通用设备驱动实现-源码
我用 Python 找出了删除我微信的所有人并将他们自动化删除了
net.sf.json.JSONObject对时间戳的格式化处理
MongoDB数据库
API生命周期的5个阶段
I used Python to find out all the people who deleted my wechat and deleted them automatically