tags:
- NotesIntro to Algorithm
对于一段好的程序，算法至关重要。算法是解决问题的一系列步骤或规则，是抽象的。而程序则更加具体，当你将算法变为程序时，你需要在特定的环境下用特定的编程语言来进行实现。
下面是算法和程序的比较：
| Algorithm | Program |
|---|---|
| Design | Implementation |
| Domain Knowledge | Programmer |
| Any Language | Programming Language |
| Hardware and OS Independent | Hardware and OS Dependent |
| Priori Analysis | Posteriori Testing |
算法是实现前的程序设计，需要领域内的知识，算法可以用任何语言来描述而且通常上无关系硬件和系统。而程序是算法思想的实现，由程序员完成，按照要求用特定的编程语言在特定的硬件设备和系统环境下进行。
在算法阶段，我们衡量一个算法好坏的评判标准是分析其时间复杂度和空间复杂度，这通常作为先验分析。在程序实现完成后，我们需要通过实际的运行来评估其性能，这被叫做后验测试。
算法的特征或properties用以下五方面来表示：
写一个算法很简单，你可以不需要任何的编程语言知识来描述算法的思想。但是，算法的实现需要你将算法思想转换成一些编程语言。假如我有一个交换A和B值的算法，我可以这样实现：
SWAP(A, B):
Begin
temp = A
A = B
B = Temp
End
也可以这样：
int SWAP(A, B)
{
temp := A;
A := B;
B := temp;
}
尽管细节可能有所不同，但它们传达的主题思想都是一样的。
传统上，我们通常使用时间复杂度和空间复杂度来衡量一个算法的好坏。此外，我们还有其他的一些标准来衡量一个算法，如：
对于时间复杂度的计算，我们简单地将高级语言程序中的一行代码作为一个基本操作。在上面的SWAP算法中，我们的算法的时间复杂度就为3，因为有三行高级语言代码。虽然高级语言程序最终会变成二进制的机器语言，但我们不用关心对时间复杂度的影响。（对能耗和寄存器的确有影响）
由于我们算法的时间复杂度的最高阶是一个常数，因此我们称其为常数时间复杂度，记作
同样上述的算法，当我们计算空间复杂度时，我们将一个变量看作一个基本单位。通过分析程序中基本单位的数量和它们的使用频率，我们可以确定整个算法的空间复杂度。在SWAP算法中，我们有三个变量，但由于我们的空间复杂度最高阶是常数阶，我们也可以将其记作
Big-O describes the worst-case scenario, providing an upper bound on the time complexity.
Big-Ω describes the best-case scenario, providing a lower bound on the time complexity.
Big-Θ describes the average case scenario.