1.算法概述.md

算法概述

算法和数据结构

什么是算法

算法（algorithm），这个概念来自数学领域，是用于解决某一类问题的公式和思想。在计算机科学领域的算法，其本质是一系列程序指令，用于解决特定的运算和逻辑问题。

算法有简单的，也有复杂的。有高效的，也有拙劣的。在计算机领域，衡量算法好坏的重要标准有两个。

• 时间复杂度

• 空间复杂度

算法可以应用在很多不同的领域中，应用场景更是多种多样。如，运算、查找、排序、最优决策等。

什么是数据结构

数据结构（data structure），是数据的组织、管理和存储格式，其使用目的是为了高效地访问和修改数据。

数据结构包含数组、链表这样的线性数据结构，也包含树、图这样复杂的数据结构。

时间复杂度

什么是时间复杂度

时间复杂度是对一个算法运行时间长短的度量，用大O法表示，记作 T(n) = O(f(n)) 。

基本操作执行次数

即对某程序代码块执行的次数，记作 n。这个 n 可以是个常量，可以是线性的，可以是用对数计算的，也可以是用多项式计算的。

渐进时间复杂度

我们将程序的相对执行时间函数 T(n) 简化为一个数量级，这个数量级可以是 n、n²、n³ 等。

推导时间复杂度的几个原则：

• 如果运行时间是常数量级，则用常数1表示

• 只保留时间函数中的最高阶项

• 如果最高阶项存在，则省去最高阶项前面的系数

总结，常见的时间复杂度按照从低到高的顺序，包括 O(1)、O(logn)、O(n)、O(nlogn)、O(n2) 等。

空间复杂度

什么是空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量，用大O法表示，记作 S(n) = O(f(n)) 。

空间复杂度的计算

空间复杂度也同时间复杂度类似，有几种不同的增长趋势。

• 常量空间

  当算法的存储空间大小固定，和输入规模没有直接关系时，空间复杂度记作 O(1)。

• 线性空间

  当算法分配的空间是一个线性集合（如数组）时，并且集合大小和输入规模n成正比，则空间复杂度记作 O(n)。

• 二维空间

  当算法分配的空间是一个二维数组集合，并且集合的长度和宽度都与输入规模n成正比，则空间复杂度记作 O(n2)。

• 递归空间

  递归比较特殊，计算机在程序执行时会专门分配一块内存用来存储“方法调用栈”。包含入栈和出栈两个行为。执行递归操作所需的内存空间和递归深度成正比，因此，纯粹的递归操作空间复杂度也是线性的，如果深度为n，那么空间复杂度为 O(n)。

总结，常见的空间复杂度按照从低到高的顺序，包括 O(1)、O(n)、O(n2) 等。其中递归算法的空间复杂度和递归深度成正比。

时间与空间的取舍

由于计算机的运算速度和空间资源是有限的，所以人们需要评估算法的时间复杂度和空间复杂度，以达到对计算机的最优利用。但往往很多时候我们需要牺牲其中一方面来成全另一方面，在绝大多数情况下，时间复杂度更为重要些，毕竟追求更快的程序执行速度。