# 一. 算法

下面是数学表达式的应用示例：

^^^ {.fr .w-50 .tip}

ℹ️ 标注⑶：常规会使用多项式来表述一个算法在运行过程中调用系统指令的次数，它可以很好地体现在同一台设备上，运行不同算法的相较性能。

ℹ️ 标注⑷：国外大部分计算机类的书籍里，都会把 $$lg$$ 的底数默认为 2，而非我们熟知的 10。一方面是因为计算机是走二进制的，例如 $$2^{10}=1024$$ 反过来可以表示为 $$10=log_21024$$，将 $$log_2$$ 视为 $$lg$$ 会更省事；另外在渐进算法层面可以知道，指数复杂度 aⁿ 中的底数 a 是不重要的，不同的底数在渐进意义上都是一样的。

^^^

在下章开始我们会看到两个排序相关的算法，第一个是知名的**插入排序**（insertion sort），它对 $$n$$ 个项进行排序大致需要执行 $$c_1n^2$$ 久的时间$$^⑶$$ ，其中的 $$c_1$$ 表示一个不依赖于 $$n$$ 的常量。也就是说，该算法的耗时大致与 $$n^2$$ 成正比。<br>另一个算法是**归并排序**（merge sort），它的耗时大致为 $$c_2n·lg n$$，其中 $$lgn$$ 等价于 $$log_2n^⑷$$，$$c_2$$ 也是一个不依赖于 $$n$$ 的常量。

通常情况下插入排序的常量因子会比归并排序的小，即 $$c_1$$<$$c_2$$。我们应该了解到，就运行时间来说，常数因子对其的影响，可能远不如输入规模 $$n$$ 的影响。

# 二. NP 完全问题

要对小规模的输入进行排序，我们知道可以使用插入排序算法，它会在 $$c_1n^2$$ 久的时间内解决排序问题，对于小规模输入来说它是高效的。