《程序员必会的40种算法》

数据密集型

数据密集型算法旨在处理大量数据，其处理需求相对简单。压缩大型文件就是一个典型的例子。

对于这类算法，待处理数据的规模远大于引擎的内存规模，因此可能需要开发一个迭代处理设计来高效的处理数据。
计算密集型

计算密集型具有大量计算需求而不涉及大量数据。一个简单的例子就是寻找大素数的算法。寻找恰当策略将算法划分为不同的阶段，使其中至少有一个阶段是可以并行化的，这是最大限度提升算法性能的关键。
数据和计算密集型

有些算法需要处理大量数据，同时也有大量计算需求。实时视频信号上的情感分析算法就是一个很好的例子，其中数据和计算需求都很大。这类算法是最耗费资源的算法，需要对算法进行精心设计，并对可用资源进行智能分配。

1.2.1 数据维度

将算法从问题的数据维度上进行归类，需要查看数据的体积、速度、多样性

体积

要处理的数据的预期规模
速度

使用该算法是新数据生成的预期速度。可以为0
多样性

量化了所设计算法预计要处理多种不同类型的数据。

1.3 性能分析

算法的性能分析是算法设计的重要部分。估计算法性能的方法之一是分析算法的复杂度。

复杂度理论研究算法的复杂程度。任何有用的算法应该具备以下三个关键特征：

算法应该是正确的；
好算法应该是易懂的；
好算法应该是高效的

有两种方法用于量化分析算法的复杂度：

空间复杂度：估计算法运行对内存的需求
时间复杂度：估计算法运行的时间

1.3.1 空间复杂度分析

空间复杂度分析就是估计算法在处理输入数据时所需的内存量。

在处理输入数据的同时，算法需要在内存中存储一些临时的数据结构。算法的设计方式将会影响这些数据结构的数量、类型和规模。在分布式计算时代，需要处理的数据量越来越大，空间复杂度分析变得日益重要。这些数据结构的规模、类型和数量将决定对于底层硬件的内存需求

1.3.2 时间复杂度分析

时间复杂度分析就是依据算法结构来估计算法完成其指定工作所需的时间。与空间复杂度不同，时间复杂度并不取决于运行算法的任何硬件设施，而是完全取决于算法本身的结构。

时间复杂度分析的总体目标是试图回答下列重要问题：算法是否具有良好的可扩展性？算法在处理更大规模数据集时性能如何变化？

在很多情况下，设计算法的方法可能不止一种，此时，时间复杂度分析的目的为：给定某个问题和多种算法，从时间效率来看，使用哪种算法效率最高？

计算算法的时间复杂度有以下两种基本方法：

实现算法后的分析方法：这种方法先分别实现各种候选算法，再对其性能进行比较。
实现算法前的理论方法：这种方法在运行算法前用数学方法近似计算每个算法的性能。

1.3.3 性能评估

典型算法的性能都取决于作为输入提供给它的数据的类型。例如，如果在待求解问题中数据已经排序，则该算法执行的速度可能会快得惊人。如果用排序后的输入作为基准来对特定算法进行测试，则将得到不真实的、过好的性能测试结果，而这个结果在大多数情况下并不能够反映算法的实际性能。为了处理算法对输入数据的这种依赖性，我们在进行性能分析时需要考虑各种不同情况。

最好复杂度

在最好复杂度中，输入数据经过组织，能够得到算法的最佳性能。最好复杂度分析得出算法性能的上界。

最坏复杂度

评估算法性能的第二种方法是尝试找到算法在给定条件下完成工作所需的最大可能时间。最坏复杂度分析非常有用，因为我们可以保证无论在何种条件下算法的性能总是优于所得的分析结果。在评估算法在处理更大规模数据集的复杂问题时，最坏复杂度分析特别有用。最坏复杂度给出了算法性能的下界。

平均复杂度

平均复杂度分析先将各种可能的输入划分为不同的组，然后从每组中选择具有代表性的一个输入来分析算法性能，最后计算出算法在各组输入上的平均性能。平均复杂度并不总是准确结果，因为它需要考虑算法输入的所有不同组合和可能性，但这并不总是容易做到的。

1.3.4 选择算法

你怎么知道哪种方案更好？你怎么知道哪种算法运行得更快？时间复杂度和大O记号（大O表示法）为回答这种问题提供了有效手段。

为了理解它的作用，我们举一个简单的例子：对一个数字列表进行排序。有几种可用的算法可以完成这项工作，问题是如何选择合适的算法。

如果列表中数字不多，那我们选择哪种算法来排序根本无关紧要。但是如果列表规模非常高，则选择合适的算法就会产生区别。一个很差的算法甚至可能需要几个小时才能完成列表排序任务，而一个设计较好的算法则可能仅用几秒完成了任务。因此，在大规模输入数据集上，投入时间和精力展开性能分析，选择合理设计的算法来高效地完成要求的任务是非常有意义的。

1.3.5 大O记号

大O记号用于量化表示各种算法在输入规模增长时的性能，它是最坏复杂度分析中最常用的方法之一。

常数时间复杂度（O（1））

如果算法运行时间是独立于输入数据规模的相同值，则称其运行时间是常数时间，表示为O(1)。

线性时间复杂度（O(n)）

如果算法的执行时间与输入规模成正比，则称该算法具有线性时间复杂度，表示为O(n)。

平方时间复杂度（O(n²)）

如果算法的执行时间与输入规模的平方成正比，则称该算法的运行时间为平方时间。

对数时间复杂度（O(log n)）

如果算法的执行时间与输入规模的对数成正比，则称该算法的运行时间为对数时间。在时间复杂度为O(log n)的算法中，随着算法的每一轮迭代，输入规模都会以常数倍数递减。

1.3.6 验证算法

验证算法指的是确保它是为待求解问题找到了一个数学求解方案。验证过程应该在尽可能多的输入值和输入类型上检验求解结果。

1.4 验证算法

验证算法指的是确保它是为待求解问题找到了一个数学求解方案。验证过程应该在尽可能多的输入值和输入类型上检验求解结果。

1.4.1 精确算法、近似算法

精确算法：预计在不引进任何假设或近似的情况下产生精确解。

近似算法：当问题的复杂度过大，在给定的资源下难以处理时，我们会通过一些假设来简化问题。

1.4.2 可解释性

有些特征会直接或间接用于得到某种特定决策，能够准确识别出这些特征的能力，称为算法的可解释性。算法在临界条件下使用，需要评估算法是否存在偏差和偏见。如果算法可能影响到与人们生活相关的决策，则算法的伦理分析将会成为验证过程中的标准环节。

2. 算法中的数据结构

算法需要必要的内存数据结构，用于在执行时保存临时数据。选择恰当的数据结构对算法高效执行至关重要.

2.1 python中的数据结构

列表（list）：有序的可变元素序列。

元组（tuple）：有序的不可变元素序列。

集合（set）：无序元素序列（其中元素不重复）。

字典（dictionary）：无序的键值对序列。

数据帧（Data Frame）：存储二维数据的二维结构。

2.1.1 列表

在Python中，列表是用来存储可变元素序列的主要数据结构。列表中储存的元素不必是同一类型的。


a = [1,3,'你好','Hello',[2,4],{2,5}]
print(type(a))  # a的类型
print(a)
----------------------------------------------------------------
<class 'list'>
[1, 3, '你好', 'Hello', [2, 4], {2, 5}]

列表是Python中非常流行的一维数据结构之一。它在各个场景中都十分有用。

迭代：Python中允许for循环对列表里的每个元素进行迭代


a = [1,3,'你好','Hello',[2,4],{2,5}]
for i in a:
    print(i)
1
3
你好
Hello
[2, 4]
{2, 5}

lambda函数：也称匿名函数。lambda函数在算法中特别重要，其提供了动态创建函数的能力。

过滤数据：为了过滤数据，需要定义一个谓词，说明需要完成什么工作，他是输入一个参数并返回一个布尔值的函数


a = [1,2,3,4,5,6,7,8,9]
b = filter(lambda i:i % 2 == 0,a)
print(list(b))
----------------------------------------------------------------
[2, 4, 6, 8]

在这段代码中，我们使用了lambda函数来过滤一个列表，该函数指定了过滤标准。filter函数旨在依据定义的标准从序列中过滤掉不符合标准的元素。

数据转换：map()函数可用于lambda函数进行数据转换


a = [1,2,3,4,5,6,7,8,9]
b = map(lambda x : x * 2,a)
print(list(b))
----------------------------------------------------------------
[2, 4, 6, 8, 10, 12, 14, 16, 18]

数据聚合:可以用reduce()函数，该函数会对循环运行定义的函数，对列表中每对元素进行处理


from functools import reduce
def doSum(x1,x2):
    return x1 + x2
a = [1,2,3,4,5,6,7,8]
x = reduce(doSum,a)
print(x)
----------------------------------------------------------------
36

列表的时间复杂度

可用大O表示法来表示

功能时间复杂度
插入一个元素 O(1)
删除一个元素 O(n)
列表切片 O(n)
元素检索 O(n)
复制 O(n)
添加单个元素所需的时间与列表的规模无关，而表格中其他操作的复杂度取决于列表的规模。列表的规模越大，性能受到的影响就越明显。

2.1.2 元组

与列表相反，元组是不可变的（只读）数据结构。


a = (1,2,3,4,5,6,7,(1,3,4,6,8),8,9)
print(type(a))
print(a[2:8])
----------------------------------------------------------------
(3, 4, 5, 6, 7, (1, 3, 4, 6, 8))

元组的时间复杂度：O(1)

元组是不可变的数据类型，其中没有append函数。。

2.1.3字典

以键值对的形式保存数据是非常重要的，尤其在分布式算法中。

要创建一个字典，应该选择一个在整个数据处理过程最适合识别数据的属性作为键。值可以是任何类型的元素。

Python总是使用复杂的数据类型（如列表）作为值。


a = {
    'color':'red',
    'age':18,
    'gender':'man',
    'classmate':['小李','小方','小王','小张']
}
print(a)
print(a.get('age')) # 通过键查找值
for k,v in a.items():   # 通过值查找键
    if v == 'red':
        print(k)
----------------------------------------------------------------
{'color': 'red', 'age': 18, 'gender': 'man', 'classmate': ['小李', '小方', '小王', '小张']}
18
color

字典的时间复杂度

功能	时间复杂度
获取一个值或一个键	O(1)
设置一个值或一个键	O(1)
复制一个字典	O(n)

获取或设置键值所需的时间和字典的大小无关。这意味着，将一个键值对添加到一个大小为3的字典中所花费的时间与将一个键值对添加到一个大小为100万的字典中所花费的时间是一样的。

2.1.4 集合

集合被定义为元素集，可以是不同类型的元素。


a = {2,4,6,8,10,55}
b = {1,3,5,7,9,55}
print(a|b)  # 并集  
print(a&b)  # 交集
----------------------------------------------------------------
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 55}
{55}

集合的时间复杂度

功能	时间复杂度
增加一个元素	O(1)
删除一个元素	O(1)
复制	O(n)

增删元素所需的时间与该集合的大小无关。

2.1.5 数据帧

数据帧是Python中pandas包中的一种数据结构，用来存储可用的表格数据。


import pandas as pd
df = pd.DataFrame([
    [1,'小李',23,'女'],
    [2,'小张',23,'男'],
    [3,'小王',22,'女'],
    [4,'小赵',25,'男']
])
df.columns = ['序号','姓名','年龄','性别']
print(df)
----------------------------------------------------------------
  序号  姓名  年龄 性别
0   1  小李  23  女
1   2  小张  23  男
2   3  小王  22  女
3   4  小赵  25  男
print(df[['姓名','性别']])# 检索
----------------------------------------------------------------
0  小李  女
1  小张  男
2  小王  女
3  小赵  男

数据帧术语

轴：在pandas文档中，一个数据帧的单列或单行称为轴。

轴族：如果轴的数量大于1，则它们作为一组，称为轴族。

标签：数据帧允许用标签来命名列和行。

2.1.6 矩阵

矩阵是一种具有固定列数和行数的二维数据结构，矩阵中的每个元素都可以通过指定它的列和行来引用。

在Python中，可以通过用numpy中的array函数来创建矩阵。


import numpy as np
x = np.array([[11,12,13],[21,22,23],[31,32,33]])
print(x)
print(type(x))
----------------------------------------------------------------
<class 'numpy.ndarray'>