西维蜀黍

【Algorithm】递归（Recursion）

递归（Recursion）

先下定义：递归算法是一种直接或者间接调用自身函数或者方法的算法。

通俗来说，递归算法的实质是把问题分解成规模缩小的同类问题的子问题，然后递归调用方法来表示问题的解。它有如下特点：

  • 一个问题的解可以分解为几个子问题的解
  • 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
  • 存在递归终止条件，即必须有一个明确的递归结束条件，称之为递归出口

  ...

Posted by Wei on 2019-07-29, Last Modified on 2025-08-11

【Algorithm】BigNum 原理

背景

一些基本数据类型的范围：

  • int：32位整数，占4字节，-2^312^31-1(-21亿多21亿多)
  • unsigned int：占4字节，02^32-1(042亿多) –10位数

VC的64位整数 ：

  • _int64：占8字节，-2^632^63-1（-900亿亿多900亿亿多）
  • unsigned int64:占8字节，02^64-1(01800亿亿多)-20位数
  • G++的64位整数：
    • long long==int64
    • unsigned long long==unsigned __int64

实数：

  • float：占4字节，7位有效数字
  • double：占8字节，15位有效数字

浮点型的问题都是追求精度的，在一般情况下我们应当选择使用double，而很少用float；

所以当我们要进行计算的数超过了20位，我们就要用数组来模拟我们的计算过程了；

  ...

Posted by Wei on 2019-07-29, Last Modified on 2025-08-11

【Algorithm】算法的时间复杂度（Time Complexity）

常见的时间复杂度量级

我们先从常见的时间复杂度量级进行大O的理解：

  • 常数阶O(1)

  • 对数阶$O(log_2n)$

  • 线性阶O(n)

  • 线性对数阶$On(log_2n)$

  • 平方阶$O(n^2)$

  • 指数阶$O(2^n)$

复杂度 标记符号 描述
常量（Constant） $O(1) $ 操作的数量为常数，与输入的数据的规模无关。n = 1,000,000 -> 1-2 operations
对数（Logarithmic） $O(log_2n)$ 操作的数量与输入数据的规模 n 的比例是 log2 (n)。n = 1,000,000 -> 30 operations
线性（Linear） $O(n)$ 操作的数量与输入数据的规模 n 成正比。n = 10,000 -> 5000 operations
平方（Quadratic） $O(n^2)$ 操作的数量与输入数据的规模 n 的比例为二次平方。n = 500 -> 250,000 operations
立方（Cubic） $O(n^3)$ 操作的数量与输入数据的规模 n 的比例为三次方。n = 200 -> 8,000,000 operations
指数（Exponential） $O(2^n)$、$O(k^n)$、$O(n!)$ 指数级的操作，快速的增长。n = 20 -> 1048576 operations

列举了几种常见的算法时间复杂度的比较（又小到大）：$O(1)$（常数阶） < $O(log_2n)$（对数阶） < $O(n)$（线性阶） < $O(n2)$（平方阶） < $O(n3)$（立方阶） < $O(2^n)$ (指数阶)。

通常将以 10 为底的对数叫做常用对数。为了简便，N 的常用对数 log10 N 简写做 lg N，例如 log10 5 记做 lg 5。

通常将以无理数 e 为底的对数叫做自然对数。为了方便，N 的自然对数 loge N 简写做 ln N，例如 loge 3 记做 ln 3。

在算法导论中，采用记号 $lg n = log_2n$ ，也就是以 2 为底的对数。改变一个对数的底只是把对数的值改变了一个常数倍，所以当不在意这些常数因子时，我们将经常采用 “lg n"记号，就像使用 O 记号一样。计算机工作者常常认为对数的底取 2 最自然，因为很多算法和数据结构都涉及到对问题进行二分。

而通常时间复杂度与运行时间有一些常见的比例关系：

复杂度 10 20 50 100 1000 10000 100000
$O(1)$ <1s <1s <1s <1s <1s <1s <1s
$O(log_2(n))$ <1s <1s <1s <1s <1s <1s <1s
$O(n)$ <1s <1s <1s <1s <1s <1s <1s
$O(n*log_2(n))$ <1s <1s <1s <1s <1s <1s <1s
$O(n^2)$ <1s <1s <1s <1s <1s 2s 3-4 min
$O(n^3)$ <1s <1s <1s <1s 20s 5 hours 231 days
$O(2^n)$ <1s <1s 260 days hangs hangs hangs hangs
$O(n!)$ <1s hangs hangs hangs hangs hangs hangs
$O(n^n)$ 3-4 min hangs hangs hangs hangs hangs hangs
  ...

Posted by Wei on 2019-07-27, Last Modified on 2025-08-11

【Distributed System】负载均衡（Load Balancing）

负载均衡（Load balancing）

**负载平衡（Load balancing）**是一种计算机技术，用来在多个计算机（计算机集群）、网络连接、CPU、磁盘驱动器或其他资源中分配负载，以达到最优化资源使用、最大化吞吐率、最小化响应时间、同时避免过载的目的。 使用带有负载平衡的多个服务器组件，取代单一的组件，可以通过冗余提高可靠性。负载平衡服务通常是由专用软件和硬件来完成。 主要作用是将大量作业合理地分摊到多个操作单元上进行执行，用于解决互联网架构中的高并发和高可用的问题。

  ...

Posted by Wei on 2019-07-26, Last Modified on 2025-08-11

【Algorithm】排序算法 - 归并排序（Merge Sort）

归并排序（Merge Sort）

归并字面上的意思是合并，归并算法的核心思想是分治法（divide-and-conquer method），就是将一个数组一刀切两半，递归切，直到切成单个元素，然后重新组装合并，单个元素合并成小数组，两个小数组合并成大数组，直到最终合并完成，排序完毕。

  ...

Posted by Wei on 2019-07-25, Last Modified on 2025-08-11

【Netwrok】输入一个 URL 会发生什么

  • ARP

  • DHCP

  • DNS

  • TCP 三次握手

  • HTTPS

  • 路由

  • CDN

  • 负载均衡

  ...

Posted by Wei on 2019-07-24, Last Modified on 2025-08-11

【LaTeX】支持中文

方法 1 - ctexart

完整安装 CTeX 套装、MikTeX 套装、TeXLive 套装，MacTeX套装之一的最新发行版。然后选择一款自己喜欢的，最好良好支持 UTF8 编码的文本编辑器，然后

\documentclass{ctexart}
\begin{document}
中文English
[E = m c^2]
\end{document}

使用 pdflatex 或者 xelatex （推荐方式，须保以 UTF8 编码保存） 编译即可。

  ...

Posted by Wei on 2019-07-24, Last Modified on 2025-08-11

【Operating System】进程 - Linux 启动进程的几种方式

有时候，我们需要在自己的程序（进程）中启动另一个程序（进程）来帮助我们完成一些工作，那么我们需要怎么才能在自己的进程中启动其他的进程呢？在Linux中提供了不少的方法来实现这一点，下面就来介绍一个这些方法及它们之间的区别。

system() 函数调用

Function

The system() function hands the argument command to the command interpreter sh. The calling process waits for the shell to finish executing the command, ignoring SIGINT and SIGQUIT, and blocking SIGCHLD.

If command is a NULL pointer, system() will return non-zero if the command interpreter sh(1) is available, and zero if it is not.

The system() library function uses fork to create a childprocess that executes the shell command specified in command using execl as follows:

execl("/bin/sh", "sh", "-c", command, (char *)

system() returns after the command has been completed.

SYNOPSIS

#include <stdlib.h>
int system (const char *string);

它的作用是，运行以字符串参数的形式传递给它的命令并等待该命令的完成。命令的执行情况就如同在shell中执行命令：sh -c string。如果无法启动shell来运行这个命令，system() 函数返回错误代码127；如果是其他错误，则返回-1。否则，system函数将返回该命令的退出码。

  ...

Posted by Wei on 2019-07-18, Last Modified on 2025-08-11

【Java】集合类 - List - LinkedHashMap

LinkedHashMap

HashMap是无序的，也就是说，迭代HashMap所得到的元素顺序并不是它们最初放置到HashMap的顺序。HashMap的这一缺点往往会造成诸多不便，因为在有些场景中，我们的确需要用到一个可以保持插入顺序的Map。

庆幸的是，JDK为我们解决了这个问题，它为HashMap提供了一个子类 —— LinkedHashMap。

由于LinkedHashMap是HashMap的子类，所以LinkedHashMap自然会拥有HashMap的所有特性。比如，LinkedHashMap的元素存取过程基本与HashMap基本类似，只是在细节实现上稍有不同。当然，这是由LinkedHashMap本身的特性所决定的，因为它额外维护了一个双向链表用于保持迭代顺序。

虽然LinkedHashMap增加了时间和空间上的开销，但是它通过维护一个额外的双向链表保证了迭代顺序。

特别地，该迭代顺序可以是插入顺序，也可以是访问顺序。因此，根据链表中元素的顺序可以将LinkedHashMap分为：保持插入顺序的LinkedHashMap 和 保持访问顺序的LinkedHashMap，其中LinkedHashMap的默认实现是按插入顺序排序的。

总结来说，HashMap和双向链表合二为一即是LinkedHashMap。所谓LinkedHashMap，其落脚点在HashMap，因此更准确地说，它是一个将所有Entry节点链入一个双向链表的HashMap。

  ...

Posted by Wei on 2019-07-16, Last Modified on 2023-02-28

【Cache System】Cache Replacement - LFU（Least Frequently Used）算法

LFU（Least Frequently Used）

LFU (Least Frequently Used) 最近最不常用算法，它是根据频率维度来选择将要淘汰的元素，即删除访问频率最低的元素。如果两个元素的访问频率相同，则淘汰最久没被访问的元素。

也就是说LFU淘汰的时候会选择两个维度，先比较频率，选择访问频率最小的元素；如果频率相同，则按时间维度淘汰掉最久远的那个元素。

  ...

Posted by Wei on 2019-07-15, Last Modified on 2025-08-11

FEATURED TAGS
algorithm algorithmproblem architecturalpattern architecture aws blockchain c# cachesystem codis compile concurrentcontrol database dataformat datastructure debug design designpattern distributedsystem django docker domain engineering freebsd git golang grafana hackintosh hadoop hardware hexo http hugo ios iot java javaee javascript kafka kubernetes linux linuxcommand linuxio lock macos markdown microservices mysql nas network networkprogramming nginx node.js npm oop openwrt operatingsystem padavan performance programming prometheus protobuf python redis router security shell software testing spring sql systemdesign truenas ubuntu vmware vpn windows wmware wordpress xml zookeeper
ABOUT ME
avatar

🐒 Software engineer | 📷 Photographer | 👹 Urban explorer

FRIENDS