Algorithm

先用几句话简单说明一下时间复杂度。**时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序运行需要的时间增长得有多快。**也就是说，对于高速处理数据的计算机来说，处理某一个特定数据的效率不能衡量一个程序的好坏，而应该看当这个数据的规模变大到数百倍后，程序运行时间是否还是一样，或者也跟着慢了数百倍，或者变慢了数万倍。不管数据有多大，程序处理花的时间始终是一样的，我们就说这个程序很好，具有 $O(1)$ 的时间复杂度，也称常数级复杂度；数据规模变得有多大，花的时间也跟着变得有多长，这个程序的时间复杂度就是 $O(n)$，比如找 $n$ 个数中的最大值；而像冒泡排序、插入排序等，数据扩大 $2$ 倍，时间变慢 $4$ 倍的，属于 $O(n^2)$ 的复杂度。还有一些穷举类的算法，所需时间长度成几何阶数上涨，这就是 $O(a^n)$ 的指数级复杂度，甚至 $O(n!)$ 的阶乘级复杂度。不会存在 $O(2n^2)$ 的复杂度，因为前面的那个 $2$ 是系数，根本不会影响到整个程序的时间增长。同样地，$O (n^3+n^2)$ 的复杂度也就是 $O(n^3)$ 的复杂度。因此，我们会说，一个 $O(0.01n^3)$ 的程序的效率比 $O(100n^2)$ 的效率低，尽管在 $n$ 很小的时候，前者优于后者，但后者运行所需的时间随数据规模增长得慢，最终 $O(n^3)$ 的复杂度将远远超过 $O(n^2)$。我们也说，$O(n^{100})$ 的复杂度小于 $O(1.01^n)$ 的复杂度。 ...

公约数和最大公约数 公约数 在这里，我们约定集合 $\mathbb{Z} = \{\dots, -2, -1, 0, 1, 2, \dots\}$ 表示所有的整数，集合 $\mathbb{N} = \{0, 1, 2, \dots\}$ 表示所有的自然数。 对于任意的实数 $x$，将小于等于 $x$ 的最大整数记作 $\lfloor x \rfloor$，读作 “the floor of $x$”。对于任意的整数 $a$ 和任意正整数 $n$，$a \operatorname{mod} n$ 表示 $a / n$ 的余数（remainder or residue），也就是说： ...

精确算法 Concorde 是一个求解TSP的精确算法，由 ANSI C 编写。在 Concorde Downloads 页面可以下载到最新版本的Concorde。下载后通过在命令行输入下面的命令进行解压，解压后会得到一个名为 concorde 的文件夹，编译的过程参考 Ubuntu（Linux）安装concorde过程或者参考 Installing Solvers · perrygeo/pytsp Wiki。 ...

算法是什么 算法（ Algorithm）是一个有限的、明确的、可计算的步骤序列，用于解决某类特定问题或执行特定计算任务。算法通常由输入、输出和一系列操作组成。它们可以用自然语言、伪代码或编程语言来描述。算法具有以下的特性： ...

字符串 求子串和模式匹配 字符串中求子串和模式匹配是两个不同的概念： 求子串（Substring Extraction）：在给定字符串中找到的连续字符序列。子串可以是字符串的任意部分，包括单个字符、连续的一段字符或者整个字符串本身1。 ...

Bytedance 实习 测试岗 2023.6 丢西瓜捡芝麻策略 解法一：直接从起点开始走，遇到比手上有的物品价格低的就换成买价格低的物品，直到终点，这样就能确保买到的价格最低。算法的时间复杂度为 $O(n)$。 ...