Talking Algorithm: The hidden secret of nature in the divide-and-conquer algorithm
Tags: algorithms
Published: 2022-10-18 06:57:01

## Introduction

> "The empire, long divided, must unite; long united, must divide. " -- *The Romance of the Three Kingdoms*

It is hard to deny the importance of **algorithms** in our modern IT industry. A well designed algorithm can run software programs with the minimal resources in the most efficient way. Therefore, algorithms are important, so that IT companies set high standards in the hiring process. Think about the algorithm tests in the technical interviews. Many people might feel that algorithms are quite distant from us, but I think its efficiency enhancement comes naturally, as the reason behind can be found in nature.

## From a snowflake

![snowflake](https://codao.crawlab.cn/images/2022-10-18-032607.jpg)

As we all know, a snowflake is beautiful, because of not only its shining appearing, but also the shape. It looks like a polished hexagon, and each branch is a snowflake-like sub-hexagon. The term for this structure with recursive self similarity is **Fractal**. Fractals are so common in nature, such as tree roots and tree leaf branches, pulmonary capillaries, natural coastal lines, or even broken glasses. 

So, why? What is the reason that fractals are so common in nature? Is it the design from Gods, or some **fundamental mathematical laws** behind it? Academic researchers believe in the latter. According the thermodynamics, snowflakes are formed when water vapor encounters an abrupt drop in temperature; according to fluid mechanics, the tree-like structure of pulmonary capillaries would allow the oxygen to be absorbed by red blood cells. In conclusion, **fractals exist for efficiencies**.

## Divide-and-conquer algorithm

Now let's go back to the algorithm. For those who are familiar with algorithms should have known the techniques using the divide-and-conquer methodology. Its fast speed comes from the process where a large piece is recursively divided into the most granular parts and then merged back, or the self-similar recursion. It is just like the fractal theory. Another example of fractal principles is the balanced tree (B-tree) database index, which transform unstructured data layer-by-layer into a tree-like structure, and ultimately make database querying much faster. The process of optimizing B-tree indexes is identical to that of optimizing the querying efficiency. The math expression *LogN* you often see in the complexity analysis, comes from the sum of arithmetic sequence in fractals. You can try deriving the equations through apply your mathematical knowledge from middle school.

## Is the world a fractal?

The fractal theory is a new scientific research area, and many scientists associate it with **the theory of complex systems**. Many complex systems are formed from some simple matters or laws. For example, ant colonies are like intelligent living individuals who can do loads of smart things, but only replying on very little information hormones. Life is made of cells, and cells come from DNAs, and DNAs are formed by micro particles including molecules, protons, and neutrons. **Everything in the world is made up by these physical models**. Just like the English poet put it, "To see a World in a Grain of Sand, And a Heaven in a Wild Flower". 

Although the fractal theory explains most of the formation in nature, it is still imperfect. As we are amazed by the powerfulness of the fractal theory, we should realize that it is not ideal, and we should explore as we see.