preface

Recently began to learn algorithm knowledge, only to record their own understanding of algorithm learning, but also to facilitate their future review

1. Why do we need to know orders of magnitude

When we want to accurately describe a set of data, we usually use specific data records, but when we want to understand a set of data, we often need to use vague descriptions, fuzzy understanding of quantity, order of magnitude

2. The order of magnitude

An order of magnitude is a scale or level of magnitude of quantity, each of which usually has a fixed ratio, such as 10,2,1000,1024,e(euler number), approximately equal to the transcendental number of 2.71828182846, the base of the natural logarithm).

In real life, we use 10 a lot, but in the algorithmic world, we probably use 2,1024 more

Note that the range of magnitude applications must be positive or natural! Although negative numbers can also be calculated as orders of magnitude, they have no practical significance. For example, the numbers -10 and -1000 are 100 times different in pure mathematics, but you can’t say they’re two orders of magnitude different.

3. For example

  • So for example,1.5 times 10 to the third is 1500 and let’s call that order of magnitude 3
  • The order volume of Taobao Double 11 last year was 870 million, so we say its order volume is 100 million
  • So alibaba has a market cap of 470 billion and Baidu has a market cap of 70 billion, so we would say that Alibaba is an order of magnitude larger than Baidu
  • Apple’s market cap recently crossed the trillion mark, so we’d say apple is on the order of a trillion
  • The refresh frequency of the display is 60Hz, which is equivalent to a refresh of 16.66ms. So when our front-end js calculation, the algorithm execution speed should be completed at the millisecond level as far as possible, so that there will be no lag when drawing web pages. So when you design the front-end framework, you can have an order of magnitude of planning for the rendering algorithm that you use

3. An algorithm is a mapping of inputs to outputs

Function sum(arr){return arr.reduce((a,b)=>a+b,0)} let sumNum = sum([1,2,3]); So arr is the input and sumNum is the output and in this case the input is an array and the output is a number

So in this case the input size is arr.length and the larger the input arr.length is, the longer sum(arr) will take to execute.

4. Objective perspective of algorithm design

  • Or the above example, taobao Tmall double tenth one orders is 870 million, due to the large display screen refresh the limit of time, the order of magnitude of data need to be finished in the millisecond time So, we design the taobao Tmall double tenth order processing algorithm, a data will need to input billion into the size of the data in the millisecond time calculated

  • Currently, the official data of Zhihu users is 180 million (the growth rate of customers is a slow process, and the corresponding algorithm has a long life cycle). Their internal user portrait drawing requirement is once an hour, so when they design the user portrait algorithm, Will need to meet the level 1 billion input size (in general, the algorithm input the size of the order of magnitude larger than an order of magnitude estimates need to be addressed basic can satisfy the demand for an order of magnitude) made within the hour level (the actual algorithm is not such, of course, if the program execution time is this slow, so you don’t have to do other CPU has been in processing this data calculation))

  • When designing the front-end framework, a complex page usually has only a few hundred DOM nodes, and most of them do not exceed 10,000 data nodes. The REACT DOM-Diff algorithm must meet the requirement of dom node comparison at the level of 100,000, which can be completed in ms level time. In this way, the page will not lag when redrawing the page

section

  • Understanding the concept of order of magnitude can help us to have a better control of programming
  • Knowledge is limited, also only according to the recent learning of things part of the summary, where there is not correct place welcome to point out.

digression

As a programmer, there may be a lot of times, some algorithm knowledge in the work may not be used for a lifetime, but this is not the reason we do not learn him, algorithms and data structures are technologies with a long half-life, learning him will let you go further in the path of programming.

In particular, non-computer majors from the students, understand some basic knowledge of the computer, can let us become the road to go further.

If this article has helped you at all, please give it a thumbs up. thank you