程序 = 算法 + 数据结构
一、算法
1. 基本概念
计算机科学中的算法指的就是计算机执行的指令。
算法是计算机处理信息的本质，因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务，如计算职工的薪水或打印学生的成绩单。
一般地，当算法在处理信息时，会从输入设备或数据的存储地址读取数据，把结果写入输出设备或某个存储地址供以后再调用。
-----------
输入 --> | 算法 | --> 输出
-----------
算法的核心是创建问题抽象的模型和明确求解目标，之后可以根据具体的问题选择不同的模式和方法完成算法的设计。
2. 示例
求一个数组中的最大值：
int max(int *array, int size) {
int max = *array; // 默认第 0 个最大
int i;
for (i = 1; i < size; i++) {
if (array[i] > max) {
max = array[i];
}
}
return max;
}
3. 复杂度
采用不同的算法，会有不同的效率。因此，知道某个算法的运行速度和占用的内存空间，对于选择正确的算法来解决问题非常有帮助。
3.1 时间复杂度
算法的时间复杂度是指算法需要消耗的时间资源。
一般来说，计算机算法是问题规模n 的函数f(n)，算法的时间复杂度也因此记做：
T(n) = O(f(n))
算法执行时间的增长率与f(n) 的增长率正相关，称作渐近时间复杂度（Asymptotic Time Complexity），简称时间复杂度。
3.2 空间复杂度
算法的空间复杂度是指算法需要消耗的空间资源。
其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。
同时间复杂度相比，空间复杂度的分析要简单得多。
3.3 大 O 表示法
-
什么是大 O 表示法？
我们常常会听到有人说，“这个算法在最糟情况下的运行时间是 O(n^2) 而且占用了 O(n) 大小的空间”，他的意思是这个算法有点慢，不过没占多大空间。
这里的O(n^2)和O(n)就是我们通常用来描述算法复杂度的大 O 表示法。
大 O 表示法能让你对一个算法的运行时间和占用空间有个大概概念。 -
大 O 表示法怎么看？怎么用？
假设一个算法的时间复杂度是 O(n)，n 在这里代表的意思就是数据的个数。举个例子，如果你的代码用一个循环遍历 100 个元素，那么这个算法就是 O(n)，n 为 100，所以这里的算法在执行时就要做 100 次工作。 -
常见的时间复杂度有：
常数阶O(1)，对数阶O(log2n)，线性阶O(n)，线性对数阶O(nlog2n)，平方阶O(n2)，立方阶O(n3)，...， k次方阶O(nk)，指数阶O(2n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。
详见 Swift Algorithm Club: 大 O 表示法 -
说明：
- 大部分情况下你用直觉就可以知道一个算法的大 O 表示法
- 大 O 表示法只是一种估算，当数据量大的时候才有用
- 这种东西仅仅在比较两种算法哪种更好的时候才有点用。但归根结底，你还是要实际测试之后才能得出结论。而且如果数据量相对较小，哪怕算法比较慢，在实际使用也不会造成太大的问题。
4. 常用算法
- 排序
- 插入排序
- 选择排序
- 快速排序
- 冒泡排序
- 查找
- 线性查找
- 二分法
二、数据结构
1. 简介
在计算机科学中，数据结构是计算机中存储、组织数据的方式。
数据结构往往与算法是分不开的，因为算法所要处理的对象就是数据结构中的数据。
正确的数据结构选择可以提高算法的效率。
在计算机程序设计的过程里，选择适当的数据结构是一项重要工作。许多大型系统的编写经验显示，程序设计的困难程度与最终成果的质量与表现，取决于是否选择了最适合的数据结构。
2. 常用的数据结构
- 数组
- 队列
- 链表
- 树
- 哈希表
- 集合
- 图
网友评论