ALGORITHM

COMPUTATION

CRYPTOGRAPHY

FRONTEND

GAME-THEORY

INVESTMENT

JS&TS

LINUX

MATHEMATICS

NODE

PROJECT-PRACTICE

REACT

THOUGHTS

古文整理

文史哲艺


Kamil Galeev presents a fascinating perspective. He observes that, similar to how certain gangs in Mexico control the avocado industry, criminal organizations worldwide tend to dominate sectors like drugs, fruit, minerals, and even entertainment. However, he poses an intriguing question: have we ever seen gangs controlling high-tech industries? Galeev explains that this absence is due to the relative simplicity of power structures within gang organizations.

He suggests a trend in the relationship between gangs and various industries, where gangs prefer to venture into fields that are operationally simpler. For instance, if a gang were to enter the mechanical production sector, they would face two likely outcomes. One, they would be unable to adapt and ultimately fail, as the complexity of mechanical production exceeds their simple power structure's managerial capabilities. Alternatively, they would need to delegate authority to professionals, transforming from a gang into more of a business entity, with actual power swiftly shifting into the hands of knowledgeable individuals.

Galeev interprets this phenomenon as stemming from the simplicity in the operation of gang power. He likens this to the simplicity of totalitarian politics compared to democratic systems, which partly explains his lack of interest in analyzing totalitarian politics. In his view, gangs gravitate towards simpler industries because power is more directly and effectively exercised in these areas.

However, the situation becomes complicated when gangs attempt to infiltrate more complex industries. In such sectors, the dependence on knowledge and specialized skills becomes paramount. Galeev notes that this high dependency on knowledge poses a dilemma for gangs, as their simple power structures are ill-equipped to manage such complexity. Complex industries require professional management and technical expertise, areas where gangs typically lack proficiency.

This also raises a point for reflection about the adaptability of different organizational forms in society. Gangs succeed in industries like drugs and fruits because these sectors are relatively straightforward and can be operated through more basic methods. However, when faced with complex domains like high-tech industries, the simplistic modus operandi of gangs clearly falls short. In contrast, formal businesses and organizations are more likely to thrive in complex industries due to their focus on specialization, innovation, and efficient management.

Therefore, Galeev's insights not only offer an intriguing view into the activities of criminal organizations but also provoke deeper contemplation on organizational forms, power structures, and the management of complex industries. The evolution of society and the development of industries reveal different strengths and weaknesses in various organizational types, presenting a rich area for exploration in organizational studies and social sciences.


Galeev: Gangs excel in simple industries, struggle in complex sectors.

Why Can't the Underworld Manage High Technology?


Event handlers are fundamentally callback functions, wherein the calling privilege is relinquished to the event initiator, and the program responsible for the event is automatically invoked when the event occurs. Regarding the source of events, it depends on the perspective. From a process standpoint, a small portion of events is indeed obtained through polling, while the majority is processed through a message loop structure. A message loop typically monopolizes a thread and can be expressed in pseudocode as follows:

```pseudo
while (true) {
  if(GetEvent()) {
    ProcessEvent()
  }
  continue;
}
```

This represents a loop that retrieves an event and processes it. Handling events usually involves calling event handler functions. So, how are events obtained? Aside from polling, it is often accomplished with the assistance of the operating system. The operating system provides certain blocking calls, such as `select`, `epoll`, and Windows' `GetMessage`, `WaitForMultipleObjects`, etc. These blocking calls generally handle multiple signal sources, returning when any of them undergoes a change, allowing the simultaneous tracking of various inputs.

In addition to event loops, another design involves the operating system directly triggering specific callback functions. Typical examples include Linux's `signal`, `aio`, Windows' `SendMessageWithCallback`, etc. Such callbacks typically interrupt the ongoing system call immediately. This integration of callbacks with event loops involves setting flags during the callback process, checking these flags when the blocking concludes, thereby seamlessly incorporating these callbacks into the usual event loop.

Now, from the perspective of the operating system, the kernel can arbitrarily schedule user processes. When a user process makes a system call, transitioning to kernel mode, the kernel suspends the current process. Upon the occurrence of the corresponding event, the kernel then awakens the respective user process, allowing it to resume execution. Thus, the kernel essentially functions as an event callback system.

Delving deeper, where do the events in the kernel come from? A crucial mechanism is known as interrupts, which, in simple terms, are hardware-implemented signal handlers. CPUs typically execute instructions sequentially, with the kernel sequentially executing user programs. In instances where all user processes are suspended, the kernel executes an idle process, engaging in a loop executing low-power instructions. A notable exception is interrupts. CPUs possess interrupt pins, and a change in voltage on these pins immediately initiates the interrupt process. The hardware structure within the CPU promptly enters kernel mode, reads the interrupt vector table, and then jumps to the corresponding code based on the address in the table for execution.

Interrupt handling procedures usually begin by saving the context, querying information from hardware sharing the interrupt, saving it to specific data structures, resetting the interrupt, and then promptly returning to kernel mode. The kernel subsequently queries interrupt information and executes specialized handling procedures. These procedures ultimately restore the execution of user-space programs, and the cycle repeats.

In essence, this is a counterpart to signal handlers and event loops in user space. Apart from hardware interrupts, there are interrupts triggered internally by the CPU. A crucial example is the timer interrupt, and the handling process is identical. Some hardware employs timer interrupts for polling, such as USB. In summary, hardware notifies the kernel through interrupts, the kernel informs user processes (threads) through blocking calls and event handlers, and the user framework manages notifications, triggering event handlers.


This article explores the essence of event handlers as callback functions, relinquishing control to event initiators. Events are obtained through either polling or operating system-assisted methods like blocking calls. The operating system serves as an event callback system, handling interrupts, and integrating callbacks into event loops.

The Event-Listening Implementation


## Equals

```typescript
type Equals<T, U> = T extends U ? (U extends T ? true : false) : false;

type Type1 = { a: number; b: string };
type Type2 = { a: number; b: string };
type Type3 = { a: number; c: string };

type Test1 = Equals<Type1, Type2>; // true
type Test2 = Equals<Type1, Type3>; // false
```

## If

```typescript
type If<C extends boolean, T, F> = C extends true ? T : F;

type A = If<true, "a", "b">; // expected to be 'a'
type B = If<false, "a", "b">; // expected to be 'b'
```

## Includes

```typescript
type Includes<T extends any[], U> = {
  [K in T[number]]: true;
}[U] extends true
  ? true
  : false;

type MyType = Includes<["Kars", "Esidisi", "Wamuu", "Santana"], "Dio">;
// expected to be `false`
```

## Merge

```typescript
type Merge<T> = {
  [P in keyof T]: T[P];
};
```

## Diff

```typescript
type Diff<O, O1> = Merge<
  {
    [P in Exclude<keyof O, keyof O1>]: O[P];
  } & {
    [P in Exclude<keyof O1, keyof O>]: O1[P];
  }
>;
```

## Ranged Number

```typescript
type IsMore<A extends number, B extends number, L extends any[] = []> = A extends L["length"]
  ? false
  : B extends L["length"]
    ? true
    : IsMore<A, B, [...L, any]>;
type NumRange<Max, Min> = isMore<infer U, Min> extends true ? (isMore<Max, U> extends true ? U : never) : never;

type MyType = NumRange<1000, 9999>;
// Only number 1000-9999 can be accepted.
```

## Tuple To Union

```typescript
type TupleToUnion<T extends any[]> = T[number];

type Arr = ["1", "2", "3"];
const test: TupleToUnion<Arr>; // expected to be '1' | '2' | '3'
```

## String To Union

```typescript
type StringToUnion<T extends string> = T extends `${infer First}${infer Reset}` ? First | StringToUnion<Reset> : never;
type Test = "123";
type Result = StringToUnion<Test>; // expected to be "1" | "2" | "3"
```

## Length of String

```typescript
type LengthOfString<S extends string, T extends any[] = []> = S extends `${infer L}${infer R}`
  ? LengthOfString<R, [...T, L]>
  : T["length"];

type MyType = LengthOfString<"hello">; // 5
```


TypeScript Type-Exercises-3


## Spilt String into Chars

```ts
type Split<T extends string, U extends unknown[] = []> = T extends `${infer F}${infer Rest}`
  ? Split<Rest, [...U, F]>
  : U;

type MyType = Split<"abcdef">;
// MyType = ["a", "b", "c", "d", "e", "f"]
```

## Trim, TrimStart, TrimEnd

```ts
type TWhiteSpace = " " | "\n" | "\t";

type TrimStart<S extends string> = S extends `${TWhiteSpace}${infer R}` ? TrimStart<R> : S;
type TrimEnd<S extends string> = S extends `${infer R}${TWhiteSpace}` ? TrimEnd<R> : S;
type Trim<T extends string> = TrimRight<TrimLeft<T>>;

type MyTrimEnd = TrimEnd<"Hello World   ">;
// 'Hello World'
type MyTrimStart = TrimStart<"  Hello World">;
// 'Hello World'
type MyTrim = Trim<"   Hello World   ">;
// 'Hello World'
```

## Lowercase To Uppercase

```ts
type LowercaseToUppercase<L extends string> = L extends `${"a"}${infer R}`
  ? `${"A"}${LowercaseToUppercase<R>}`
  : L extends `${"b"}${infer R}`
  ? `${"B"}${LowercaseToUppercase<R>}`
  : L extends `${"c"}${infer R}`
  ? `${"C"}${LowercaseToUppercase<R>}`
  : L extends `${"d"}${infer R}`
  ? `${"D"}${LowercaseToUppercase<R>}`
  : L extends `${"e"}${infer R}`
  : .....
  : L;

type MyUppercase = LowercaseToUppercase<"hello">;
// MyUppercase = "HELLO"
```

With the akin method, we also make a `UppercaseToLowercase` type definition.

## Capitalize

```ts
type Capitalize<S extends string> = S extends `${infer L}${infer R}` ? `${Uppercase<L>}${R}` : "";

type MyType = Capitalize<"hello world">;
// MyType = 'Hello world'
```

## Replace

```ts
type Replace<S extends string, F extends string, T extends string> = F extends ""
  ? S
  : S extends `${infer L}${F}${infer R}`
    ? `${L}${T}${R}`
    : S;

type MyType = Replace<"this is the test demo", "e", "E">;
// MyType: 'this is thE test demo'
```

It replace the first matched char.

## Replace All

```ts
type ReplaceAll<S extends string, F extends string, T extends string> = F extends ""
  ? S
  : S extends `${infer L}${F}${infer R}`
    ? `${ReplaceAll<L, F, T>}${T}${ReplaceAll<R, F, T>}`
    : S;

type MyType = ReplaceAll<"this is the test demo", "e", "E">;
// MyType: 'this is thE tEst dEmo'
```

Replace all matched chars.

## StartsWith && EndsWith

```ts
type StartsWith<T extends string, U extends string> = T extends `${U}${string}` ? true : false;
type EndsWith<T extends string, U extends string> = T extends `${string}${U}` ? true : false;

type a = StartsWith<"abc", "ac">; // false
type b = StartsWith<"abc", "ab">; // true
type c = StartsWith<"abc", "abcd">; // false
```

## Repeat String

```ts
type RepeatString<
  Input extends string,
  Count,
  AuxArr extends Input[] = [],
  Result extends string = "",
> = AuxArr["length"] extends Count ? Result : RepeatString<Input, Count, [Input, ...AuxArr], `${Input}${Result}`>;

type MyType = RepeatString<"hello", 3>;
// 'hellohellohello'
```


There are some type exercise about string literal type.

TypeScript Type-Exercises 2


- Template String

```ts
type URL:`https://${string}:${port}`
let a1:URL = 'https://google.com:443' // ok
let a2:URL = 'https://test' // error
```

## Get the return type of the function

```ts
type ReturnType<T> = T extends (...args: any[]) => infer R ? R : any;

type T2 = ReturnType<() => string>; // T2 = string
const sum = (a: number, b: number): number => a + b;
type T3 = ReturnType<sum>; // T3 = number
```

## Get the parameters type list

```ts
type Parameters<T extends (...args: any[]) => any> = T extends (...args: infer P) => any ? P : never;

type Func = (a: number, b: string) => void;
type Params = Parameters<Func>;
// Params = [number, string]
```

**Note:** For above two examples they showed the keyword `infer`'s usage. \
Namely you can treat them as a variable that contain the correspond type. \
For example, in `type Parameters<T extends (...args: any[]) => any> = T extends (...args: infer P) => any ? P : never` , the `infer P` means storing the types of `...args` into `P` and assigns `P`'s value to the `Parameters` if `T` is an function.

## Restrict the variable equals to one of the elements in an Tuple

```ts
const myTuple = ["a", 100, false] as const;

type MyType = (typeof myTuple)[number];

let myVar: MyType;
// myVar could only be 'a', 100 or false
```

**Note:** In this example the `myTuple` was perceived an readonly tuple and every element are its literal type, namely the first element is the `'a'` type rather then `string`. If you want to make `MyType = string | number | boolean` you can remove the `as const` assertion.

## Equal to the first element in a specified tuple.

```ts
type First<T extends any[]> = T extends [infer F, ...infer R] ? F : never;

type MyType = First<["a", 100, false]>;
// MyType = 'a'
```

## Awaited. Get the type `T` of `Promise<T>`

```ts
type Awaited<T extends Promise<any>> = T extends PromiseLike<infer L> ? L : never;

const asyncFunc = async () => {
  return true;
};
type MyType = Awaited<asyncFunc>;
// MyType = boolean.
```


TypeScript Type-Exercises 1


![蔡元培（1868-1940），字鹤卿](https://image-assets.dreams.plus/7b2044bab6ac61e0b9dfc6ebcdcf620.webp)

五年前，严几道先生为本校校长时，余方服务教育部，开学日曾有所贡献于学校。诸君多自预科毕业而来，想必闻知。士别三日，刮目相见，况时阅数载，诸君较昔当为长足之进步矣。予今长斯校，请以三事为诸君告：

一曰抱定宗旨。诸君来此求学，必有一定宗旨，欲求宗旨之正大与否，必先知大学之性质。今人肄业专门学校，学成任事，此固势所必然。而在大学则不然，大学者，研究高深学问者也。外人每指摘本校之腐败，以求学于此者，皆有做官发财思想，故毕业预科者，多入法科，入文科者甚少，入理科者尤少，盖以法科为干禄之终南捷径也。因做官心热，对于教员，则不问其学问之浅深，惟问其官阶之大小。官阶大者，特别欢迎，盖为将来毕业有人提携也。现在我国精于政法者，多入政界，专任教授者甚少，故聘请教员，不得不聘请兼职之人，亦属不得已之举。究之外人指摘之当否，姑不具论，然弭谤莫如自修，人讥我腐败，问心无愧，于我何惧？果欲达其做官发财之目的，则北京不少专门学校，入法科者尽可肄业于法律学堂，入商科者亦可投考商业学校，又何必来此大学？所以诸君须抱定宗旨，为求学而来，入法科者，非为做官;入商科者，非为致富。宗旨既定，自趋正轨，诸君肄业于此，或三年，或四年，时间不为不多，苟能爱惜分阴，孜孜求学，则求造诣，容有底止。若徒志在做官发财，宗旨既乖，趋向自异。平时则放荡冶游，考试则熟读讲义，不问学问之有无，惟争分数之多寡;试验既终，书籍束之高阁，毫不过问，敷衍三、四年，潦草塞责，文凭到手，即可借此活动于社会，岂非与求学初衷大相背驰乎？光阴虚度，学问毫无，是自误也。且辛亥之役，吾人之所以革命，因清廷官吏之腐败。即在今日，吾人对于当轴多不满意，亦以其道德沦丧。今诸君苟不于此时植其基，勤其学，则将来万一因生计所迫，出而仕事，但任讲席，则必贻误学生;置身政界，则必贻误国家。是误人也。误已误人，又岂本心所愿乎？故宗旨不可以不正大。此余所希望于诸君者一也。

二曰砥砺德行。方今风俗日偷，道德沦丧，北京社会，尤为恶劣，败德毁行之事，触目皆是，非根基深固，鲜不为流俗所染。诸君肄业大学，当能束身自爱。然国家之兴替，视风俗之厚薄。流俗如此，前途何堪设想。故必有卓绝之士，以身作则，力矫颓俗，诸君为大学学生，地位甚高，肩此重任，责无旁贷，故诸君不惟思所以感已，更必有以励人。苟德之不修，学之不讲，同乎流俗，合乎污世，已且为人轻侮，更何足以感人。然诸君终日伏首案前，芸芸攻苦，毫无娱乐之事，必感身体上之苦痛。为诸君计，莫如以正当之娱乐，易不正当之娱乐，庶几道德无亏，而于身体有益。诸君入分科时，曾填写愿书，遵守本校规则，苟中道而违之，岂非与原始之意相反乎？故品行不可以不谨严。此余所希望于诸君者二也。

三曰敬爱师友。教员之教授，职员之任务，皆以图诸君求学便利，诸君能无动于衷乎？自应以诚相待，敬礼有加。至于同学共处一室，尤应互相亲爱，庶可收切磋之效。不惟开诚布公，更宜道义相勖，盖同处此校，毁誉共之。同学中苟道德有亏，行有不正，为社会所訾詈，已虽规行矩步，亦莫能辨，此所以必互相劝勉也。余在德国，每至店肆购买物品，店主殷勤款待，付价接物，互相称谢，此虽小节，然亦交际所必需，常人如此，况堂堂大学生乎？对于师友之敬爱，此余所希望于诸君者三也。

余到校视事仅数日，校事多未详悉，兹所计划者二事：一曰改良讲义。诸君既研究高深学问，自与中学、高等不同，不惟恃教员讲授，尤赖一已潜修。以后所印讲义，只列纲要，细微末节，以及精旨奥义，或讲师口授，或自行参考，以期学有心得，能裨实用二曰添购书籍。本校图书馆书籍虽多，新出者甚少，苟不广为购办，必不足供学生之参考。刻拟筹集款项，多购新书，将来典籍满架，自可旁稽博采，无虞缺乏矣。今日所与诸君陈说者只此，以后会晤日长，随时再为商榷可也。


《就任北京大学校长之演说》是近代教育家蔡元培的演说作品，是蔡元培在 1917 年就任北京大学校长时发表的。这篇就任北京大学校长的就职演讲，开宗明义地对青年学子提出了三点要求：一是抱定宗旨；二是砥砺德行；三是敬爱师友。明确求学目的及办学宗旨，望学子们以身作则，匡正流俗，为天下人之道德楷模。

就任北京大学校长之演说


When we navigate through the ocean of divide and conquer, there's a question that must be addressed—how is the time complexity of divide and conquer algorithms calculated?

## From Divide and Conquer to Recurrence Relation

Divide and conquer involves breaking down a large problem into smaller subproblems and then merging the solutions of these subproblems to obtain the solution to the original problem. Recurrence relation is a mathematical way of modeling the time cost of this process.

Starting with a concrete example makes it easier to understand. Taking merge sort as an example, let $T(n)$ represent the time complexity of the original problem, where $n$ is the size of the input data. In the first split, the original data is divided into two equal parts, each of size $n/2$. Then, recursive calls to merge sort are made on these two parts, and the time complexity of this part is $2 T(n/2)$. Finally, the two sorted subarrays are merged, requiring a time complexity of $\Theta(n)$.

Based on the analysis above, we can write the recurrence relation for merge sort as follows:

$$
T(n) = \left\{ \begin{aligned} &\Theta(1) & \text{if } n=1\\ &2 T(n/2) + \Theta(n) & \text{if } n>1 \end{aligned} \right.
$$

It can be imagined that for any divide and conquer algorithm, its time complexity can be expressed as a recurrence relation. The right-hand side of the recurrence relation usually consists of two parts: the total cost of the divided subproblems and the total cost of dividing and merging subproblems. The first part remains a function of $T$, while the second part represents the actual asymptotic complexity.

Having a recurrence relation is not sufficient to determine the exact time complexity of the algorithm. We need to further calculate the actual solution $T(n)$.

## Substitution Method

The first method for solving recurrence relations is called the substitution method. We need to guess the form of the solution first and then use mathematical induction to prove that the guess is correct.

For Equation (1), let's assume that our guess for the solution is $T(n) = O(n \log n)$. If we remove the asymptotic notation, this equation is equivalent to $T(n) \le c_1 n \log n$, where $c_1$ is any positive constant.

According to mathematical induction, we first need to establish that the guess holds for small values of $n$. When $n=1$, according to Equation (1), $T(1) = \Theta(1) = d_1$, where $d_1$ is some constant greater than 0. According to the guess, we hope $T(1) \le c_1 \log 1 = 0$, but no matter how we choose $c_1$, this equation cannot hold because $T(1) = d_1$ is always greater than 0. The mathematical induction fails before it even starts.

However, there is no need to worry; this is just a special case caused by $ \log 1 = 0$. We can place the initial state of mathematical induction at $n>1$ without affecting the results of mathematical induction. We are only interested in the asymptotic properties of $T(n)$ when $n$ is sufficiently large, not in the initial stage.

Now, let $n = 2$, then $T(2) = 2T(1) + d_2 = 2d_1 + d_2$. We hope that $T(2) \le c_1 \log 2$ holds. Simplifying, we get $c_1 \ge d_1 + d_2/2$. Since $d_1$ and $d_2$ are constants, such $c_1$ exists, and the initial condition holds.

Next, mathematical induction assumes that the solution holds at $n/2$, i.e., $T(n/2) \le c_1 \frac{n}{2} \log\frac{n}{2} = \frac{1}{2}c_1n(\log n - 1)$. Then we prove that $T(n) \le c_1 n \log n$ also holds.

Substituting $T(n/2)$ into Equation (1), we get

$$
\begin{equation} \begin{aligned} T(n) & = 2 T\left(\frac{n}{2}\right) + \Theta(n) \\ & \le 2 \frac{1}{2}c_1n(\log n - 1) + d_2n \\ & = c_1 n \log n + (d_2 - c_1) n \\ & \le c_1 n \log n \end{aligned} \end{equation}
$$

Where the last line's inequality requires $d_2 - c_1 < 0$, obviously such $c_1$ exists, so the proof is complete.

Thus, we have proved that $T(n) = O(n \log n)$ is the solution to the recurrence relation (1). However, this is not the end; this asymptotic notation is not a tight bound. Can we further guess that $T(n) = \Theta(n \log n)$ holds? This is indeed a good idea. So, as we proceed, as long as we can prove that $T(n) = \Omega(n \log n)$ holds, we can obtain the tight bound mentioned above. Removing the asymptotic notation, this equation is equivalent to $T(n) \ge c_2 n \log n$. Using mathematical induction again, confirming that this holds in the initial stage, and then assuming that the solution holds at $n/2$, we can derive that the solution holds at $n$. Therefore, the proof is complete. Since the proof steps are almost identical to those just mentioned, we will not elaborate on them, and you can try it yourself.

The substitution method relies on accurate guesses, which can be impractical. Therefore, in practice, a more common approach is to find a guess using other methods and then use the substitution method to verify the guess. The recursive tree method we will introduce next provides this possibility.

## Recursive Tree

Expanding the recurrence relation layer by layer directly yields a tree structure. For example, let's take $T(n) = 3 T(n/4) + \Theta(n^2)$ as an example and see how to draw its recursive tree.

Expanding the first layer, we draw three child nodes under the root node.

Here, $cn^2$ represents the cost of decomposition and merging at this layer, which corresponds to the part represented by $\Theta(n^2)$ in the recurrence relation.

Next, further expand to the second layer.

![Recursive Tree](https://image-assets.dreams.plus/20231218224727.webp)

Here, the cost of each node in the first layer is still $c(\frac{n}{4})^2$, still corresponding to the part represented by $\Theta(n^2)$ in the recurrence relation, but the data size has changed from $n$ to $n/4$.

Continue expanding in this way until the leaf nodes.

![Recursive Tree](https://image-assets.dreams.plus/20231218224626.webp)

This completes a complete recursive tree. The data size of each layer is reduced to one-fourth of the previous one, until the data size of the leaf node is 1, so the total number of layers is $\log_4 n$. The rightmost side of the figure calculates the total cost of all nodes in each layer, and the calculation is simple: multiply the cost of a single node by the number of nodes in that layer. In the last layer, the cost of a single node is a constant, and the number of nodes is $3^{\log_4 n} = n^{\log_4 3}$, and we denote the total cost as $\Theta(n^{\log_4 3})$.

Next, we just need to add up the costs of all nodes to obtain the solution to the recurrence relation.

$$
\begin{aligned} T(n) &= cn^2 + \frac{3}{16} cn^2 + \left(\frac{3}{16}\right)^2 cn^2 + \cdots + \left( \frac{3}{16} \right)^{\log_4 n-1} cn^2 + \Theta(n^{\log_4 3}) \\ &=\sum_{i=0}^{\log_4 n-1}{\left(\frac{3}{16}\right)^i cn^2} + \Theta(n^{\log_4 3})\\ &\lt \sum_{i=0}^{\infty}{\left(\frac{3}{16}\right)^i cn^2} + \Theta(n^{\log_4 3}) \\ &= \frac{1}{1 - 3/16}cn^2 + \Theta(n^{\log_4 3}) \\ &= \frac{16}{13} cn^2 + \Theta(n^{\log_4 3}) \\ &= O(n^2) \end{aligned}
$$

Here, in the third line, we made a simplification by replacing a finite geometric series with an infinite geometric series. Although the total size has increased, this infinite decreasing geometric series has a limit, so this replacement can simplify the derivation process. The second term in the fifth line is a lower-order term relative to the first term, so it is discarded, resulting in the final result.

Similar to before, we have only proven the upper bound of the recurrence relation. Naturally, we want to try whether it can also be proven as a lower bound. In the above equation, each term in the summation contains $cn^2$, and each term is positive, so $T(n) = \Omega(n^2)$ obviously holds. Therefore, the solution to the recurrence relation is $T(n) = \Theta(n^2)$.

In this example, we directly calculated the solution to the recurrence relation using the recursive tree method. Of course, we can use the substitution method to verify whether this solution is correct. In some cases, it may be slightly difficult to calculate the exact solution using the recursive tree method, but it does not prevent us from making a reasonable guess and then further verifying this guess using the substitution method.

## Master Theorem

Both the substitution method and the recursion tree method have their drawbacks. The former requires an accurate guess, while the latter involves drawing a recursion tree and deriving results. If you derive too much, you may find that the forms of most recursive solutions seem to be the same. From the derivation process above, it can be observed that the final solution depends entirely on the sum of costs in the middle layers and has nothing to do with the leaf layer because the latter is a lower-order term. In other recursion trees, the final solution may depend entirely on the cost of the leaf layer, unrelated to the middle layers. Therefore, we may be able to classify recursive formulas and directly write out the final solution according to some rules. This is the idea behind the master theorem.

When the divide-and-conquer method evenly splits the data each time, the recursive formula generally has the following form.

$$
T(n) = aT\left(\frac{n}{b}\right) + f(n) \tag{2}
$$

where $a$ is a positive integer representing the number of subproblems when dividing each time, $b$ is an integer greater than 1 representing the reduction factor in problem size each time, and $f(n)$ is an asymptotically positive function representing the cost of dividing and merging.

To find a unified solution applicable to any $a$, $b$, and $f(n)$, we still need to use the recursion tree to calculate the costs of all intermediate and leaf nodes and try to derive a simple result.

![](https://image-assets.dreams.plus/20231218224657.webp)

From the graph, we can see that the total cost of all nodes is $T(n) = \Theta(n^{\log_b a}) + \sum_{j=0}^{\log_b n-1}{a^j f(n/b^j)}$. Further derivation requires a breakthrough idea, and I don't know how the original researchers discovered the following pattern, but it is indeed magical.

Researchers found that the relationship between $f(n)$ and $\Theta(n^{\log_b a})$ determines the final simplified form of $\sum_{j=0}^{\log_b n-1}{a^j f(n/b^j)}$. Define

$$
g(n) = \sum_{j=0}^{\log_b n-1}{a^j f(n/b^j)} \tag{3}
$$

Now let's analyze three cases.

1. If $\Theta(n^{\log_b a})$ is larger, we can assume that there exists a constant $\epsilon > 0$ such that $f(n) = O(n^{\log_b a-\epsilon})$. Substituting this into the summation formula, it can be simplified to $g(n) = O(n^{\log_b a})$.

2. If both are equally large, directly substitute into equation (3) and simplify to get $g(n) = \Theta(n^{\log_b a} \log n)$.

3. If $f(n)$ is larger and, for some constant $c < 1$, for all sufficiently large $n$, $a f(n/b) \le c f(n)$ holds, then it can be deduced that $g(n) = \Theta(f(n))$.

Here, the complete proof process is not provided, partly because I don't want to make it too long, and secondly, I feel that these proofs are somewhat cumbersome and not very meaningful. Interested students can refer to the original book.

Substituting the functions $g(n)$ for these three cases into the complete solution, we get:

- For case 1: $T(n) = \Theta(n^{\log_b a}) + O(n^{\log_b a}) = \Theta(n^{\log_b a})$

- For case 2: $T(n) = \Theta(n^{\log_b a}) + \Theta(n^{\log_b a} \log n) = \Theta(n^{\log_b a} \log n)$

- For case 3: $T(n) = \Theta(n^{\log_b a}) + \Theta(f(n)) = \Theta(f(n))$

Now, for any recursive formula, we only need to determine which case it belongs to and directly substitute into the corresponding formula. To facilitate understanding, let's go through a few examples.

**Example 1:**

$T(n) = 9 T(n/3) + n$

For this recursive formula, we have $a = 9$, $b = 3$, $f(n) = n$. Since $f(n) = n$ is asymptotically smaller than $\Theta(n^2)$, it can be applied to the first case of the master theorem, and the solution is $T(n) = \Theta(n^2)$.

**Example 2:**

$T(n) = T(2n/3) + 1$

For this formula, $a = 1$, $b = 3/2$, $f(n) = 1$. Since $n^{\log_b a} = n^{\log_{3/2} 1} = n^0 = 1$, which is exactly equal to $f(n)$, it can be applied to the second case of the master theorem, and the solution is $T(n) = \Theta(\log n)$.

**Example 3:**

$T(n) = 3T(n/4) + n\log n$

For this formula, $a = 3$, $b = 4$, $f(n) = n\log n$. Since $n^{\log_b a} = n^{\log_4 3} = n^{0.793}$, and $f(n) = n\log n$ is asymptotically larger than $n^{0.793}$, it should consider the third case of the master theorem. However, we need to check if the additional condition holds: for some constant $c < 1$ and all sufficiently large $n$, $a f(n/b) \le c f(n)$ holds. Substituting $a$, $b$, and $f(n)$ into the inequality, we get

$$
3\frac{n}{4}\log\frac{n}{4} \le cn\log n \implies \frac{3}{4}( \log n - 2) \le c\log n \implies \left(\frac{3}{4} - c\right) \log n \le \frac{3}{2}
$$

When $c \ge \frac{3}{4}$, this inequality always holds, and the additional condition is satisfied. Therefore, it can be applied to the third case of the master theorem, and the solution is $T(n) = \Theta(n\log n)$.

**Example 4:**

$T(n) = 2T(n/2) + n\log n$

For this formula, $a = 2$, $b = 2$, $f(n) = n\log n$. Since $n^{\log_b a} = n^{\log_2 2} = n$, and $f(n) = n\log n$ is asymptotically larger than $n$, it should consider the third case of the master theorem. Substituting $a$, $b$, and $f(n)$ into the inequality, we get

$$
2\frac{n}{2}\log\frac{n}{2} \le cn\log n \implies \log n - 1 \le c\log n \implies (1-c)\log n \le 1
$$

When $c \ge 1$, this inequality always holds. However, the additional condition requires $c < 1$, so this case cannot be applied to the third case of the master theorem. In other words, not all recursive formulas of the form $T(n) = a T(n/b) + f(n)$ can be solved using the master theorem; there is a gap between cases two and three. In such cases, we can only use the recursion tree method. Students can try it, and the result will be $T(n) = \Theta(n \log^2 n)$.

After going through these four examples, have you mastered the master theorem? If you have any questions, please leave a comment, and I will reply as soon as possible.

The study of algorithms is endless, and the calculation of time complexity is fundamental and should not be underestimated.

## Details

Careful readers may notice that in the fourth case mentioned above, although $nlgn$ grows asymptotically faster than $n$, it is not asymptotically greater in the polynomial sense because there is no $\epsilon > 0$ such that $nlgn = \Omega \left( n^{1+\epsilon} \right)$ holds. On the contrary, $nlgn = o \left( n^{1+\epsilon} \right)$ holds for any $\epsilon > 0$. So, in fact, this case does not need to be judged for regular conditions to draw conclusions in advance. However, in the third case in the previous text, I did not emphasize asymptotic greater in the polynomial sense, not because I forgot to write it, but because this condition is not needed at all.

For any recurrence relation that fits the master theorem format, if it satisfies the regular conditions in case three, then it must satisfy $f\left(n\right) = \Omega \left( n^{log_b a + \epsilon} \right)$." The specific proof details can be found in [this answer](https://cs.stackexchange.com/a/121749/128497) on StackExchange, and are not detailed here.

Although regular conditions can imply $f\left(n\right) = \Omega \left( n^{log_b a + \epsilon} \right)$, the reverse is not true. We can construct the following function:

$T\left(n\right) = T\left(n/2\right) + n\left( 2 - \cos n \right)$

Here, $a=1$, $b=2$, and $f\left(n\right) = n \left( 2 - \cos n \right) = \Omega \left( n^{log_2 1+ \epsilon} \right) = \Omega \left( n^\epsilon \right)$ holds for any $\epsilon \le1$. However, when applying the regular condition:

$\begin{aligned} f\left(n / 2\right) &\le c f\left(n\right) \\ \frac{n}{2} \left(2 - \cos \frac{n}{2} \right) & \le c \left( 2 - \cos n \right) \end{aligned}$

For any $c \lt 1$, the right side must be $c \left( 2 - \cos n \right) \lt 3$. However, the left side, when $n$ is large enough, must be greater than $3$. Therefore, this equation cannot hold, and the regular condition is not satisfied.

## Reference

These cases are from the Wikipedia entry on [Master theorem](<https://en.wikipedia.org/w/index.php?title=Master_theorem_(analysis_of_algorithms)&section=7#Inadmissible_equations>).


In this article, we will model the time complexity of divide and conquer using mathematical methods, analyze its asymptotic properties, and provide three methods of calculation.

The Master Theorem For Time Complexity


## Problem Citation

A pile of stones, two people take turns to take at least 1 stone and at most 2 stones. Whoever gets the last stone loses. Is there a sure-win strategy of playing first and playing second? That's a famous **Bash Game Problem**

## Analysis

There is a pile of n items in total, and two players take turns picking up items from it. It is stipulated that each time at least one item must be taken, and at most m items can be taken. The one who takes the last item wins.

Let

$n=(m+1)q+r \quad( 0\leq r \leq m ) \\$

$\quad (\text{i})\quad$If $r=0$, the second player will win. The strategy is as follows:

If the first player takes away $k$ items, the second player takes away $m+1-k$ items. The result is $(m+1)(q-1)$ items left. By maintaining this method, the second player will win.

$\quad (\text{ii})\quad$If $r≠0$, the first player will win. The strategy is as follows:

The first player takes away $r$ items first. If the second player takes away $k$ items, the first player takes away $m+1-k$ items. The result is $(m+1)(q-1)$ items left. By maintaining this method, the first player will win.

In short, to ensure that the opponent is left with a multiple of $(m+1)$, one can eventually win.

## Extension

If it is stipulated that the one who takes the last item loses, let

$n-1=(m+1)q+r \quad( 0≤r≤m ) \\$

$\quad (\text{i})\quad$If $r=0$, the second player will win. The strategy is as follows: If the first player takes away $k$ items, the second player takes away $m+1-k$ items. The result is $(m+1)(q-1)+1$ item left. By maintaining this method, the first player will take the last item.

$\quad (\text{ii})\quad$If $r≠0$, the first player will win. The strategy is as follows: The first player takes away $r$ items first. If the second player takes away $k$ items, the first player takes away $m+1-k$ items. The result is $(m+1)(q-1)+1$ item left. By maintaining this method, the second player will take the last item.

## Mini Game

Two people take turns counting, each time reporting at least one, at most ten. Whoever reaches $100$ first wins.

Attached code:

```cpp
#include<cstdio>
#include<string.h>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        int n,m;
        scanf("%d%d",&n,&m);
        if(n%(m+1)) printf("first\n");
        else printf("second\n");
    }
    return 0;
}
```

References:

- [1] [Summary of Bash Game](https://suool.blog.csdn.net/article/details/15777651?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.control&dist_request_id=ea4f2841-87a2-4c48-a15d-b529f81dffd9&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.control)
- [2] [Bash Game hdu 1846](https://www.cnblogs.com/pangbi/p/11509328.html)
- [3] [Bash Game - Baidu Baike](https://baike.baidu.com/item/巴什博弈/1819345?fr=aladdin)


A pile of stones, two people take turns to take at least 1 stone and at most 2 stones. Whoever gets the last stone loses.

The Bash Game


## Prologue

_Fast Inverse Square Root_ is a rather famous algorithm, and the specific author is no longer traceable. Its prominence comes from its extensive use in the game Quake III, where it became well-known.

Why do we need the inverse square root instead of the square root itself? In computer graphics, many calculations involve the inverse square root rather than the square root. For example, the `normalize()` operation for a vector $\frac{1}{\sqrt{x^2 + y^2 + z^2}}(x,y,z)$ includes the inverse square root. In computer graphics, each frame's rendering requires at least tens of thousands of calls to normalize. If we can accelerate the calculation of the inverse square root, the rendering speed will significantly improve.

The algorithm originated more than 20 years ago. Today, the algorithm has research value but not practical use since modern CPUs have faster and more accurate instructions. We can simply use `1/sqrt(y)`.

However, this doesn't hinder us from understanding the elegance of this algorithm. In a brief overview, it involves:

1. IEEE 754 Standard
2. Undefined behavior in the C language
3. Newton's iteration method.

The focus here is on the second step—how to derive the magic number `0x5f3759df`. For more detailed information, you can refer to the source.

## Algorithm

```c
float Q_rsqrt(float number)
{
    long i;
    float x2, y;
    const float threehalfs = 1.5F;
    x2 = number * 0.5F;
    y = number;

    /* Core Code */
    // 1. reinterpret_cast from float to int
    i = *(long *)&y; // evil floating-point bit-level hacking
    // 2. Estimate the inverse square root
    i = 0x5f3759df - (i >> 1); // what the heck? (....why not 0x69696969?)
    // reinterpret_cast from int to float
    y = *(float *)&i;
    // 3. Newton's method
    y = y * (threehalfs - (x2 * y * y)); // 1st iteration
    // y = y * (threehalfs - (x2 * y * y)); // 2nd iteration, this can be removed

    return y;
}
```

The algorithm roughly consists of three parts:

- `reinterpret_cast` used for conversion between float and int because any compiler would otherwise prohibit bitwise operations on float types.
- Estimation using the magic number `0x5f3759df` for the inverse square root (explained later).
- One iteration of Newton's method (explained later).

## Estimating the Inverse Square Root

In the IEEE 754 standard, a 32-bit floating-point number contains 1 sign bit, 8 exponent bits $E$, and 23 mantissa bits $M$. Any floating-point number can be represented as: $(1.M) \times 2^{E - 127} = (1 + \frac{M}{2^{23}}) \times 2^{E - 127}, M \in[0, 2^{23} ), E \in [0,256)$.

To calculate $y$'s inverse square root $\frac{1}{\sqrt{y}} = y^{-\frac{1}{2}}$, the IEEE 754 form of $y$ is $y = (1 + \frac{M_y}{2^{23}}) \times 2^{E_y - 127}$.

For simplicity, let's take the logarithm of $y$ to the base 2:

$$
\begin{align}
\log y &= \log{((1 + M_y) \times 2^{E_y - 127})} \\
&= \log{(1+\frac{M_y}{2^{23}})} + E_y - 127
\end{align}
$$

It's clear that $\frac{M_y}{2^{23}}$ is in the interval $[0,1]$. In this interval, $\log(1+x) \approx x$. If we add a constant $\mu$, the approximation improves:

Using this approximation, we can further simplify:

$$
\begin{align}
\log y
&= \log{(1+\frac{M_y}{2^{23}})} + E_y - 127 \\
&\approx \frac{M_y}{2^{23}} + \mu + E_y - 127 \\
&= \frac{1}{2^{23}}(M_y + E_y \times 2^{23}) + \mu - 127
\end{align}
$$

Now, let's take the logarithm of $y^{-\frac{1}{2}}$:

$$
\log y^{-\frac{1}{2}} = -\frac{1}{2} \log y \approx -\frac{1}{2}\left( \frac{1}{2^{23}}(M_y + E_y \times 2^{23}) + \mu - 127 \right)
$$

Assuming the accurate value of $y^{-\frac{1}{2}}$ is $A$, with exponent and mantissa $E_A$ and $M_A$ respectively, we can take the logarithm of $A$:

$$
\log A \approx \frac{1}{2^{23}}(M_A + E_A \times 2^{23}) + \mu - 127
$$

By equating the two logarithmic expressions, we get:

$$
\begin{align}
M_A + E_A \times 2^{23} &= 2^{23} \times \frac{3}{2}(127 - \mu) - \frac{1}{2}(M_y + E_y \times 2^{23})
\end{align}
$$

When $\mu$ is set to $0.0450461875791687011756$, the first term becomes `1597463011` in hexadecimal (`0x5F3759e3`). If we replace the second term's $\frac{1}{2}$ with a right shift operation, the result is remarkably close to the line in the code:

```c
i = 0x5f3759df - (i >> 1);
```

The magic number is slightly different, but with an appropriate $\mu$ value, it should yield exactly the same number.

## Newton's Iteration Method

The update formula for Newton's iteration method is:

$$
x_{t+1} = x_t - \frac{f(x_t)}{f^\prime(x_t)}
$$

The precondition for Newton's iteration method is that the initial point should be near the function's zero. Since the estimation from `i = 0x5f3759df - (i >> 1);` should have a small error, we can assume the precondition is satisfied.

Now, our problem is, given $y$, we need to find $x$ such that $\frac{1}{\sqrt{y}} = x$, i.e., $\frac{1}{x^2} = y$. Rearranging, we get $f(x) = \frac{1}{x^2} - y = 0$. Applying Newton's iteration to $f(x)$ gives the iteration formula:

$$
x_{t+1} = x_t - \frac{y}{2}x_t^3
$$

This is translated into code as:

```c
y = y * (threehalfs - (x2 * y * y));
```

## References

[1] [Is fast inverse square root still used?](https://www.quora.com/Is-fast-inverse-square-root-still-used)

[2] [Fast Inverse Square Root — A Quake III Algorithm](https://www.youtube.com/watch?v=p8u_k2LIZyo)

[3] [Relevant Thesis](https://www.lomont.org/papers/2003/InvSqrt.pdf)


Magic Number - 0x5f3759df

The article introduces an algorithm called Fast Inverse Square Root, which is used to quickly calculate the inverse square root of a floating point number.

Fast Inverse Square Root


余幼時即嗜學。家貧，無從致書以觀，每假借於藏書之家，手自筆錄，計日以還。天大寒，硯冰堅，手指不可屈伸，弗之怠。錄畢，走送之，不敢稍逾約。以是人多以書假余，余因得遍觀羣書。既加冠，益慕聖賢之道，又患無碩師名人與游，嘗趨百里外，從鄉之先達執經叩問。先達德隆望尊，門人弟子填其室，未嘗稍降辭色。余立侍左右，援疑質理，俯身傾耳以請；或遇其叱咄，色愈恭，禮愈至，不敢出一言以復；俟其欣悅，則又請焉。故余雖愚，卒獲有所聞。

當余之從師也，嘗負篋曳屣，行深山巨谷中。窮冬烈風，大雪深數尺，足膚皸裂而不知。至舍，四支僵勁不能動，媵人持湯沃灌，以衾擁覆，久而乃和。寓逆旅，主人日再食，無鮮肥滋味之享。同捨生皆被綺綉，戴珠纓寶飾之帽，腰白玉之環，左佩刀，右備容臭，燁然若神人。余則縕袍敝衣處其間，畧無慕豔意。以中有足樂者，不知口體之奉不若人也。蓋余之勤且艱若此。今雖耄老，未有所成，猶幸預君子之列，而承天子之寵光，綴公卿之後，日侍坐備顧問，四海亦謬稱其氏名，況才之過於余者乎？

今諸生學於太學，縣官日有廩稍之供，父母歲有裘葛之遺，無凍餒之患矣；坐大廈之下而誦《詩》《書》，無奔走之勞矣；有司業、博士為之師，未有問而不告、求而不得者也；凡所宜有之書，皆集於此，不必若余之手錄、假諸人而後見也。其業有不精、德有不成者，非天質之卑，則心不若余之專耳，豈他人之過哉。

東陽馬生君則，在太學已二年，流輩甚稱其賢。余朝京師，生以鄉人子謁余，譔長書以為贄，辭甚暢達；與之論辯，言和而色夷。自謂少時用心於學甚勞，是可謂善學者矣。其將歸見其親也，余故道為學之難以告之。謂余勉鄉人以學者，余之志也；詆我夸際遇之盛而驕鄉人者，豈知予者哉。


余朝京師，生以鄉人子謁余，譔長書以為贄，辭甚暢達；與之論辯，言和而色夷。自謂少時用心於學甚勞，是可謂善學者矣。其將歸見其親也，余故道為學之難以告之。謂余勉鄉人以學者，余之志也；詆我夸際遇之盛而驕鄉人者，豈知予者哉。

原点日志

ALL POSTS