写在前面

前面学习完了Python基础内容后，从本节开始正式学习数据结构与算法相关内容。这是一个比较复杂的主题，一般分为初级、高级、以及专门的算法分析三个阶段来学习，因此我们也需要循序渐进。本节主要熟悉数据结构与算法中一般概念，然后熟悉算法效率分析的大O记法，知识结构如下图所示：





什么是算法？



1)算法的定义

算法(Algorithm)，指的是对特定问题求解步骤的一种描述。 

在数学上，它是运算步骤的有限序列，每一步代表执行某种运算。例如，手动计算两个整数和的算法描述为:  将两个数字对齐写在纸上，然后从个位开始，逐位求和，遇到和大于10则向高位进位，最终计算出两个数字之和。

在计算机中，算法是指令的有限序列，每条指定代表一个或者多个操作。例如，在12306网站完成车票查询、车票订购等任务，在计算机上都是由一系列算法实现。

在利用计算机求解问题的过程中，我们首先对问题进行建模，构造合适的算法，然后编写相关程序，流程如下(来自Introduction to Algorithm)：





2)算法的5大特性

对于一个算法，有5大特性，列出如下：

输入  一个算法有零个或者多个外部输入,注意可以没有输入。
输出  一个算法有一个或者多个输出，注意算法必定有某种形式的输出。
有穷性(Finiteness) 算法必须在有限步骤内完成。
确定性(Definiteness ) 算法中每条指定必须没有二义性（只有一种解释），在任何条件下，算法只有唯一的一条执行路径，对于相同的输入只能得到相同的输出。
可行性（Effectiveness ） 算法中描述的操作都可以通过已经实现的基本操作执行有效次实现，具有可行性。
3) 算法评价的因素

解决同一个问题有不同的方法，这些方法之间如何比较和选择成为一个关键。

例如去不同城市，可以选择的交通方式有火车、轮船、飞机、自驾、客运大巴、拼车等多种，这些不同的旅行方式，在舒适度、价钱、时间、安全等方面各有不同，需要从多个角度比较和选择。

评价算法好坏也有各种因素，主要包括下面几个因素：

正确性  是否正确地解决了问题？
可读性  算法主要是人来编写，其次才是机器执行。是否容易理解成为实现和维护的关键。
实现难度  算法是否容易实现？ 
存储开销 算法消耗的内存、外存储空间合理吗？
执行时间 算法执行时耗时能接受吗？
健壮性  程序遇到非预期输入能否做出合理反应? 例如简单的计算程序，遇到除0操作时，应该提醒用户错误，而不是程序崩溃掉。
什么是数据结构？



1）抽象数据类型

利用计算机求解问题的首要步骤是对问题进行建模，在建模的过程中，我们需要考虑到数据的输入、处理、输入等内容，算法描述了操作这些数据的具体流程，但是如何表示和存储问题模型中的数据则需要选择或者重新设计一种有利的结构。 

抽象数据类型（Abstract Data Types，ADT），是一种理论上的概念，它从逻辑层面，描述了可能值范围、允许的操作以及操作的行为表现。ADT与具体的实现细节无关（implementation-independent ）。例如整数，是一种ADT，它可能的值包括-1,0,1…，允许的操作包括加减乘除，以及大于、小于比较等。这些是数学上的模型，与在计算中具体如何表示无关。



2）数据结构

ADT是一种理论上的数学模型，而数据结构则是计算机上对这个抽象数据类型的实现，是实现层面的概念，由具体计算机语言以及这个语言的基础类型来实现。



3）ADT与数据结构的区别

从上面的定义可以看出了它们之间的差别。例如栈(Stack)是一种ADT，定义了它是先进后出的结构，支持的操作包括：入栈(push)、出栈(pop)、查看栈顶元素(top)、判断栈是否为空(empty)等4种操作。在计算上可以通过数组实现，称为ArrayStack，或者通过链表实现，称为LinkListStack。这两种具体实现称之为栈的数据结构。



算法效率评判标准

上面提到了，如果我们评价交通工具，我们可能会选择舒适度、时间、安全、价格等标准进行评判，与此类似，评判一个算法好坏也需要一些标准。

对一个算法进行空间和时间复杂度分析时，可以通过执行完程序后进行统计分析(事后统计方法)，也可以在未执行程序时就进行理论分析(事前估算分析估计方法)。对于同一个算法，在不同的机器上执行，受到处理器、机器字长、存储空间、指令集等的影响，运行时间存在差异，例如运行在“天河一号”超级计算机和普通PC上的程序，运行时间就可能大不相同；同一个算法，即使利用同一台机器来运行程序，但采用C或者Ada编写的程序就比用Basic或者Lisp编写的快约20倍。因此，事后统计分析的方法很多时候并不可靠(为特定设备编写的程序进行性能比较除外)，因此人们常常采用事先分析估算的方法。

既然事先估算方法，并没有实际执行程序，使用绝对单位的字节大小或者时间长度，显然是不可能的了，应该使用某种理论上的抽象标准。在上面我们提到了诸如可读性、正确性等因素，这些因素是每个好的算法都必须具备的，这些因素没有区分度，真正具有区分度的因素是空间复杂度(Space Complexity)和时间复杂度（Time Complexity）两个标准。这两个复杂度，一般随着问题输入的数据量，即与问题规模n，成某种函数关系，例如时间复杂度可以表示为:  
T(n)=f(n)。

在寻求这个函数关系时，我们首先找出一种被作为基本操作(Elementary operation)的运算，估算它的执行次数与n的关系。所谓基本操作指的是算法中对时间有着关键影响，与问题规模成正比的操作。例如检查一个元素x是否在一组数字a中，比较x与a中某个元素值是否相等的操作，就可以视为基本操作。

def find_in_array(array,val):
    """
    naive search algorithm
    :param array: input elements array
    :param val:  the value to search
    :return: index if found or -1
    """
    for i, x in enumerate(array):
        if x == val:   # 基本操作
           return i
    return -1

在上面的查找过程中，我们会遇到3种情形:

最坏情况下(worst-case)  要查找的元素在数组最后一个位置  T(n)=n
平均情况下(average case) 假定每个元素被查找的概率相同，则平均查找时需要的比较次数为: T(n)=∑ni=11n∗i=1+n2
最好情况下(best-case) 要查找的元素在数组第一个位置 T(n)=1
下面我们来重点熟悉时间复杂度的大O记法。



渐进分析法



1)什么是渐进分析法?

渐进分析法（Asymptotic Analysis）的目标是寻找到问题处理的时间与问题规模之间，随着问题规模变大时的一种上限和下限关系，通过上限我们了解到算法最坏情况，通过下限了解到算法最好的情况。


  
大O定义: 假设f(n)是算法时间复杂度的表示，而g(n)是其中最具影响的因子，如果: f(n)<=Cg(n)，对于所有的n>=n0,C>0,n0>=1都成立，则我们可以将f(n)记为: f(n)=O(g(n))


上面定义中，最具影响的因子，是复杂度表达式中，对结果影响最大的部分，例如:f(n)=5n2+2n+1，那么当n增大时，显然n2决定了f(n)的大小，这个因子就是上面定义中的g(n)。

f(n)与g(n)关系如下图所示:



例如,f(n)=3n+2, g(n)=n，令:f(n)<=Cg(n)⇒3n+2<=Cn，求解这个不定方程，可以得到: C=4,n>=2时:f(n)<=Cg(n)成立，因此有:f(n)=O(n)。

除了大O记法，还有一个表达复杂度下界的f(n)=Ω(g(n))记法，和表达复杂度平均界限的f(n)=Θ(g(n))记法，在算法分析中，我们通常考虑的是算法的上界，即最坏情况下的表现，对于另外两种记法，感兴趣地可以参考Asymptotic Notation，这里不再详细展开。



2)渐进分析法为什么有效？

引用一个来自[1]的例子，假设时间复杂度表示为: 
f(n)=n2+100n+logn10+1000，当n逐渐增大时，我们统计如下表所示:



从这个表可以看出，当n=1,10时，100n和1000所占比重较大；当n=100时，n平方和100n所占比重相同；当n>100后，n平方所占比重越来越大，到最后n=100000时，n平方接近100%。这就说明，使用n平方来近似表达f(n)的计算复杂度是完全可行的，也就是f(n)=O(n2)。



摊销分析法

摊销分析法(Amortized analysis)是从操作序列的角度分析算法的一种方法，考虑的是当执行某个操作n次时，运行时间和资源消耗的平均情况。

例如有一个动态分配的数组，当空间足够时，在尾部添加(push, 不是insert)一个新元素需要的T(n)=1；但是当空间不够时，需要重新分配连续空间，并把之前的元素复制到这块连续空间，这个时候添加元素的时间复杂度变成了T(n)=n。那么是不是添加n个元素时，最坏情况就变成了T(n)=n∗n=n2了？

答案是否定的，上面的分析过于悲观，因此需要利用摊销分析法，对插入n个元素的复杂度进行分析。在上面插入过程中，一个重要的事实是: 并不是每次插入，都要复制元素，仅当空间不足时才会进行复制操作，而这个复制操作引起的开销在这n次操作中平摊下来就变小了。

假设我们数组初始大小为1，自增因子为2，那么这个变化过程如下表格所示(例子整理自Algorithmic Complexity):

添加序号
  
复制次数
  
一共消耗
  
数组旧的大小
  
数组新的大小
1
  
0
  
1
  
1
  
-
2
  
1
  
2
  
1
  
2
3
  
2
  
3
  
2
  
4
4
  
0
  
1
  
4
  
-
5
  
4
  
5
  
4
  
8
6
  
0
  
1
  
8
  
-
7
  
0
  
1
  
8
  
-
8
  
0
  
1
  
8
  
-
9
  
8
  
9
  
8
  
16
假设T(i)=1+Ci,其中Ci为复制元素的开销:

Ci={2m,i=2m+1(m=0,1,2...)0,其他情况

假设添加n个元素时数组最多需要扩容m次，则有: 2m≥n,m取整数，则有: m≤logn2+1

则n次添加的代价之和为: 
T(n)=∑ni=1T(i)≤n+∑mj=12j−1=n+2n−1=3n−1

对n次添加进行平摊后，添加一个元素的时间复杂度为:T(n)/n=O(1)

这个分析表明，虽然向动态数组添加元素存在O(n)的情况，但是平摊下来每个添加操作的时间复杂度仍然为O(1)，因此不用过于悲观。上面的这种分析方法称之为总和法(Aggregate Method)。


  
注意： 这里平摊后的时间复杂度，和上面渐进分析得出的平均情况复杂度，并不是同一个概念。渐进分析的平均情况，使用了概率假设，例如假设数组中每个元素被查找的概率相同这种假定，但是摊销分析并没有对输入进行任何假设。摊销分析强调的是对一个操作执行多次时的序列进行分析，将这种总的时间复杂度平摊到每一个操作之上从而得出最终的复杂度。


摊销分析方法，除了上面介绍的这种总和法，还有其他方法，感兴趣地可以自行参考Amortized Analysis。

本节介绍了数据结构与算法中的一般概念，以及算法分析中常用的大O记法和摊销分析方法，这只是一个入门，算法分析一般作为专门课程是一个需要深入学习的主题，已经超过了本节范畴，后面会循序渐进地进行相关学习。



参考资料

[1] 数据结构与算法 c++版 第三版   Adam Drozdek编著  清华大学出版社
[2]  数据结构  严蔚敏 吴伟明  清华大学出版社
Amortized analysis
Amortized Analysis
Introduction to Algorithm
Abstract data type vs Data Type vs Data Structure, with respect to object-oriented programming
Abstract data type
Algorithmic Complexity

学习起因
曾经有一次在逛V2EX时，碰到这么一个帖子。
发帖的楼主大学没有高数课程，出去工作时一直在从事前端的工作。感觉到数学知识的匮乏，所以想补一补数学。
看了看帖子，感觉和我很像，因为我的专业是不开高数的，我学的也是前端。也同样感觉到了数学知识匮乏所带来的困顿。同时因为自己的数学思维实在是不怎么好，所以决定努力补习数学与计算机基础知识。
当时也有人说:"前端需要什么数据结构与算法"，但是对于这个事情我有自己的看法。
我并不认为前端不需要算法之类的知识，在我看来前端具备坚实的计算机基础，对自身发展是极其有利的。我想做程序员。而不是一辈子的初级前端和码农。
也算是给自己的勉励吧。毕竟基础决定上限，再加上自己对计算机真的很感兴趣，所以学起来就算很累，但也是很幸福的。于是去网上选购了《学习JavaScript数据结构与算法》这本书，配合着去图书馆借阅的《大话数据结构》，开始了数据结构与算法的初步学习。
这本书讲的内容很是不错，清晰易懂。同时用JavaScipt语言实现，学起来的难度低。值得一看呢。
栈
书中前两章是对JavaScipt基础与数组常用操作的讲解，如果不清楚的话,推荐去看看下面这篇博客。
接下来就是数据结构的第一部分，栈。
栈是一种遵从后进先出原则(LIFO,全称为Last In First Out)的有序集合。栈顶永远是最新的元素。
举个例子就是:栈就像放在箱子里的一叠书 你要拿下面的书先要把上面的书拿开。(当然，你不能先拿下面的书。)
看图示也可明白。
JavaScipt中栈的实现
首先，创建一个构造函数。
/**
* 栈的构造函数
*/
function Stack() {
// 用数组来模拟栈
var item = [];
}
栈需要有如下的方法:
push(element(s)): 添加几个元素到栈顶
pop(): 移除并返回栈顶元素
peek(): 返回栈顶元素
isAmpty: 检查栈是否为空，为空则返回true
clear: 移除栈中所有元素
size: 返回栈中元素个数。
print: 以字符串显示栈中所有内容
push方法的实现
说明: 需要往栈中添加新元素，元素位置在队列的末尾。也就是说，我们可以用数组的push方法来模拟实现。
实现:
/**
* 将元素送入栈，放置于数组的最后一位
* @param  {Any} element 接受的元素，不限制类型
*/
this.push = function(element) {
items.push(element);
};
pop方法的实现
说明: 需要把栈顶元素弹出，同时返回被弹出的值。可以用数组的pop方法来模拟实现。
实现:
/**
* 弹出栈顶元素
* @return {Any} 返回被弹出的值
*/
this.pop = function() {
return items.pop();
};
peek方法的实现
说明: 查看栈顶元素，可以用数组长度来实现。
实现:
/**
* 查看栈顶元素
* @return {Any} 返回栈顶元素
*/
this.peek = function() {
return items[items.length - 1];
}
其余方法的实现
说明: 前三个是栈方法的核心，其余方法则在此一次性列出。因为下文要讲的队列，会与这部分有很大重合。
实现:
/**
* 确定栈是否为空
* @return {Boolean} 若栈为空则返回true,不为空则返回false
*/
this.isAmpty = function() {
return items.length === 0
};
/**
* 清空栈中所有内容
*/
this.clear = function() {
items = [];
};
/**
* 返回栈的长度
* @return {Number} 栈的长度
*/
this.size = function() {
return items.length;
};
/**
* 以字符串显示栈中所有内容
*/
this.print = function() {
console.log(items.toString());
};
实际应用
栈的实际应用比较多，书中有个十进制转二进制的函数。(不懂二进制怎么算的话可以百度)下面是函数的源代码。
原理就是输入要转换的数字，不断的除以二并取整。并且最后运用while循环，将栈中所有数字拼接成字符串输出。
/**
* 将10进制数字转为2进制数字
* @param  {Number} decNumber 要转换的10进制数字
* @return {Number}           转换后的2进制数字
*/
function divideBy2(decNumber) {
var remStack = new Stack(),
rem,
binaryString = '';
while (decNumber > 0) {
rem = Math.floor(decNumber % 2);
remStack.push(rem);
decNumber = Math.floor(decNumber / 2);
}
while (!remStack.isAmpty()) {
binaryString += remStack.pop().toString();
}
return binaryString;
};
到此而言，栈的学习就告一段落了。因为源代码中注释较多，所以这儿就不贴出源代码的内容了。有兴趣的可以自己下载查看。
队列
队列与栈是很相像的数据结构，不同之处在于队列是是先进先出(FIFO:First In First Out)的。
举个例子: 火车站排队买票，先到的先买。(插队的不算)，是不是很好理解了~
JavaScipt中队列的实现
队列的实现和栈很像。首先依然是构造函数:
/**
* 队列构造函数
*/
function Queue() {
var items = [];
}
队列需要有如下的方法:
enqueue(element(s)): 向队列尾部添加几个项
dequeue(): 移除队列的第一项(也就是排在最前面的项)
front(): 返回队列的第一个元素，也就是最新添加的那个
其余方法与队列相同
enqueue方法的实现
说明: 向队列尾部添加几个项。
实现:
/**
* 将元素推入队列尾部
* @param  {Any} ele 要推入队列的元素
*/
this.enqueue = function(ele) {
items.push(ele);
};
dequeue方法的实现
说明: 移除队列的第一项。
实现:
/**
* 将队列中第一个元素弹出
* @return {Any} 返回被弹出的元素
*/
this.dequeue = function() {
return items.shift()
};
front方法的实现
说明: 返回队列的第一个元素，也就是最新添加的那个。
实现:
/**
* 查看队列的第一个元素
* @return {Any} 返回队列中第一个元素
*/
this.front = function() {
return items[0];
};
以上的三个方法，就是队列这种数据结构的核心方法了。其实很好理解的。
实际应用
书上的是个击鼓传花的小游戏。原理就是循环到相应位置时，队列弹出那个元素。最后留下的就是赢家。
源代码如下:
/**
* 击鼓传花的小游戏
* @param  {Array}  nameList 参与人员列表
* @param  {Number} num      在循环中要被弹出的位置
* @return {String}          返回赢家(也就是最后活下来的那个)
*/
function hotPotato(nameList, num) {
var queue = new Queue();
for (var i = 0; i < nameList.length; i++) {
queue.enqueue(nameList[i]);
}
var eliminated = '';
while (queue.size() > 1) {
for (var i = 0; i < num; i++) {
queue.enqueue(queue.dequeue());
}
eliminated = queue.dequeue();
console.log(eliminated + " Get out!")
}
return queue.dequeue()
}
具体实现，有兴趣的同学可以自己下载源代码，试一试。
队列的学习到此就告一段落了。下一期将讲述另外一种数据结构: 链表。
感想
很多时候看书，直接看算法导论或者一些数据结构的书，都是很迷糊的。后来才发现，看书从自己能看懂的开始，由浅入深才是适合自己的学习方式。
前端路漫漫，且行且歌~

算法的复杂度是个不错的知识点，但是它与我们这门算法的课程有什么关系呢？我们慢慢来看。

算法学（Algorithmics）是设计和研究算法的科学，它的历史可比计算机科学的历史久远多了，但今天算法学却几乎全由计算机科学家实践。

算法学是一个非常广泛的领域，需要不少数学知识。当然了，并非所有计算机科学家都需要成为天才的算法学家。从算法的角度来看，大多数程序员面临的问题实际上非常简单。

但我们有时需要实现一些更复杂的东西。在这种情况下，算法方面的基本知识就会显得非常有用。我们并不要求你发明一种革命性的新算法并给出其复杂度的具体证明，但为了能够准确地使用那些在网络上或软件库中找到的算法，还是有必要接受一下“基础培训”的。

懂算法会让你更有效率，能够更好地理解你所要解决的问题，也不会写出不规范的代码：有一些代码尽管可以正常运行，但从算法的角度来看却是不合理的。一个经验不丰富的程序员可能会直接使用这些不合格的算法（他会想：“代码能运行，所以应该没什么问题”），但你因为懂算法，就能很快发现代码的问题，并改写出一个优秀得多的版本。

听我说了这些，你可能有点跃跃欲试了。下面是两个简单的对于算法复杂度的研究题，它们可以让你更准确地了解算法复杂度的作用。

寻找最大和最小的元素


问题 1：有一个正整数列表，我们想要找到列表中最大的整数。


这个问题的经典解法如下：遍历此列表，并一直保存迄今为止发现的最大元素，称其为“当前最大值”。

我们可以将此算法描述为：


一开始，“当前最大值”等于 0。我们用列表中每一个元素去和“当前最大值”做比较，如果当前遍历到的元素比“当前最大值”更大，则将“当前最大值”设为当前元素的值。在遍历完整个列表后，“当前最大值”就真的“实至名归”了。


下面我们给出此算法的一种实现，是用“世界上最好的编程语言” PHP 来实现的（当然，你也可以用其他编程语言来实现）：

<?php
function max($list) {
   $current_max = 0;
   foreach ($list as $item)
       if ($item > $current_max)
           $current_max = $item;
   return $current_max;
}
?>


我们可以快速验证此算法是正确的：我们只需要确认在此算法执行时，“当前最大值”总是等于到目前为止所遍历到的列表元素里最大的那个值。

我们也注意到此算法是会“结束”的，它不会陷入无限循环：此算法遍历完整个列表，然后停止。这看起来像一个不重要的细节，但实际上有一些编程语言里是可以表示无限多元素的列表的：在这种情况下，我们的算法是不正确的。

现在让我们研究此算法的复杂度。我们要考虑哪些操作呢？显然，大部分工作都在于将当前元素与“当前最大值”进行比较（毕竟，“当前最大值” current_max 的初始化（初始化为 0）并不占多少运行时间），因此我们计算“比较操作”的次数，将其作为此算法的操作数。

算法的执行时间取决于哪些参数呢？可以想见，执行时间并不依赖于列表中每个元素的值（在此，我们假设两个整数的比较时间是恒定的，不论它们的值是多少）。因此，我们用元素列表的长度 N 来量化输入。

对于一个包含 N 个元素的列表，我们要进行 N 次比较：每个元素都与“当前最大值”进行一次比较。因此，算法的时间复杂度是 O(N)：它的执行时间是呈线性的，与列表的元素数目 N 成正比。

那么，此算法的空间复杂度是多少呢？此算法使用了一个列表，里面的元素占用了一定的内存空间。但是，这个列表在我们查找其最大元素之前就已经存在了，它所占用的内存空间并不是由我们的算法分配的，因此我们说此列表的元素数目 N 并不会被考虑到算法的空间复杂度的计算中，我们只考虑由我们的算法直接申请的内存。

而我们的算法直接申请的内存空间几乎可以忽略不计，因为最多就是占用了一个临时变量（current_max），用以存储“当前最大值”。因此，我们的算法所占用的内存空间不依赖于列表的长度： （我们将空间复杂度记为 O(1)，表示它不依赖于 N）。

对于我们的算法，现在只剩下一个小细节要注意了：如果我们的列表是空的，那么返回的最大值将是 0。要说“一个空的列表的最大值是 0” 显然不一定是正确的：在某些情况下，如果列表是空的，最好返回一个错误。

因此我们可以改进一下我们的算法：我们不再为“当前最大值”赋初值为 0，而是以列表的第一个元素（如果该列表为空，则返回一个错误）作为“当前最大值”的初始值。然后，我们从第二个元素开始比较。

经过改进后的算法执行 N-1 次比较（因为我们不必将第一个元素与它自己进行比较）。不过，这并没有改变算法的时间复杂度：N 和 N-1 之间的时间差并不依赖于 N，它是恒定的，因此我们可以忽略它：两种算法具有相同的时间复杂度，它们都是时间线性的（时间复杂度是 O(N) ）。

最后，我们注意到第二个算法也适用于负数（如果列表的所有元素都是负数，第一个算法会返回 0，这显然不正确）。因此改良后的第二个算法更通用，也更好。

当然了，查找列表中最小值的算法和查找最大值是类似的，我们就不赘述了。

寻找不重复的元素

现在我们来看第 2 个问题。


问题 2：有一个列表 1，其中包含重复项（多次出现的元素）：我们想要构建一个包含与列表 1 相同元素的列表 2，但是列表 2 中每个元素只重复出现一次。


例如，列表 1 里有以下元素：

AABCDBCA


则列表 2 将包含以下元素：

ABCD


你想到解决这个问题的算法了吗？在阅读我的解决方案之前，请自己思考一下。

我的解决方案

我的算法如下：


对于给定的包含重复元素的列表 L，我们要构建一个新的列表 U（取英语 Unique（“独一无二的”）的第一个字母），列表 U 一开始是空的，我们需要往里面填充元素。我们遍历列表 L，对于列表 L 中的每一个元素，我们确认一下它是否存在于列表 U 中（可以用与之前的查找最大元素类似的算法，毕竟就是逐一比较元素嘛）。如果列表 L 中遍历到的元素还不在列表 U 中，就将这个元素添加进列表 U 中；如果已经存在于列表 U 中，就不添加。遍历完列表 L 后，列表 U 中就拥有了和列表 L 相同的元素，只是这些元素都是不重复出现的。



练习： 使用你喜欢的编程语言来实现上述从列表中提取不重复元素的算法。


复杂度

这个算法的复杂度是多少？如果你充分理解了之前查找列表最大值的算法的复杂度的计算，那么这对你来说应该很简单。

对于给定列表 L 中的每个元素，我们都会执行遍历列表 U 的操作，因此执行的操作数与列表 U 包含的元素数目有关。

但问题是：列表 U 的大小在遍历给定列表 L 的过程中会发生变化，因为我们会添加元素进列表 U。当我们遍历到列表 L 中的第一个元素时，列表 U 还是空的（因此我们不执行任何比较操作）；当我们遍历到列表 L 的第二个元素时，列表 U 有 1 个元素，所以我们要再执行一个比较操作。

但是当我们遍历到列表 L 中的第三个元素时，我们就变得不是那么肯定了：如果列表 L 中的前两个元素是不相同的，它们都被添加到 U 中，在这种情况下我们要执行 2 次比较操作（将列表 L 中的第三个元素分别与列表 U 中的两个元素作比较）；如果前两个元素是相同的，那么列表 L 中的第二个元素就没有被添加到列表 U 中，只执行 1 次比较操作。

正如我们的课程里已经说过的，复杂度的计算需要考虑在“最坏的情况”（worst case）下：也就是执行的操作数目最多时的复杂度。因此，我们将认为给定列表 L 的所有元素都是不相同的。

在“最坏的情况”下，我们将给定列表 L 的所有元素逐一添加进列表 U 中。假设给定列表 L 一共有 N 个元素，在遍历到给定列表 L 的第 N 个元素时，我们已经向列表 U 添加了 (N-1) 个元素了，因此这时要做 (N-1) 次比较操作。

所以我们总共要做的比较操作数是 0 + 1 + 2 + … + (N-1) 。开始时的操作数少，越到后面做的操作越多（有点像人生，出生时责任比较少，慢慢地责任越来越大，要处理的事情也越来越多，不过也说明你在成长，毕竟“能者多劳”）。

上面这一串数字相加，得到的总操作数是 N * (N - 1) / 2（这个不难，是数学里面的等差数列求和公式），由于我们在计算复杂度时考虑的是 N 很大的情况，上面的结果可以约等于 N * N / 2，即 N2 / 2 个操作。

因此，我们的算法具有 O(N2) 的时间复杂度（我们去除了常数因子 1/2）。我们也可以称 O(N2) 为“二次/平方”的复杂度（正如我们称 O(N) 具有“线性”的复杂度）。

与之前那个查找最大元素的算法比起来，现在这个算法除了速度较慢（时间复杂度较高）之外，还具有更高的空间复杂度：我们构建了一个最初不存在的列表 U（因此申请了内存空间）。

在最坏的情况下，列表 U 还具有与给定列表 L 一样多的元素：因此将为 N 个元素分配空间，这使得空间复杂度为 O(N)。之前查找最大元素的算法的空间复杂度是恒定的（O(1)），但现在这个算法的空间复杂度却是线性的（O(N)）。

该算法只需要比较元素，因此被操作的元素并不一定要是整数：我们可以用相同的算法来消除单词列表中重复的单词，重复的浮点数，等等。因此，许多算法是与使用的元素的具体类型无关的。

寻找不重复的元素：另一种方法

寻找不重复的元素，其实还有另一种算法（聪明如你可能也想到了）：我们可以先对给定列表 L 中的元素进行排序，使得所有重复的元素都相邻，这样排除重复元素将变得很简单。

比如给定列表 L 初始是这样的：

AABCDBCA


我们可以在构建列表 U 前，先对列表 L 进行排序，使其变成下面这样：

AAABBCCD


这样，我们之后构建列表 U 的算法就简单了。


算法如下：只需遍历排序后的列表 L，并记住最近一次遍历到的那个元素。如果当前元素与前一个元素相同，则这个元素是重复的，就不要把它包含在不重复元素的列表 U 中。


如果重复的元素彼此不相邻，则上述算法不再有效。因此我们必须先对列表进行排序。

这个新的算法的时间复杂度是什么？消除重复是在列表的单次遍历中完成的，因此是线性的（ O(N)）。但由于我们必须先对列表进行排序，因此第一步排序的操作也必须被考虑进这种新算法的总复杂度中。

当然了，在这里提到列表的排序还稍微有一些太早了，因为我们在之后的课程里才会讲到排序算法。

尽管目前我们还没有学习排序算法和它们的复杂度，但我还是想说一下这个新算法的复杂度问题。

事实证明，这种算法的复杂度取决于排序的复杂度：因为，排序基本上会执行 N2 个操作，这远远超过我们之后的构建列表 U 时的 N 个操作，所以整体复杂度是 O(N2)。

然而，也存在更高端的排序算法，虽然仍然执行多于 N 个操作，但比 N2 要少得多。

我们将在之后的课程里学习排序算法，目前你只需要知道这个多了一步排序的新算法比旧算法更有效，也更“高级”。

“在列表中搜索指定元素”与“找出列表中最大/小值的元素”是非常相似的算法，都是线性时间的（算法的时间复杂度是 O(N)），空间复杂度都是 O(1)。

消除列表中的重复元素的算法更复杂一些，因为最简单的算法在时间上具有平方的时间复杂度（O(N2)），其空间复杂度具有线性（O(N)）。

我希望这些更具体的研究能让你确信算法学和算法复杂度还是很有用的。现在你也应该已经习惯“算法”，“时间复杂度”，“空间复杂度”这些基本概念了。

 

读书给我更多的憩息，引导我散步在别人的知识与灵魂中。
继续学习数据结构啦！
至于为什么在数据结构里还会谈到算法，毕竟数据结构和算法本就在写代码时是分不开的，所以在学数据结构时也就会谈到亿点点算法啦，哈哈哈。
算法其本质就是数学，所以大家在学习算法时需要多去理解它，而不是说自己记下代码怎么写就行，这样会很容易就忘记的。别问小编为什么会这样说，问就是小编也试过。


关于数据结构和算法的关系在文章开头已提到了哈，下面我们介绍介绍高斯。
关于高斯

大家都知道高斯是很聪明的一个人，也是著名的数学家，而我们算法其本质也就是数学，所以这其中的种种大家也就都懂啦。
比如我们计算从1加到100，大家最先想到简单的方法可能就是直接加。
然后根据我们的经验就知道这其实是有简便方法的，比如有一种便是对称相加。
当然，高斯想到了另一种，将100加上1，99加上2…一直到1加上100，最后再除以二，在计算机运行也就是一个公式的步骤，其算法类似于我们学过的等差数列，这样当数学和计算机相遇时便构成了算法。
什么是算法：算法是解决特定问题步骤求解的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。
首先算法的特性有五个的基本特性，分别是：输入，输出，有穷性，确定性和可行性。
1.输入输出：算法具有零个（如打印hello，word）或多个输出，至少有一个或多个输出，算法是一定需要输出的。就和人们表达一样嘛，你有再好的想法，不表达出来又有什么用呢。
2.有穷性：指算法在执行有限的步骤之后，自动结束而不会出现无线循环，并且每一个步骤都在可接受的时间内完成。（防止死循环）
3.确定性：算法的每一步骤都具有确定的含义，不会出现二义性。只执行一条路径，相同的输入只能有唯一的输出结果，也就是说算法的每个步骤都必须是无歧义的。
4.可行性：算法的每一步都必须是可行的，每一步都能通过执行有限的次数完成。
1.正确性：算法的正确性是指算法至少应该具有输入，输出和加工处理无歧义性，能正确反映问题的需求，能够得到问题的正确答案。
那么何为”正确“呢，在程序设计时一般分为以下几点：
算法程序没有语法错误（基本）；

算法程序对于合法的输入数据能够产生满足要求的输出结果；

算法程序对于非法的输入数据能够得出满足规格说明的结果（判断算法是否正确）；

算法程序对于精心选择的，甚至刁难的测试数据都有满足要求的输出结果（最难）。
2.可读性：算法设计的另一目的是为了便于阅读，理解和交流。可读性的提高非常有助于人们理解算法，有些可读性很低的算法往往可能会隐含着错误，且不易被发现。比如当你的同事准备接你写的代码时，发现你的代码很难让人去理解，那么这不就将公司的效率拉得极低么。
3.健壮性：当输入不合法时，算法也能做出相应处理，而不是产生异常或莫名其妙的结果 。
4.时间效率高且存储量低：时间效率指的是算法的执行时间，也就是说，在解决同一个问题时，算法执行的时间越短，那么它的效率也就越高。存储量指的是在算法执行时所需要的最大存储空间，主要指算法程序运行时所占用的内存或外部硬盘存储空间。就比如大家在生活中都希望花最少的钱，用最短的时间从而办最大的事，算法亦是。