当前位置:网站首页>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]所创,转载请带上原文链接,感谢
边栏推荐
- 学习记录并且简单分析
- 构建者模式(Builder pattern)
- TypeScript(1-2-2)
- Travel notes of Suzhou
- Your random IO hard disk
- How does the system response time and throughput change with the increase of concurrency pressure during performance pressure testing
- Xiaoqingtai officially set foot on the third day of no return
- net.sf.json . jsonobject's format processing of time stamp
- python开发qt程序读取图片的简单流程
- go语言参数传递到底是传值还是传引用?
猜你喜欢
Introduction to latex
Examples of unconventional aggregation
Chapter 5 programming
(O) Analysis of service manager (1) BinderInternal.getContextObject
c++ opencv4.3 sift匹配
On the concurrency of update operation
这几个C++的坑,一旦踩中了,加班是肯定避免不了了!
佛萨奇forsage以太坊智能合约是什么?以太坊全球滑落是怎么回事
浅谈,盘点历史上有哪些著名的电脑病毒,80%的人都不知道!
IT行业薪资一直遥遥领先!十年后的程序员,是否还是一个高薪职业?
随机推荐
Flink的sink实战之一:初探
聊聊Go代码覆盖率技术与最佳实践
Js中常见的内存泄漏场景
TypeScript(1-2-2)
Solution to the problem of offline connection between ADB and mobile phone
LiteOS-消息队列-实战
(O)ServiceManager分析(一)之BinderInternal.getContextObject
uni-app实战仿微信app开发
go语言参数传递到底是传值还是传引用?
Talk about go code coverage technology and best practices
微信小程序相关
这几个C++的坑,一旦踩中了,加班是肯定避免不了了!
LiteOS-消息队列
实验
机械硬盘随机IO慢的超乎你的想象
Framework - SPI four modes + general device driver implementation - source code
前后端分离跨域问题解决方案
net.sf.json.JSONObject对时间戳的格式化处理
Xiaoqingtai officially set foot on the third day of no return
Talking about, check the history of which famous computer viruses, 80% of the people do not know!